Java鏈表操作示例

一、什麼是鏈表

鏈表是一種數據結構，它由多個節點（node）組成，每個節點包含兩個屬性，一個是存儲的數據，另一個是指向下一個節點的指針。鏈表的優勢在於可以動態的增加和刪除元素。相對於數組而言，鏈表的內存分配更加靈活，但是在訪問某個節點時需要遍歷整個鏈表，時間複雜度為O(n)。

二、創建鏈表

下面是一個簡單的鏈表實現，它包括鏈表的節點類和鏈表類：

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    public LinkedList() {
        this.head = null;
    }

    public void add(int data) {
        Node node = new Node(data);
        if (this.head == null) {
            this.head = node;
        } else {
            Node temp = this.head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }
    }
}

三、鏈表的遍歷

遍歷鏈表指的是依次訪問鏈表中每個節點。下面是遍歷鏈表的一個示例方法：

public void traverse() {
    Node temp = this.head;
    while (temp != null) {
        System.out.print(temp.data + " ");
        temp = temp.next;
    }
    System.out.println();
}

四、在鏈表中插入一個新節點

下面給出了在鏈表中插入新節點的方法，如需在鏈表的第 i 個位置插入新節點，需要先定位到該位置的前一個節點，然後將新節點插入該節點之後。

public void insert(int data, int index) {
    Node node = new Node(data);

    if (index == 0) {
        node.next = this.head;
        this.head = node;
        return;
    }

    Node temp = this.head;
    for (int i = 0; i < index - 1; i++) {
        temp = temp.next;
    }

    node.next = temp.next;
    temp.next = node;
}

五、在鏈表中刪除一個節點

從鏈表中刪除節點的方法需要先定位到待刪節點的前一個節點，然後將前一個節點的指針指向待刪節點的下一個節點。

public void remove(int data) {
    if (this.head == null) {
        return;
    }

    if (this.head.data == data) {
        this.head = this.head.next;
        return;
    }

    Node temp = this.head;
    while (temp.next != null && temp.next.data != data) {
        temp = temp.next;
    }

    if (temp.next != null) {
        temp.next = temp.next.next;
    } else {
        System.out.println("節點不存在");
    }
}

六、鏈表的反轉

反轉鏈表指的是反轉鏈表中節點的順序。下面是一個遞歸實現的反轉鏈表方法：

public Node reverse(Node node) {
    if (node == null || node.next == null) {
        return node;
    }

    Node head = reverse(node.next);
    node.next.next = node;
    node.next = null;
    return head;
}

七、鏈表的排序

鏈表的排序指的是對鏈表中節點的數據進行排序。下面是一個使用快速排序的鏈表排序方法：

public Node sort(Node node) {
    if (node == null || node.next == null) {
        return node;
    }

    int pivot = node.data;
    Node left = null;
    Node right = null;
    node = node.next;

    while (node != null) {
        Node next = node.next;
        if (node.data < pivot) {
            node.next = left;
            left = node;
        } else {
            node.next = right;
            right = node;
        }
        node = next;
    }

    left = sort(left);
    right = sort(right);
    Node result = left;
    while (left != null && left.next != null) {
        left = left.next;
    }
    if (left != null) {
        left.next = new Node(pivot);
    } else {
        result = new Node(pivot);
        left = result;
    }
    left.next = right;
    return result;
}