一、单链表（Singly Linked List）
定义：单链表是一种链表结构，其中每个节点包含一个数据域和一个指向下一个节点的指针（next），最后一个节点的 next 指向 null，表示链表的末尾。
1. 特点
- 单向性：节点仅通过
next指针连接到下一个节点。 - 动态性：可以动态调整大小，在链表头部或尾部插入和删除元素时更为灵活。
2. 优点
- 插入和删除操作高效：在链表头或尾部插入和删除元素，时间复杂度为 O(1)。
- 空间利用率高：不需要预先分配大量内存，内存使用灵活。
3. 缺点
- 查找效率低：需要从头部开始遍历，查找元素的时间复杂度为 O(n)。
- 只能向前遍历：无法访问前一个节点，限制了操作的灵活性。
4. 应用场景
- 需要频繁插入和删除的场景：如实现队列、堆栈等动态数据结构。
- 不需要随机访问：如链表实现的栈、队列等场景。
5. 示例代码（Java）
class Node {int data;Node next;Node(int data) {this.data = data;this.next = null;}
}public class SinglyLinkedList {Node head;// 插入节点到链表头部public void insertAtHead(int data) {Node newNode = new Node(data);newNode.next = head;head = newNode;}// 输出链表public void display() {Node current = head;while (current != null) {System.out.print(current.data + " -> ");current = current.next;}System.out.println("null");}public static void main(String[] args) {SinglyLinkedList list = new SinglyLinkedList();list.insertAtHead(10);list.insertAtHead(20);list.insertAtHead(30);list.display(); // 输出：30 -> 20 -> 10 -> null}
}
二、双链表（Doubly Linked List）
定义：双链表是一种链表结构，其中每个节点包含三个部分：一个数据域，一个指向下一个节点的指针（next），以及一个指向上一个节点的指针（prev）。双链表可以从任意节点向前或向后遍历。
1. 特点
- 双向性：可以在两个方向上遍历链表。
- 节点占用内存增加：每个节点额外包含一个
prev指针。
2. 优点
- 灵活性更高：可以在头部和尾部插入和删除元素。
- 可以向前和向后遍历：方便在节点间双向操作。
3. 缺点
- 内存占用更大：每个节点多一个
prev指针，占用更多内存。 - 插入和删除操作稍复杂：需要更新
next和prev指针，增加了实现的复杂性。
4. 应用场景
- 双向遍历需求的场景：如浏览器的前进和后退功能、音乐播放器的播放列表。
- 缓存应用：双向链表适用于实现 LRU 缓存等场景。
5. 示例代码（Java）
class DoublyNode {int data;DoublyNode next;DoublyNode prev;DoublyNode(int data) {this.data = data;this.next = null;this.prev = null;}
}public class DoublyLinkedList {DoublyNode head;// 在链表头部插入节点public void insertAtHead(int data) {DoublyNode newNode = new DoublyNode(data);if (head != null) {head.prev = newNode;newNode.next = head;}head = newNode;}// 输出链表public void display() {DoublyNode current = head;while (current != null) {System.out.print(current.data + " <-> ");current = current.next;}System.out.println("null");}public static void main(String[] args) {DoublyLinkedList list = new DoublyLinkedList();list.insertAtHead(10);list.insertAtHead(20);list.insertAtHead(30);list.display(); // 输出：30 <-> 20 <-> 10 <-> null}
}
三、循环链表（Circular Linked List）
定义：循环链表是一种特殊的链表结构，其中最后一个节点的 next 指针指向链表的头部，形成一个闭环。循环链表可以是单链表或双链表。
1. 特点
- 循环结构：最后一个节点的
next指向头节点。 - 无头无尾：从任意节点开始遍历都能回到起点。
2. 优点
- 支持循环访问：可以从任意节点开始无限循环遍历。
- 高效处理循环队列：适用于队列循环、轮询等场景。
3. 缺点
- 实现复杂度稍高：需要注意处理指针操作，防止无限循环。
- 内存浪费：如果不需要循环特性，可能会浪费内存。
4. 应用场景
- 循环任务：如多任务调度、音乐播放器的循环播放。
- 环形缓冲区：适用于实时数据流或固定容量的数据缓存。
5. 示例代码（Java）
class CircularNode {int data;CircularNode next;CircularNode(int data) {this.data = data;this.next = null;}
}public class CircularLinkedList {CircularNode head;// 插入节点到链表尾部public void insert(int data) {CircularNode newNode = new CircularNode(data);if (head == null) {head = newNode;head.next = head; // 形成循环} else {CircularNode current = head;while (current.next != head) {current = current.next;}current.next = newNode;newNode.next = head; // 形成循环}}// 输出链表public void display() {if (head != null) {CircularNode current = head;do {System.out.print(current.data + " -> ");current = current.next;} while (current != head);System.out.println("(head)");}}public static void main(String[] args) {CircularLinkedList list = new CircularLinkedList();list.insert(10);list.insert(20);list.insert(30);list.display(); // 输出：10 -> 20 -> 30 -> (head)}
}
四、哨兵链表（Sentinel Linked List）
定义：哨兵链表是一种带有哨兵节点的链表结构。哨兵节点通常为一个空节点（不存储数据），仅用于标记链表的开始或结束，以简化链表的操作。
1. 特点
- 简化边界处理：哨兵节点不存储数据，仅用于标记链表的头尾。
- 减少特殊情况判断：避免插入和删除操作时的边界情况。
2. 优点
- 提高代码的简洁性：通过哨兵节点，减少了代码中对边界条件的检查。
- 提高插入和删除的效率：可以减少处理链表首尾的特殊情况。
3. 缺点
- 占用额外的空间：引入哨兵节点需要额外的空间。
- 实现稍复杂：需要在链表中添加和管理哨兵节点。
4. 应用场景
- 需要频繁插入和删除的场景：如双向链表、队列和栈等，避免对边界的处理。
- 需要简化代码逻辑：尤其在复杂链表操作中，有助于降低边界条件判断的复杂度。
5. 示例代码（Java）
class SentinelNode {int data;SentinelNode next;SentinelNode prev;SentinelNode(int data) {this.data = data;}
}public class SentinelLinkedList {SentinelNode head;SentinelNode tail;public SentinelLinkedList() {head = new SentinelNode(0); // 哨兵头节点tail = new SentinelNode(0); // 哨兵尾节点head.next = tail;tail.prev = head;}// 在尾部插入节点public void insertAtEnd(int data) {SentinelNode newNode = new SentinelNode(data);newNode.next = tail;newNode.prev = tail.prev;tail.prev.next = newNode;tail.prev = newNode;}// 输出链表public void display() {SentinelNode current = head.next;while (current != tail) {System.out.print(current.data + " <-> ");current = current.next;}System.out.println("null");}public static void main(String[] args) {SentinelLinkedList list = new SentinelLinkedList();list.insertAtEnd(10);list.insertAtEnd(20);list.insertAtEnd(30);list.display(); // 输出：10 <-> 20 <-> 30 <-> null}
}