链表（Linked List）是一种在计算机科学中广泛使用的基础数据结构。与数组不同，链表中的元素不是连续存储的，而是通过指针连接在一起。每个元素包含两部分：数据和指向下一个元素的指针（在双向链表中还有指向上一个元素的指针）。链表允许有效地在序列中任何位置插入和删除元素，不需要移动其他元素，这是它的主要优势之一。
链表的基本类型
链表的基本类型包括单向链表、双向链表和循环链表。
-
单向链表（Singly Linked List）：
- 每个元素包含数据和指向下一个元素的指针。
- 最后一个元素的指针指向NULL，表示链表的结束。
- 只能从头部开始遍历链表。
-
双向链表（Doubly Linked List）：
- 每个元素包含数据、指向下一个元素的指针，以及指向上一个元素的指针。
- 第一个元素的“上一个”指针和最后一个元素的“下一个”指针指向NULL。
- 可以从头部或尾部开始遍历链表，也可以向前或向后遍历。
-
循环链表（Circular Linked List）：
- 循环链表既可以是单向的，也可以是双向的：
- 单向循环链表：在这种链表中，每个节点只有指向下一个节点的指针，最后一个节点指向头节点，形成一个环。
- 双向循环链表：在这种链表中，每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点。链表的头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，形成了一个双向的环。
- 可以从任意元素开始，沿一个方向无限遍历链表。
- 循环链表既可以是单向的，也可以是双向的：
链表操作的几个基本例子：
-
插入元素： 在链表中插入元素涉及调整指针，以将新元素放入链表中的特定位置。例如，在单向链表中，在一个给定的元素之后插入新元素需要将新元素的指针指向当前元素的下一个元素，然后将当前元素的指针指向新元素。
-
删除元素： 删除链表中的元素涉及调整指针，以从链表中移除元素。在单向链表中，这意味着将前一个元素的指针指向被删除元素的下一个元素。
-
查找元素： 查找链表中的元素通常需要从头开始遍历，直到找到所需的元素或达到链表的末尾。
-
遍历链表： 遍历链表意味着从头（或尾）开始，逐个访问链表的每个元素，直到达到链表的末尾（或开始）。
链表相对于数组的优点是插入和删除操作不需要移动其他元素，可以实现更快的操作。然而，相对于数组，链表的缺点是它不支持随机访问，这意味着访问任何特定元素都需要从头开始遍历链表。此外，由于每个元素都需要存储指针，链表通常也需要更多的内存空间。
下面是用Java代码简单展示单向链表、双向链表和循环链表的基本数据结构。这些示例仅展示了每种链表的基本框架，并未包含完整的功能实现（例如添加、删除或查找元素的方法）。
链表的基本示例
单向链表
public class SingleLinkedList<E> {
Node<E> head;
/**
* 插入节点到链表末尾
*/
public void insert(E data) {
Node<E> newNode = new Node<>(data);
if (head == null) {
head = newNode;
} else {
Node<E> current = head;
// 遍历到末尾
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
/**
* 删除指定值的节点
*/
public void delete(E data) {
if (head == null) return;
if (head.item.equals(data)) {
head = head.next;
return;
}
Node<E> current = head;
while (current.next != null) {
if (current.next.item.equals(data)) {
current.next = current.next.next; // 删除节点
return;
}
current = current.next;
}
}
/**
* 查找指定值的节点
*/
public Node<E> find(E data) {
Node<E> current = head;
while (current != null) {
if (current.item.equals(data)) {
return current;
}
current = current.next;
}
return null;
}
// 遍历链表
public void traverse() {
Node<E> current = head;
while (current != null) {
System.out.print(current.item + " ");
current = current.next;
}
System.out.println();
}
private static class Node<E> {
E item;
Node<E> next;
public Node(E item) {
this.item = item;
next = null;
}
}
}
双向链表
public class DoublyLinkedList<E> {
Node<E> head, tail;
// 插入节点到末尾
public void insert(E data) {
Node<E> newNode = new Node<>(data);
if (head == null) {
head = tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
// 删除指定值的节点
public void delete(E data) {
Node<E> current = head;
while (current != null) {
if (current.data.equals(data)) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current. prev;
} else {
tail = current.prev;
}
return;
}
current = current.next;
}
}
/**
* 查找指定值的节点
* */
public Node<E> find(E data) {
Node<E> current = head;
while(current != null) {
if (current.data.equals(data)) {
return current;
}
current = current.next;
}
return null;
}
/**
* 遍历链表
* */
public void traverse() {
Node<E> current = head;
while(current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
private static class Node<E> {
E data;
Node<E> prev, next;
public Node(E data) {
this.data = data;
prev = null;
next = null;
}
}
}
循环链表
循环链表可以是单向的也可以是双向的。这里为了简洁起见，我将展示一个单向循环链表的基本结构。
/**
* 循环链表可以是双向的，也可以是单向的。这里展示的是单向循环链表
* */
public class CircularLinkedList<E> {
Node<E> head;
/**
* 插入节点
* */
public void insert(E data) {
Node<E> newNode = new Node<>(data);
if (head == null) {
head = newNode;
} else {
Node<E> current = head;
while(current.next != head) {
current = current.next;
}
current.next = newNode;
}
newNode.next = head;
}
/**
* 删除指定值的节点
* */
public void delete(E data) {
if (head == null) return;
// 只有一个节点，且是待删节点
if (head.data.equals(data) && head.next == head) {
head = null;
return;
}
Node<E> current = head;
Node<E> prev = null;
do {
if (current.data.equals(data)) {
if (prev != null) {
// 删除中间的节点
prev.next = current.next;
} else {
// 删除头部节点，需要找到尾节点
while (current.next != head) {
current = current.next;
}
// 设置新的头部节点
head = head.next;
current.next = head;
}
return;
}
prev = current;
current = current.next;
} while (current.next != head);
}
// 删除指定值的节点
public Node<E> find(E data) {
if (head == null) return null;
Node<E> current = head;
do {
if (current.data.equals(data)) {
return current;
}
current = current.next;
} while (current.next != head);
return null;
}
// 遍历链表
public void traverse() {
if (head == null) return;
Node<E> current = head;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current.next != head);
}
private static class Node<E> {
E data;
Node<E> next;
public Node(E data) {
this.data = data;
next = this; // 初始化指向自己
}
}
}
请注意，这些示例仅展示了每种链表类型的基本结构。在实际使用中，链表通常会包含更多方法，例如用于添加、删除和搜索节点的方法，以及可能的额外功能，比如求链表长度或者翻转链表等。每种链表的具体实现会根据实际的应用需求有所不同。