Java中的链表结构是指，将一组数据按照指定规则连接起来的数据结构。它由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的引用。在Java中，这种数据结构被封装成了一个链表类，常见的有单向链表、双向链表和循环链表等。
一、单向链表
单向链表是最简单的一种链表结构，节点只包含一个数据元素和一个指向下一个节点的引用。它的优点是删除和插入节点非常方便，但是定位元素较为困难。
-
链表的节点定义
public class Node { // 节点的数据元素 private int data; // 指向下一个节点的引用 private Node next; // 构造函数 public Node(int data) { this.data = data; this.next = null; } // 获得数据元素 public int getData() { return data; } // 设置数据元素 public void setData(int data) { this.data = data; } // 获得下一个节点的引用 public Node getNext() { return next; } // 设置下一个节点的引用 public void setNext(Node next) { this.next = next; } } -
链表的操作方法
-
添加节点：向链表的末尾添加一个新节点
public void addNode(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node currentNode = head; while (currentNode.getNext() != null) { currentNode = currentNode.getNext(); } currentNode.setNext(newNode); } size++; } -
删除节点：删除链表中指定元素的节点
public boolean removeNode(int data) { if (head == null) { return false; } if (head.getData() == data) { head = head.getNext(); size--; return true; } Node currentNode = head; while (currentNode.getNext() != null) { if (currentNode.getNext().getData() == data) { currentNode.setNext(currentNode.getNext().getNext()); size--; return true; } currentNode = currentNode.getNext(); } return false; } -
查找节点：根据元素值查找节点
public Node findNode(int data) { if (head == null) { return null; } Node currentNode = head; while (currentNode != null) { if (currentNode.getData() == data) { return currentNode; } currentNode = currentNode.getNext(); } return null; }
-
二、双向链表
双向链表是在单向链表基础上增加了一个指向前一个节点的引用，这样可以方便地实现反向遍历和插入、删除操作。但是相应地，它需要占用更多的存储空间。
-
链表的节点定义
public class Node { // 节点的数据元素 private int data; // 指向下一个节点的引用 private Node next; // 指向前一个节点的引用 private Node prev; // 构造函数 public Node(int data) { this.data = data; this.next = null; this.prev = null; } // 获得数据元素 public int getData() { return data; } // 设置数据元素 public void setData(int data) { this.data = data; } // 获得下一个节点的引用 public Node getNext() { return next; } // 设置下一个节点的引用 public void setNext(Node next) { this.next = next; } // 获得前一个节点的引用 public Node getPrev() { return prev; } // 设置前一个节点的引用 public void setPrev(Node prev) { this.prev = prev; } } -
链表的操作方法
-
添加节点：向链表的末尾添加一个新节点
public void addNode(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node currentNode = head; while (currentNode.getNext() != null) { currentNode = currentNode.getNext(); } currentNode.setNext(newNode); newNode.setPrev(currentNode); } size++; } -
删除节点：删除链表中指定元素的节点
public boolean removeNode(int data) { if (head == null) { return false; } if (head.getData() == data) { head = head.getNext(); if (head != null) { head.setPrev(null); } size--; return true; } Node currentNode = head; while (currentNode != null) { if (currentNode.getData() == data) { currentNode.getPrev().setNext(currentNode.getNext()); if (currentNode.getNext() != null) { currentNode.getNext().setPrev(currentNode.getPrev()); } size--; return true; } currentNode = currentNode.getNext(); } return false; } -
查找节点：根据元素值查找节点
public Node findNode(int data) { if (head == null) { return null; } Node currentNode = head; while (currentNode != null) { if (currentNode.getData() == data) { return currentNode; } currentNode = currentNode.getNext(); } return null; }
-
三、循环链表
循环链表是一种特殊的链表结构，它的最后一个节点的指针不是指向null，而是指向第一个节点，形成一个环状结构。这样在循环遍历时可以省去边界判断，但是插入和删除操作需要特殊考虑。
-
链表的节点定义
public class Node { // 节点的数据元素 private int data; // 指向下一个节点的引用 private Node next; // 构造函数 public Node(int data) { this.data = data; this.next = null; } // 获得数据元素 public int getData() { return data; } // 设置数据元素 public void setData(int data) { this.data = data; } // 获得下一个节点的引用 public Node getNext() { return next; } // 设置下一个节点的引用 public void setNext(Node next) { this.next = next; } } -
链表的操作方法
-
添加节点：向链表的末尾添加一个新节点
public void addNode(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; head.setNext(head); } else { Node currentNode = head; while (currentNode.getNext() != head) { currentNode = currentNode.getNext(); } currentNode.setNext(newNode); newNode.setNext(head); } size++; } -
删除节点：删除链表中指定元素的节点
public boolean removeNode(int data) { if (head == null) { return false; } if (head.getData() == data) { Node currentNode = head; while (currentNode.getNext() != head) { currentNode = currentNode.getNext(); } head = head.getNext(); currentNode.setNext(head); size--; return true; } Node currentNode = head; while (currentNode.getNext() != head) { if (currentNode.getNext().getData() == data) { currentNode.setNext(currentNode.getNext().getNext()); size--; return true; } currentNode = currentNode.getNext(); } return false; } -
查找节点：根据元素值查找节点
public Node findNode(int data) { if (head == null) { return null; } Node currentNode = head; while (currentNode.getNext() != head) { if (currentNode.getData() == data) { return currentNode; } currentNode = currentNode.getNext(); } if (currentNode.getData() == data) { return currentNode; } return null; }
-
四、链表的时间复杂度分析
链表结构相比于数组具有更灵活的插入和删除操作，但是它也存在一些缺点。在访问随机元素时，需要从头开始遍历整个链表，时间复杂度为O(N)；而在数组中可以通过索引直接访问元素，时间复杂度为O(1)。下面给出单向链表、双向链表和循环链表的常见操作的时间复杂度：
| 操作 | 单向链表 | 双向链表 | 循环链表 |
|---|---|---|---|
| 访问元素 | O(N) | O(N) | O(N) |
| 插入元素 | O(1) | O(1) | O(1) |
| 删除元素 | O(N) | O(N) | O(N) |
五、链表的应用举例
链表结构常见于计算机科学领域中的各种数据结构与算法，例如栈、队列、哈希表和图等。下面以一个简单的应用场景为例，说明链表的应用。
-
题目描述
给定一个链表，判断它是否为回文链表。回文链表是指正序和倒序读取的结果相同的链表。
-
解题思路
可以使用快慢指针将链表分成两半，然后将后半部分反转，最后比较前半部分和反转后的后半部分是否相同。
-
代码实现
public boolean isPalindrome(Node head) { if (head == null || head.getNext() == null) { return true; } Node slow = head, fast = head; while (fast.getNext() != null && fast.getNext().getNext() != null) { slow = slow.getNext(); fast = fast.getNext().getNext(); } Node secondHalf = reverseList(slow.getNext()); Node currentNode = head; while (secondHalf != null) { if (currentNode.getData() != secondHalf.getData()) { return false; } currentNode = currentNode.getNext(); secondHalf = secondHalf.getNext(); } return true; } private Node reverseList(Node head) { if (head == null || head.getNext() == null) { return head; } Node prev = null, current = head; while (current != null) { Node next = current.getNext(); current.setNext(prev); prev = current; current = next; } return prev; }
六、使用场景
使用场景，常见的应用包括：
- 实现栈和队列：链表作为栈或队列的底层数据结构，实现入栈、出栈、入队、出队等操作时具有高效性和灵活性。
- 实现哈希表：在哈希表中，每个关键字会被映射到一个桶中，而这个桶则是一个链表，其中存放相同关键字的元素。
- 作为缓存的数据结构：在缓存中，经常需要在数据集中插入、删除、移动元素。链表结构提供了一种高效的方式来操作这些数据。
- 浏览器历史记录和撤销功能：浏览器历史记录和撤销功能等需要保留一系列操作或状态的应用场景都可以使用链表来实现。
- 实现图论算法：在图论中，使用链表结构可以方便地表示邻接表，保存每个节点的所有邻居节点。
- 数据库管理系统：在数据库管理系统中，可以使用链表来优化查询操作的效率。
