【链表小结】
链表（Linked List）是一种动态数据结构，由一系列的节点（Node）按顺序连接而成，每个节点包含数据域和指向下一个节点的指针（或引用）。链表通过指针将节点连接成一个有序的序列。链表的基本组成部分包括头指针、头结点和首元结点，这些概念有助于理解链表的结构和操作。
1. 头指针（Head Pointer）
头指针是链表的入口点，它指向链表的第一个节点。头指针对于链表的操作非常重要，因为通过头指针可以访问到整个链表。在大多数情况下，头指针是一个链表的公开接口，指向链表的第一个节点或为空（表示链表为空）。
- 如果头指针为
null，则链表为空。 - 如果头指针不为
null，则指向链表的第一个节点。
在不同类型的链表中，头指针的角色略有不同。它可能指向一个虚拟的头结点（如双链表中的头结点）或直接指向链表的第一个实际数据节点。
2. 头结点（Head Node）
头结点是链表的第一个节点，有时它也称为虚拟头结点。它的存在主要是为了方便链表操作，尤其是在处理空链表和对链表进行插入或删除时。头结点并不存储有效数据，通常它的指针指向链表中的第一个数据节点。
头结点的作用：
- 统一接口：提供一个统一的接口，即使链表为空，头结点也存在，减少对链表头部插入和删除操作的特殊处理。
- 简化操作：插入和删除操作时，可以避免处理链表为空或操作第一个节点时的特殊情况。
头结点通常用于双向链表和单向链表中。在没有头结点的链表中，头指针直接指向链表的第一个节点。
3. 首元结点（First Node）
首元结点是链表中的第一个数据节点，通常是链表的有效数据的起始点。对于一个链表来说，首元结点是链表中的第一个具有实际意义的数据节点。
- 在单向链表中，头指针指向首元结点（如果存在）。
- 在双向链表中，头指针指向首元结点，同时每个节点都有指向前后节点的指针。
4. 链表结构示意
(1) 单链表（Singly Linked List）
单链表中的每个节点包含两个部分：数据部分和指向下一个节点的指针。头指针指向链表的第一个数据节点（首元结点）。
Head Pointer -> [data | next] -> [data | next] -> [data | next] -> null
在单链表中，节点有一个 next 指针，指向下一个节点。当链表为空时，头指针指向 null。
(2) 双链表（Doubly Linked List）
双链表中的每个节点包含三个部分：数据部分、指向前一个节点的指针和指向下一个节点的指针。头指针指向链表的第一个数据节点（首元结点）。
Head Pointer -> [prev | data | next] <-> [prev | data | next] <-> [prev | data | next] -> null
在双链表中，每个节点不仅包含指向下一个节点的指针 next，还包含指向前一个节点的指针 prev。头指针指向链表的首元结点。
(3) 循环链表（Circular Linked List）
循环链表是指链表的最后一个节点指向链表的第一个节点，形成一个环。在单向循环链表中，最后一个节点的 next 指针指向头节点。头指针指向首元结点，但循环链表的最后一个节点指向头结点，而不是 null。
Head Pointer -> [data | next] -> [data | next] -> [data | next]
链表结构和顺序表（数组）结构有一些不同，它们的插入、删除、查找操作在时间复杂度上有所差异。我们将通过实现单链表、双链表和循环链表来完成顺序表中的各项操作，主要包括：插入、删除、获取元素、修改元素等。通过链表实现这些操作，不同类型的链表会有不同的优势。
5. 对比总结
| 名称 | 说明 |
|---|---|
| 头指针 | 指向链表的第一个节点的指针，是链表的入口点。 |
| 头结点 | 链表的第一个节点，可能是一个虚拟的节点，用于简化链表的操作。 |
| 首元结点 | 链表中实际存储数据的第一个节点，通常是链表的有效数据节点。 |
链表的操作通常依赖于头指针，因为头指针是链表的起始位置。头结点和首元结点的区别在于，头结点可能只是一个辅助节点，而首元结点才是真正存储数据的节点。理解这些组成部分有助于更好地理解链表的结构和常见操作。
下面是单链表、双链表和循环链表中常见操作的实现。
1. 单链表（Singly Linked List）
节点结构：
public class SinglyLinkedList {
private class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head; // 头节点
private int size; // 链表大小
public SinglyLinkedList() {
head = null;
size = 0;
}
}
插入操作
插入元素可以在链表的任何位置进行（包括头部、尾部和中间位置）。我们会实现在指定位置插入元素的操作。
// 插入元素到链表指定位置
public void insert(int index, int element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node newNode = new Node(element);
if (index == 0) { // 插入到头部
newNode.next = head;
head = newNode;
} else { // 插入到中间或尾部
Node current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
size++;
}
删除操作
删除指定位置的元素，类似地，我们需要通过遍历找到该位置，然后修改前驱节点的 next 指针来删除目标节点。
// 删除指定位置的元素
public int remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
int removedElement;
if (index == 0) { // 删除头结点
removedElement = head.data;
head = head.next;
} else {
Node current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
removedElement = current.next.data;
current.next = current.next.next;
}
size--;
return removedElement;
}
获取操作
获取指定位置的元素，需要遍历链表找到该位置的节点。
// 获取指定位置的元素
public int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
修改操作
根据给定索引修改元素的值。
// 修改指定位置的元素
public void set(int index, int element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
current.data = element;
}
2. 双链表（Doubly Linked List）
双链表与单链表类似，不同之处在于每个节点除了有 next 指针外，还有一个 prev 指针，指向前一个节点。通过 prev 和 next 指针，可以在链表中向前或向后遍历，插入和删除操作更为灵活。
节点结构：
public class DoublyLinkedList {
private class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
private Node head; // 头节点
private Node tail; // 尾节点
private int size; // 链表大小
public DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
}
插入操作
在双链表中，插入操作既可以在头部，也可以在尾部或中间进行。需要调整前后节点的 prev 和 next 指针。
// 插入元素到指定位置
public void insert(int index, int element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node newNode = new Node(element);
if (index == 0) { // 插入到头部
if (head != null) {
newNode.next = head;
head.prev = newNode;
}
head = newNode;
if (tail == null) {
tail = newNode;
}
} else if (index == size) { // 插入到尾部
newNode.prev = tail;
if (tail != null) {
tail.next = newNode;
}
tail = newNode;
} else { // 插入到中间
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
newNode.next = current;
newNode.prev = current.prev;
if (current.prev != null) {
current.prev.next = newNode;
}
current.prev = newNode;
}
size++;
}
删除操作
删除操作与插入类似，但要修改前后节点的指针来断开目标节点。
// 删除指定位置的元素
public int remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
int removedElement;
if (index == 0) { // 删除头结点
removedElement = head.data;
head = head.next;
if (head != null) {
head.prev = null;
}
} else if (index == size - 1) { // 删除尾结点
removedElement = tail.data;
tail = tail.prev;
if (tail != null) {
tail.next = null;
}
} else { // 删除中间节点
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
removedElement = current.data;
current.prev.next = current.next;
if (current.next != null) {
current.next.prev = current.prev;
}
}
size--;
return removedElement;
}
获取操作
获取指定位置的元素，需要遍历链表找到目标节点。
// 获取指定位置的元素
public int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
3. 循环链表（Circular Linked List）
循环链表与普通链表的不同之处在于最后一个节点的 next 指针指向头节点，形成一个环。循环链表可以是单向的或双向的。
节点结构（单向循环链表）：
public class CircularLinkedList {
private class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head; // 头节点
private int size; // 链表大小
public CircularLinkedList() {
head = null;
size = 0;
}
}
插入操作
插入操作首先检查是否是空链表。如果链表为空，插入节点使其指向自己；否则，按照正常插入操作进行。
// 插入元素到指定位置
public void insert(int index, int element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node newNode = new Node(element);
if (index == 0) { // 插入到头部
if (head == null) { // 如果链表为空
head = newNode;
newNode.next = head;
} else {
Node current = head;
while (current.next != head) {
current = current.next;
}
current.next = newNode;
newNode.next = head;
head = newNode;
}
} else { // 插入到中间或尾部
Node current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
size++;
}
删除操作
删除操作与插入操作类似，只是需要更新 next 指针来断开节点的联系。
// 删除指定位置的元素
public int remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
int removedElement;
if (index == 0) { // 删除头结点
removedElement = head.data;
if (head.next == head) { // 只有一个节点
head = null;
} else {
Node current = head;
while (current.next != head) {
current = current.next;
}
current.next = head.next;
head = head.next;
}
} else { // 删除中间或尾部
Node current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
removedElement = current.next.data;
current.next = current.next.next;
}
size--;
return removedElement;
}
结论：
- 单链表：只具有
next指针，适合用来实现简单的链式结构，但插入和删除操作时间较长，尤其是在中间或尾部。 - 双链表：每个节点有
next和prev指针，支持双向遍历，插入删除操作更灵活。 - 循环链表：最后一个节点指向头节点，适合用于环形结构，但操作相对复杂。
这些操作的实现依赖于链表的特性，具体使用哪种链表结构可以根据需求来选择。