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类就是一个链表的实现。学习链表需要掌握链表的基本原理和实现方法，并理解链表相比于数组的优缺点，以及适用的场景。