Java鏈表實現原理

一、什麼是鏈表

鏈表是一種數據結構，由一些節點組成，每個節點包含一個元素和指向下一個節點的指針。鏈表的特點是可以任意增刪元素，而不用像數組那樣需要移動其他元素。

二、鏈表的實現

鏈表的實現通常分為單鏈表、雙向鏈表和循環鏈表。

1. 單鏈表

單鏈表是最基本的鏈表結構，每個節點只包含一個後繼節點的指針，即next指針。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class LinkedList {
    private ListNode head;

    public LinkedList() {
        head = null;
    }

    public void add(int val) {
        if (head == null) {
            head = new ListNode(val);
        } else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new ListNode(val);
        }
    }

    public void remove(int val) {
        if (head == null) {
            return;
        }
        if (head.val == val) {
            head = head.next;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }

    public void print() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

2. 雙向鏈表

雙向鏈表是在單鏈表的基礎上，每個節點多了一個指向前驅節點的指針，即prev指針。

class ListNode {
    int val;
    ListNode prev;
    ListNode next;
    ListNode(int x) { val = x; }
}

class DoublyLinkedList {
    private ListNode head;

    public DoublyLinkedList() {
        head = null;
    }

    public void add(int val) {
        if (head == null) {
            head = new ListNode(val);
        } else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            ListNode newNode = new ListNode(val);
            cur.next = newNode;
            newNode.prev = cur;
        }
    }

    public void remove(int val) {
        if (head == null) {
            return;
        }
        if (head.val == val) {
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
                if (cur.next != null) {
                    cur.next.prev = cur;
                }
                return;
            }
            cur = cur.next;
        }
    }

    public void print() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

3. 循環鏈表

循環鏈表是在單鏈表或雙向鏈表的基礎上，將最後一個節點的指針指向頭節點，形成一個環形結構。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class CircularLinkedList {
    private ListNode head;

    public CircularLinkedList() {
        head = null;
    }

    public void add(int val) {
        if (head == null) {
            head = new ListNode(val);
            head.next = head;
        } else {
            ListNode cur = head;
            while (cur.next != head) {
                cur = cur.next;
            }
            ListNode newNode = new ListNode(val);
            cur.next = newNode;
            newNode.next = head;
        }
    }

    public void remove(int val) {
        if (head == null) {
            return;
        }
        if (head.val == val) {
            if (head.next == head) {
                head = null;
            } else {
                ListNode cur = head;
                while (cur.next != head) {
                    cur = cur.next;
                }
                head = head.next;
                cur.next = head;
            }
            return;
        }
        ListNode cur = head;
        while (cur.next != head) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }

    public void print() {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        do {
            System.out.print(cur.val + " ");
            cur = cur.next;
        } while (cur != head);
        System.out.println();
    }
}

三、鏈表的優缺點

鏈表的優點是可以對任意位置的元素進行增刪操作，並且空間利用率較高。鏈表的缺點是不能像數組那樣以O(1)的時間訪問任意位置的元素，需要遍歷整個鏈表，時間複雜度為O(n)，並且鏈表的節點需要額外的指針空間。

四、總結

鏈表是一種基本的數據結構，可以用於實現各種其它高級的數據結構，如棧、隊列、哈希表和圖等。Java中提供的LinkedList類就是一個鏈表的實現。學習鏈表需要掌握鏈表的基本原理和實現方法，並理解鏈表相比於數組的優缺點，以及適用的場景。