1. 简介
链表（Linked List）是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针（或引用）。链表的一个主要优点是能够高效地插入和删除元素，尤其是在数组中需要移动大量元素的情况下。
1.1 链表的基本操作
-
插入：可以在链表的任意位置插入新节点。
-
删除：可以从链表的任意位置删除节点。
-
查找：遍历链表查找特定的节点。
-
更新：修改链表中某个节点的值。
1.2 链表类型
链表有多种变体，每种类型在特定场景下有不同的应用。
-
单链表适用于简单的数据结构，头部插入和删除高效，适合实现栈、队列等数据结构。
-
双链表适用于需要频繁从两端或中间插入、删除节点的场景，适合实现双向队列、LRU缓存等。
-
循环链表适用于需要循环访问或周期性任务调度的场景，适合实现循环队列、约瑟夫问题等。
1.3 比较
| 特性 | 单链表 (Singly Linked List) | 双链表 (Doubly Linked List) | 循环链表 (Circular Linked List) |
| 节点结构 | 每个节点有一个指针指向下一个节点 | 每个节点有两个指针，分别指向前一个和下一个节点 | 最后一个节点的指针指向头节点，形成环 |
| 遍历方向 | 只能从头到尾遍历 | 可以从头到尾、从尾到头遍历 | 循环访问，遍历方向根据链表类型 |
| 空间复杂度 | O(n) | O(n) | O(n) |
| 插入和删除效率 | 在头部插入删除高效，其他位置较慢 | 在任意位置插入删除高效 | 插入删除效率与单链表或双链表类似，循环性优势 |
| 适用场景 | 适用于简单的线性访问 | 适用于需要从两端访问节点的场景 | 适用于需要循环遍历的场景 |
2. 单链表
单链表是最基本的链表类型，它的每个节点只包含一个指向下一个节点的指针。每个节点包含两个部分：数据域和指针域（指向下一个节点的指针）。
特点：
-
只能从头到尾进行单向遍历。
-
插入和删除操作通常比较高效，尤其在头部插入删除时。
class SinglyLinkedList {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
// 插入元素
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
// 打印链表
public void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("null");
}
}
3. 双链表
双链表是每个节点都有两个指针，一个指向下一个节点，另一个指向前一个节点。相比于单链表，双链表允许在两端（头尾）插入或删除节点，操作更灵活。
特点：
-
可以在两个方向（前后）进行遍历。
-
删除节点时更加灵活，可以直接访问前驱节点。
-
每个节点需要更多的内存来存储两个指针。
class DoublyLinkedList {
static class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
private Node head;
// 插入元素
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.prev = temp;
}
}
// 打印链表
public void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " <-> ");
temp = temp.next;
}
System.out.println("null");
}
}
4. 循环链表
循环链表是链表的变体，其中最后一个节点的指针指向头节点，形成一个环。循环链表可以是单向的（单循环链表）或双向的（双循环链表）。
特点：
-
可以从任意节点开始遍历，遍历过程中可以循环回到起点。
-
适合需要循环访问的场景，如实现循环队列、约瑟夫问题等。
4.1 单向循环链表
class CircularLinkedList {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
// 插入元素
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
newNode.next = head; // 成环
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = head; // 成环
}
}
// 打印链表
public void printList() {
if (head == null) return;
Node temp = head;
do {
System.out.print(temp.data + " -> ");
temp = temp.next;
} while (temp != head);
System.out.println("(back to head)");
}
}
4.2 双向循环链表
class CircularDoublyLinkedList {
static class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
private Node head;
// 插入元素
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
newNode.next = head;
newNode.prev = head;
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = newNode;
newNode.prev = temp;
newNode.next = head;
head.prev = newNode; // 将头节点的prev指针指向新节点
}
}
// 打印链表
public void printList() {
if (head == null) return;
Node temp = head;
do {
System.out.print(temp.data + " <-> ");
temp = temp.next;
} while (temp != head);
System.out.println("(back to head)");
}
}
不积跬步，无以至千里 --- xiaokai
