在 Java 中创建链表

简介

链表是一种重要的数据结构，在 Java 编程中广泛应用。与数组不同，链表的元素在内存中并非连续存储，而是通过节点（Node）相互连接。每个节点包含数据以及指向下一个节点的引用（在双向链表中还包含指向前一个节点的引用）。了解如何在 Java 中创建和操作链表对于掌握数据结构和算法至关重要，它能帮助开发者更高效地解决各种实际问题。

链表基础概念

链表是由一系列节点组成的数据结构。每个节点包含两部分：数据部分和引用部分。数据部分存储实际的数据值，引用部分则存储下一个节点的内存地址（在单链表中），或者同时存储上一个节点和下一个节点的内存地址（在双向链表中）。这种结构使得链表在插入和删除操作上具有高效性，因为无需像数组那样移动大量元素，只需修改节点的引用即可。

使用方法

单链表创建

在 Java 中创建单链表，首先需要定义节点类，然后通过节点类构建链表。

// 定义单链表节点类
class ListNode {
    int data;
    ListNode next;

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

// 创建单链表并进行简单操作
public class SinglyLinkedList {
    public static void main(String[] args) {
        // 创建节点
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);

        // 连接节点
        head.next = second;
        second.next = third;

        // 遍历链表
        ListNode current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

双向链表创建

双向链表的节点不仅包含指向下一个节点的引用，还包含指向前一个节点的引用。

// 定义双向链表节点类
class DoublyListNode {
    int data;
    DoublyListNode next;
    DoublyListNode prev;

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

// 创建双向链表并进行简单操作
public class DoublyLinkedList {
    public static void main(String[] args) {
        // 创建节点
        DoublyListNode head = new DoublyListNode(1);
        DoublyListNode second = new DoublyListNode(2);
        DoublyListNode third = new DoublyListNode(3);

        // 连接节点
        head.next = second;
        second.prev = head;
        second.next = third;
        third.prev = second;

        // 正向遍历链表
        DoublyListNode current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();

        // 反向遍历链表
        current = third;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
    }
}

常见实践

插入节点

在链表头部插入节点

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

在链表中间或尾部插入节点

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

删除节点

删除链表头部节点

// 删除单链表头部节点
public static ListNode deleteHead(ListNode head) {
    if (head == null) {
        return null;
    }
    return head.next;
}

删除链表指定节点

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

遍历链表

迭代遍历

// 迭代遍历单链表
public static void traverse(ListNode head) {
    ListNode current = head;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
}

递归遍历

// 递归遍历单链表
public static void recursiveTraverse(ListNode head) {
    if (head == null) {
        return;
    }
    System.out.print(head.data + " ");
    recursiveTraverse(head.next);
}

最佳实践

内存管理

在链表操作中，及时释放不再使用的节点内存非常重要。当删除节点时，确保将节点的引用设置为 null，以便 Java 的垃圾回收器能够回收内存。

// 删除节点并释放内存
public static ListNode deleteAndFreeMemory(ListNode head, int data) {
    if (head == null) {
        return null;
    }
    if (head.data == data) {
        ListNode temp = head;
        head = head.next;
        temp = null; // 释放内存
        return head;
    }
    ListNode current = head;
    while (current.next != null && current.next.data != data) {
        current = current.next;
    }
    if (current.next != null) {
        ListNode temp = current.next;
        current.next = current.next.next;
        temp = null; // 释放内存
    }
    return head;
}

性能优化

对于频繁的插入和删除操作，双向链表可能更适合，因为可以直接访问前一个节点，减少遍历时间。同时，在遍历链表时，尽量避免不必要的重复遍历，可以将中间结果存储起来。

小结

在 Java 中创建和操作链表是一项基础而重要的技能。通过理解链表的基本概念，掌握单链表和双向链表的创建方法，以及常见的插入、删除和遍历操作，开发者能够更灵活地处理各种数据处理需求。遵循最佳实践，如合理的内存管理和性能优化，能使链表的使用更加高效和可靠。

参考资料

《Effective Java》 - Joshua Bloch
Oracle Java 官方文档
LeetCode 等在线算法平台相关链表题目及解答