在Java中实现链表是一种基础且重要的数据结构学习。链表允许我们在不连续的内存地址中存储元素，每个元素（节点）包含数据部分和指向列表中下一个元素的引用（或链接）。这种结构非常适合动态数据集，其中元素数量经常变化，因为它提供了在链表任意位置快速插入和删除节点的能力。接下来，我们将逐步介绍如何在Java中从头开始实现一个基本的单向链表和双向链表。 ### 单向链表 单向链表是最简单的链表形式，其中每个节点仅包含数据和指向列表中下一个节点的链接。以下是实现单向链表的基本步骤： #### 1. 定义节点类 首先，我们需要定义一个`Node`类来表示链表中的每个节点。这个类将包含两部分：数据域和指向下一个节点的链接。 ```java class ListNode { int val; // 节点存储的数据 ListNode next; // 指向下一个节点的链接 // 构造函数 public ListNode(int val) { this.val = val; this.next = null; } } ``` #### 2. 定义链表类 接下来，我们定义一个`LinkedList`类来表示整个链表。这个类将包含一些基本操作，如添加元素、删除元素、遍历链表等。 ```java class LinkedList { ListNode head; // 链表的头节点 // 构造函数 public LinkedList() { this.head = null; } // 在链表末尾添加元素 public void add(int val) { ListNode newNode = new ListNode(val); if (head == null) { head = newNode; } else { ListNode current = head; while (current.next != null) { current = current.next; } current.next = newNode; } } // 删除链表中值为val的第一个节点 public void delete(int val) { if (head == null) return; if (head.val == val) { head = head.next; return; } ListNode current = head; while (current.next != null) { if (current.next.val == val) { current.next = current.next.next; return; } current = current.next; } } // 打印链表 public void printList() { ListNode current = head; while (current != null) { System.out.print(current.val + " -> "); current = current.next; } System.out.println("null"); } } ``` #### 3. 使用链表 现在，我们可以创建一个`LinkedList`的实例，并使用定义的方法来操作链表。 ```java public class Main { public static void main(String[] args) { LinkedList list = new LinkedList(); list.add(1); list.add(2); list.add(3); list.printList(); // 输出: 1 -> 2 -> 3 -> null list.delete(2); list.printList(); // 输出: 1 -> 3 -> null } } ``` ### 双向链表 双向链表与单向链表相似，但每个节点还包含指向前一个节点的链接。这种结构使得从后向前遍历链表变得简单，并且允许我们在O(1)时间复杂度内访问任何节点的前一个节点。 #### 1. 定义节点类 ```java class DoublyListNode { int val; DoublyListNode prev; // 指向前一个节点的链接 DoublyListNode next; // 指向下一个节点的链接 public DoublyListNode(int val) { this.val = val; this.prev = null; this.next = null; } } ``` #### 2. 定义链表类 ```java class DoublyLinkedList { DoublyListNode head; DoublyListNode tail; // 链表的尾节点，便于在链表末尾添加元素 public DoublyLinkedList() { this.head = null; this.tail = null; } // 在链表末尾添加元素 public void add(int val) { DoublyListNode newNode = new DoublyListNode(val); if (head == null) { head = newNode; tail = newNode; } else { tail.next = newNode; newNode.prev = tail; tail = newNode; } } // 删除链表中值为val的第一个节点 public void delete(int val) { if (head == null) return; if (head.val == val) { head = head.next; if (head != null) { head.prev = null; } if (head == tail) { tail = null; } return; } DoublyListNode current = head; while (current.next != null) { if (current.next.val == val) { current.next = current.next.next; if (current.next != null) { current.next.prev = current; } if (tail == current.next) { tail = current; } return; } current = current.next; } } // 打印链表 public void printList() { DoublyListNode current = head; while (current != null) { System.out.print(current.val + " <-> "); current = current.next; } System.out.println("null"); } } ``` #### 3. 使用双向链表 ```java public class Main { public static void main(String[] args) { DoublyLinkedList list = new DoublyLinkedList(); list.add(1); list.add(2); list.add(3); list.printList(); // 输出: 1 <-> 2 <-> 3 <-> null list.delete(2); list.printList(); // 输出: 1 <-> 3 <-> null } } ``` ### 总结 通过上面的介绍，我们学习了如何在Java中实现单向链表和双向链表。链表是一种灵活的数据结构，非常适合在元素数量动态变化时保持数据的完整性。掌握链表的基本概念和操作方法对于深入学习更复杂的数据结构和算法至关重要。如果你对链表有进一步的兴趣，可以尝试实现循环链表、跳表等高级链表变种，并在实践中加深对链表操作的理解。同时，通过不断练习，你将能更加熟练地运用链表来解决实际问题，并在数据结构和算法的学习中迈出坚实的一步。 最后，提到"码小课"，这是一个专注于编程教育的平台，为学习者提供了丰富的编程课程和实践机会。通过参与码小课的学习，你可以系统地掌握编程技能，深入理解各种数据结构和算法，从而在编程道路上不断前行。