如何在 Java 中实现链表结构？从基本概念到链表操作的完整实现？

news/2025/10/1 4:36:37/文章来源:href="https://blog.51cto.com/u_15701057/14109578" target="_blank"

大佬们好！我是LKJ_Coding，一枚初级马牛，正在努力在代码的丛林中找寻自己的方向。如果你也曾在调试中迷失，或是在文档中翻滚，那我们一定有许多共同话题可以聊！今天，我带着满满的代码“干货”来和大家分享，学不学无所谓，反正我先吐槽了！

前言

链表（Linked List）是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的引用。链表的优势在于它的动态大小，能够有效地进行元素的插入和删除操作，特别是在频繁修改数据的场景下，相比于数组，链表的效率更高。

本文将介绍链表的基本概念，如何在 Java 中实现单链表和双链表，并展示如何进行常见的链表操作，如增、删、查、改等。通过代码示例，帮助你更好地理解和实现链表结构。

1. 链表的基本概念

1.1 链表的定义

链表是一种由节点组成的线性数据结构。每个节点包含两个部分：

数据部分：存储实际的数据。
指针部分：指向下一个节点（在双链表中，指向前一个节点和下一个节点）。

1.2 链表的种类

单链表（Singly Linked List）：每个节点只包含指向下一个节点的引用。
双链表（Doubly Linked List）：每个节点包含指向下一个节点和上一个节点的引用。

链表的主要特点是，它的元素存储位置不需要连续，可以随时动态插入和删除元素。

2. 单链表和双链表的实现

2.1 单链表的实现

单链表由一个头节点（head）开始，每个节点指向下一个节点，直到链表的尾节点，其 next 指针为 null。

2.1.1 单链表的节点定义

class Node {int data;       // 数据部分Node next;      // 指向下一个节点的指针// 节点构造器Node(int data) {this.data = data;this.next = null;}
}class SinglyLinkedList {Node head; // 链表头节点// 构造方法public SinglyLinkedList() {this.head = null;}// 向链表末尾添加新节点public void append(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;} else {Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;}}// 打印链表内容public void printList() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();}// 删除指定值的节点public void delete(int value) {if (head == null) return;// 如果要删除的节点是头节点if (head.data == value) {head = head.next;return;}Node current = head;while (current.next != null && current.next.data != value) {current = current.next;}// 如果找到了要删除的节点if (current.next != null) {current.next = current.next.next;}}// 查找指定值的节点public boolean search(int value) {Node current = head;while (current != null) {if (current.data == value) {return true;}current = current.next;}return false;}
}

2.1.2 代码解析

append(int data)：将一个新节点添加到链表末尾。
printList()：打印链表的所有元素。
delete(int value)：删除链表中指定值的节点。如果头节点是目标节点，更新头节点。
search(int value)：查找链表中是否包含指定的值。

2.2 双链表的实现

双链表的每个节点不仅有指向下一个节点的指针（next），还有指向前一个节点的指针（prev）。双链表的优点是可以在 O(1) 的时间复杂度内进行双向遍历和删除操作。

2.2.1 双链表的节点定义

class DoublyNode {int data;         // 数据部分DoublyNode next;  // 指向下一个节点的指针DoublyNode prev;  // 指向前一个节点的指针// 节点构造器DoublyNode(int data) {this.data = data;this.next = null;this.prev = null;}
}class DoublyLinkedList {DoublyNode head;  // 链表头节点DoublyNode tail;  // 链表尾节点// 构造方法public DoublyLinkedList() {this.head = null;this.tail = null;}// 向链表末尾添加新节点public void append(int data) {DoublyNode newNode = new DoublyNode(data);if (head == null) {head = newNode;tail = newNode;} else {tail.next = newNode;newNode.prev = tail;tail = newNode;}}// 打印链表内容public void printList() {DoublyNode current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();}// 删除指定值的节点public void delete(int value) {if (head == null) return;// 如果要删除的节点是头节点if (head.data == value) {head = head.next;if (head != null) {head.prev = null;}return;}DoublyNode current = head;while (current != null && current.data != value) {current = current.next;}// 如果找到了要删除的节点if (current != null) {if (current.next != null) {current.next.prev = current.prev;}if (current.prev != null) {current.prev.next = current.next;}}}// 查找指定值的节点public boolean search(int value) {DoublyNode current = head;while (current != null) {if (current.data == value) {return true;}current = current.next;}return false;}
}

2.2.2 代码解析

append(int data)：将新节点添加到双链表末尾，并更新 prev 和 next 指针。
delete(int value)：删除双链表中指定值的节点。如果节点在链表头或尾部，需要特殊处理 prev 和 next 指针。
search(int value)：查找链表中是否存在指定值的节点。

3. 链表操作总结

增：在链表的头部、尾部或中间插入节点。使用 append() 方法可以在尾部添加节点，使用 insertAtHead() 或 insertAtIndex() 方法可以在头部或指定位置插入节点。
删：通过查找并删除指定节点，可以使用 delete() 方法删除节点。
查：使用 search() 方法查找链表中是否存在指定值的节点。
改：可以通过修改节点的 data 值来更新链表中的元素。

4. 代码示例：实现链表类及其操作

以下是完整的代码示例，展示如何实现一个简单的单链表和双链表结构，并进行增、删、查、改等操作。

public class LinkedListDemo {public static void main(String[] args) {// 单链表示例SinglyLinkedList singlyLinkedList = new SinglyLinkedList();singlyLinkedList.append(10);singlyLinkedList.append(20);singlyLinkedList.append(30);singlyLinkedList.printList(); // 输出：10 20 30singlyLinkedList.delete(20);singlyLinkedList.printList(); // 输出：10 30// 双链表示例DoublyLinkedList doublyLinkedList = new DoublyLinkedList();doublyLinkedList.append(100);doublyLinkedList.append(200);doublyLinkedList.append(300);doublyLinkedList.printList(); // 输出：100 200 300doublyLinkedList.delete(200);doublyLinkedList.printList(); // 输出：100 300}
}