8. 什么是链表？如何在Java中实现单链表和双向链表？

PangHu大约 5 分钟

1. 什么是链表？

链表（Linked List） 是一种线性数据结构，它由一系列节点（Node）组成，每个节点包含两个部分：

数据部分（Data）：存储数据的部分。
指针部分（Next）：指向下一个节点的引用或指针。

链表的特点是每个节点都是动态分配的，不像数组那样需要预先分配固定大小的内存，因此链表的大小可以灵活调整。根据节点之间的链接方式，链表可以分为几种常见类型：

单链表（Singly Linked List）：每个节点只包含一个指向下一个节点的引用。
双向链表（Doubly Linked List）：每个节点包含两个引用，一个指向下一个节点，另一个指向前一个节点。
循环链表（Circular Linked List）：链表的最后一个节点指向链表的第一个节点，形成一个环。

2. 在 Java 中实现单链表

2.1 单链表的实现

单链表由一系列节点组成，每个节点包含数据和一个指向下一个节点的引用。链表中只有一个头节点（head），用于标识链表的起点。

示例代码：

public class SinglyLinkedList {
    // 定义链表节点的内部类
    private static class Node {
        int data;
        Node next;

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

    private Node head;

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

    // 在链表末尾添加节点
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }

    // 在链表开头添加节点
    public void prepend(int data) {
        Node newHead = new Node(data);
        newHead.next = head;
        head = newHead;
    }

    // 删除链表中指定值的节点
    public void deleteWithValue(int data) {
        if (head == null) return;

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

        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // 打印链表中的所有节点
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.prepend(0);
        list.printList();

        list.deleteWithValue(2);
        list.printList();
    }
}

输出示例：

0 -> 1 -> 2 -> 3 -> null
0 -> 1 -> 3 -> null

2.2 单链表的操作说明

append(int data)：在链表末尾添加一个新的节点。如果链表为空，新的节点将成为头节点。
prepend(int data)：在链表的开头添加一个新的节点，该节点将成为新的头节点。
deleteWithValue(int data)：删除链表中第一个值为 data 的节点。如果找到该节点，将其从链表中移除。
printList()：打印链表中的所有节点。

3. 在 Java 中实现双向链表

3.1 双向链表的实现

双向链表与单链表类似，但每个节点除了指向下一个节点的引用外，还包含一个指向前一个节点的引用。这样可以在链表中进行双向遍历。

示例代码：

public class DoublyLinkedList {
    // 定义链表节点的内部类
    private static class Node {
        int data;
        Node next;
        Node prev;

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

    private Node head;

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

    // 在链表末尾添加节点
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        Node newNode = new Node(data);
        current.next = newNode;
        newNode.prev = current;
    }

    // 在链表开头添加节点
    public void prepend(int data) {
        Node newHead = new Node(data);
        if (head != null) {
            head.prev = newHead;
        }
        newHead.next = head;
        head = newHead;
    }

    // 删除链表中指定值的节点
    public void deleteWithValue(int data) {
        if (head == null) return;

        if (head.data == data) {
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
            return;
        }

        Node current = head;
        while (current != null) {
            if (current.data == data) {
                if (current.prev != null) {
                    current.prev.next = current.next;
                }
                if (current.next != null) {
                    current.next.prev = current.prev;
                }
                return;
            }
            current = current.next;
        }
    }

    // 打印链表中的所有节点（从头到尾）
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.prepend(0);
        list.printList();

        list.deleteWithValue(2);
        list.printList();
    }
}

输出示例：

0 -> 1 -> 2 -> 3 -> null
0 -> 1 -> 3 -> null

3.2 双向链表的操作说明

append(int data)：在链表末尾添加一个新的节点。如果链表为空，新的节点将成为头节点。并更新 prev 引用。
prepend(int data)：在链表的开头添加一个新的节点，该节点将成为新的头节点，并更新 prev 引用。
deleteWithValue(int data)：删除链表中第一个值为 data 的节点。如果找到该节点，将其从链表中移除，并更新前后节点的 next 和 prev 引用。
printList()：打印链表中的所有节点，从头到尾进行双向遍历。

4. 单链表和双向链表的比较

特性	单链表	双向链表
指针数量	每个节点有一个指针，指向下一个节点	每个节点有两个指针，分别指向下一个和上一个节点
内存占用	较小，只有一个指针的空间开销	较大，每个节点有两个指针的空间开销
遍历方向	只能从头到尾遍历	可以从头到尾或从尾到头遍历
插入/删除效率	插入/删除节点时，可能需要遍历前驱节点	插入/删除效率更高，无需遍历前驱节点
实现复杂度	相对简单	需要处理前后节点的链接，较为复杂

5. 总结

链表是一种灵活的线性数据结构，适用于在动态插入、删除操作较多的场景。单链表结构简单，适合存储方向固定的数据结构，而双向链表则提供了双向遍历的能力，适用于需要在任意方向操作的场景。通过理解和实现单链表与双向链表，可以更好地掌握链表这种基础的数据结构在实际开发中的应用。