Java Program Implement LinkedList (Singly Linked List)

Linked List คืออะไร?

Linked List เป็นโครงสร้างข้อมูล Linear ประกอบด้วย Nodes ที่เชื่อมต่อกันผ่าน Reference/Pointer แต่ละ Node มี:

• Data - ข้อมูลที่เก็บ
• Next - Reference ไป Node ถัดไป

แตกต่างจาก Array: ไม่ต้องการหน่วยความจำติดกัน, ขนาดไดนามิก, Insert/Delete ที่กลาง O(1) (ถ้ามี Reference)

Node Class Design

static class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Operations พื้นฐาน

1. Insert at End (Append)

public static Node insert(Node head, int data) {
    Node newNode = new Node(data);
    
    if (head == null) {
        return newNode; // List ว่าง Node ใหม่กลายเป็น Head
    }
    
    // เดินหา Node สุดท้าย
    Node current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
    return head;
}

2. Insert at Beginning (Prepend)

public static Node prepend(Node head, int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    return newNode; // Head ใหม่
}

3. Delete by Value

public static Node delete(Node head, int key) {
    if (head == null) return null;
    
    // ลบ Head
    if (head.data == key) {
        return head.next;
    }
    
    // หา Node ก่อน Node ที่จะลบ
    Node current = head;
    while (current.next != null && current.next.data != key) {
        current = current.next;
    }
    
    // พบ Node ที่จะลบ
    if (current.next != null) {
        current.next = current.next.next;
    }
    
    return head;
}

4. Search

public static boolean search(Node head, int key) {
    Node current = head;
    while (current != null) {
        if (current.data == key) return true;
        current = current.next;
    }
    return false;
}

5. Print/Traverse

public static void printList(Node head) {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
}

ตัวอย่างที่ 1: ใน main โดยตรง

public class Demo {
    Node head;
    
    static class Node {
        int data;
        Node nextElement;
        Node(int element) {
            data = element;
            nextElement = null;
        }
    }
    
    public static Demo insert(Demo list, int data) {
        Node newNode = new Node(data);
        newNode.nextElement = null;
        
        if (list.head == null) {
            list.head = newNode;
        } else {
            Node last = list.head;
            while (last.nextElement != null) {
                last = last.nextElement;
            }
            last.nextElement = newNode;
        }
        return list;
    }
    
    public static void main(String[] args) {
        Demo inputList = new Demo();
        System.out.print("A linked list is declared: \n");
        
        inputList = insert(inputList, 100);
        inputList = insert(inputList, 150);
        inputList = insert(inputList, 200);
        inputList = insert(inputList, 250);
        
        Node current = inputList.head;
        System.out.print("The elements of the linked list are: \n");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.nextElement;
        }
    }
}

ผลลัพธ์

A linked list is declared: 
The elements of the linked list are: 
100 150 200 250

ตัวอย่างที่ 2: แยกเมธอด (OOP Style)

public class Demo {
    Node head;
    
    static class Node {
        int data;
        Node nextElement;
        Node(int element) {
            data = element;
            nextElement = null;
        }
    }
    
    public static Demo insert(Demo list, int data) {
        Node newNode = new Node(data);
        newNode.nextElement = null;
        
        if (list.head == null) {
            list.head = newNode;
        } else {
            Node last = list.head;
            while (last.nextElement != null) {
                last = last.nextElement;
            }
            last.nextElement = newNode;
        }
        return list;
    }
    
    public static void printList(Demo list) {
        Node current = list.head;
        System.out.print("The elements of the linked list are: \n");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.nextElement;
        }
    }
    
    public static void main(String[] args) {
        Demo inputList = new Demo();
        System.out.print("A linked list is declared: \n");
        
        inputList = insert(inputList, 100);
        inputList = insert(inputList, 150);
        inputList = insert(inputList, 200);
        inputList = insert(inputList, 250);
        
        printList(inputList);
    }
}

การปรับปรุง: Tail Reference (O(1) Append)

เก็บ Reference ไป Node สุดท้าย (Tail) เพื่อ Append O(1)

public class BetterLinkedList {
    Node head;
    Node tail; // เพิ่ม Tail Reference
    int size;
    
    static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }
    
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }
    
    public void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
        if (tail == null) tail = head;
        size++;
    }
}

java.util.LinkedList (Built-in)

ใน Production ใช้ Built-in java.util.LinkedList<E>:

import java.util.LinkedList;

LinkedList list = new LinkedList<>();
list.add("A");        // Add Last
list.addFirst("B");   // Add First
list.addLast("C");    // Add Last
list.removeFirst();   // Remove First
list.removeLast();    // Remove Last
list.getFirst();      // Peek First
list.getLast();       // Peek Last

Singly vs Doubly Linked List

สรุป

• Linked List = Node chain (Data + Next Pointer)
• Operations: Insert (Head/Tail/Middle), Delete, Search, Traverse
• Append O(n) โดยไม่มี Tail, O(1) ถ้ามี Tail Reference
• Built-in: java.util.LinkedList (Doubly Linked List)
• เหมาะสำหรับ: Frequent Insert/Delete at ends, Unknown Size