Java 中链表的实现

简介

在 Java 编程中，链表（Linked List）是一种重要的数据结构。它由一系列节点组成，每个节点包含数据和指向下一个节点的引用（在双向链表中还包含指向前一个节点的引用）。链表与数组不同，它的元素在内存中并不连续存储，这使得链表在插入和删除操作上具有更高的效率，尤其适用于需要频繁进行这些操作的场景。本文将详细介绍 Java 中链表的基础概念、使用方法、常见实践以及最佳实践。

基础概念

链表是一种线性数据结构，它由节点（Node）组成。每个节点包含两部分：数据（data）和指向下一个节点的引用（next）。在双向链表中，节点还包含指向前一个节点的引用（prev）。链表的头节点（head）是链表的起始点，通过头节点可以遍历整个链表。链表的最后一个节点的 next 引用通常为 null，表示链表的结束。

使用方法

单链表

以下是一个简单的单链表实现示例：

class ListNode {
    int val;
    ListNode next;

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

public class SinglyLinkedList {
    private ListNode head;

    public SinglyLinkedList() {
        head = null;
    }

    // 添加节点到链表尾部
    public void addNode(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
            return;
        }
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 打印链表
    public void printList() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

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

双向链表

双向链表的节点包含指向前一个节点和后一个节点的引用，以下是双向链表的实现示例：

class DoublyListNode {
    int val;
    DoublyListNode next;
    DoublyListNode prev;

    DoublyListNode(int x) {
        val = x;
    }
}

public class DoublyLinkedList {
    private DoublyListNode head;
    private DoublyListNode tail;

    public DoublyLinkedList() {
        head = null;
        tail = null;
    }

    // 添加节点到链表尾部
    public void addNode(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }

    // 打印链表
    public void printList() {
        DoublyListNode current = head;
        while (current != null) {
            System.out.print(current.val + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

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

常见实践

遍历链表

遍历链表是常见的操作之一。对于单链表，可以从头部开始，通过 next 引用依次访问每个节点，直到 next 为 null。对于双向链表，既可以从头部开始，也可以从尾部开始遍历。

// 单链表遍历
public void traverseSinglyList() {
    ListNode current = head;
    while (current != null) {
        System.out.println(current.val);
        current = current.next;
    }
}

// 双向链表遍历（从头部开始）
public void traverseDoublyListFromHead() {
    DoublyListNode current = head;
    while (current != null) {
        System.out.println(current.val);
        current = current.next;
    }
}

// 双向链表遍历（从尾部开始）
public void traverseDoublyListFromTail() {
    DoublyListNode current = tail;
    while (current != null) {
        System.out.println(current.val);
        current = current.prev;
    }
}

插入节点

插入节点可以在链表的头部、中间或尾部进行。在头部插入节点时，只需将新节点的 next 指向原头部节点，然后将头节点更新为新节点。在中间或尾部插入节点时，需要先找到合适的位置，然后调整节点的引用。

// 在单链表头部插入节点
public void insertAtHead(int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = head;
    head = newNode;
}

// 在单链表指定位置插入节点
public void insertAtPosition(int val, int position) {
    ListNode newNode = new ListNode(val);
    if (position == 0) {
        newNode.next = head;
        head = newNode;
        return;
    }
    ListNode current = head;
    for (int i = 0; i < position - 1 && current != null; i++) {
        current = current.next;
    }
    if (current != null) {
        newNode.next = current.next;
        current.next = newNode;
    }
}

删除节点

删除节点时，需要先找到要删除的节点，然后调整其前一个节点的 next 引用，跳过要删除的节点。

// 删除单链表中的指定节点
public void deleteNode(int val) {
    if (head == null) {
        return;
    }
    if (head.val == val) {
        head = head.next;
        return;
    }
    ListNode current = head;
    while (current.next != null && current.next.val != val) {
        current = current.next;
    }
    if (current.next != null) {
        current.next = current.next.next;
    }
}

最佳实践

选择合适的链表类型

如果只需要单向遍历链表，并且对插入和删除操作的效率要求较高，单链表是一个不错的选择。如果需要双向遍历链表，或者在删除节点时需要快速找到前一个节点，双向链表更为合适。

内存管理

在使用链表时，要注意内存管理。当删除节点时，确保正确释放相关的内存。在 Java 中，垃圾回收机制会自动回收不再使用的对象，但如果存在循环引用，可能会导致对象无法被回收。

避免循环引用

循环引用是链表中常见的问题，可能导致无限循环。在实现链表时，要确保节点的引用关系正确，避免形成循环。可以在插入和删除节点时进行必要的检查。

小结

本文详细介绍了 Java 中链表的基础概念、使用方法、常见实践以及最佳实践。链表作为一种重要的数据结构，在许多算法和应用中都有广泛的应用。通过掌握链表的实现和操作，能够提高程序的效率和性能。希望读者通过本文的学习，能够深入理解并高效使用 Java 中的链表。

参考资料

《Effective Java》
Oracle Java 官方文档
LeetCode 链表相关题目及讨论区