2- 链表(Linked List)
链表是一种动态数据结构，提供了灵活的方式来存储和操作数据。与数组相比，链表具有动态分配内存的优势，可以在运行时动态地添加和删除元素，无需在内存中连续存储。这种特性使得链表在添加和删除元素时更为灵活，但在访问元素时可能较慢，因为需要从头开始遍历整个链表。
- Node类
在Java中实现链表前，首先需要定义一个节点类（Node
public class Node<T> {
T data;
Node<T> next;
Node<T> prev; // 双向链表使用
public Node(T data) {
this.data = data;
this.next = null;
this.prev = null; // 双向链表初始化前驱节点
}
}
- 单向链表（Singly Linked List）
单向链表的每个节点只包含一个指向下一个节点的链接，这简化了结构，但在执行某些操作时可能需要更多的遍历。单向链表 是一种链表，其中每个节点只包含指向下一个节点的引用。它的结构简单，适合大多数基本操作。单向链表的基本字段如下：
public class SinglyLinkedList<T> {
private Node<T> head;
private Node<T> tail; // 如果有尾部指针
public SinglyLinkedList() {
this.head = null;
}
/* 方法 */
}
- 双向链表（Doubly Linked List）
双向链表的每个节点除了指向下一个节点的链接外，还包含一个指向前一个节点的链接。这增加了存储需求，但可以使得在链表中向前和向后遍历变得更加高效。双向链表与单向链表 的区别在于每个节点包含两个引用：一个指向下一个节点，另一个指向前一个节点。这种结构允许双向遍历，提高了灵活性。双向链表的基本字段如下：
public class DoublyLinkedList<T> {
private Node<T> head;
private Node<T> tail; // 如果有尾部指针
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
/* 方法 */
}
链表操作的实现细节（非官方，根据自己随便的思路写的）
- 插入头部（Inserting at Head）
在单向链表或双向链表的头部插入一个新的节点是非常高效的操作，是O(1)的时间复杂度，因为直接访问了头部指针。
public void insertAtHead(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = head;
if (head != null) {
head.prev = newNode; // 双向链表需要处理
}
head = newNode;
}
- 删除头部（Removing at Head）
删除链表头部的节点也是一个时间复杂度为O(1)的操作。
public void removeFromHead() {
if (head != null) {
head = head.next;
if (head != null) {
head.prev = null; // 双向链表需要处理
}
}
}
- 插入尾部（Inserting at Tail）
插入尾部需要遍历整个链表来找到最后一个节点，因此时间复杂度为O(n)，除非持有尾部节点的引用。
插入尾部和删除尾部的操作可以更高效地实现，如果维护了尾部指针，则插入尾部的复杂度也可以是O(1)。
public void insertAtTail(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode;
} else {
Node<T> last = head;
while (last.next != null) {
last = last.next;
}
last.next = newNode;
newNode.prev = last; // 双向链表需要处理
}
}
- 删除尾部（Removing at Tail）
在没有尾部指针的情况下，删除尾部节点效率低下（O(n)），因为需要找到倒数第二个节点。
public void removeFromTail() {
if (head == null || head.next == null) {
head = null;
} else {
Node<T> last = head;
while (last.next.next != null) {
last = last.next;
}
last.next = null; // 断开连接
if (last.next != null) {
last.next.prev = null; // 双向链表需要处理
}
}
}
在链表内部插入节点
在链表两个相邻节点之间插入节点，或在两个不相邻节点之间更换其中的 节点/子链表 的操作如下：
public void insertBetween(Node<T> prevNode, Node<T> nextNode, T data) {
if (prevNode == null || nextNode == null) {
/* 可将 prevNode.next 赋给 nextNode 或将 nextNode.prev 赋给 prevNode，并在此检查情况，更改 if 的条件，调用插入尾部或头部的方法 */
throw new IllegalArgumentException("Previous and next nodes cannot be null");
}
Node<T> newNode = new Node<>(data);
newNode.next = nextNode;
newNode.prev = prevNode; // 双向链表需要处理
prevNode.next = newNode;
nextNode.prev = newNode; // 双向链表需要处理
}
注意事项
-
如果 prevNode 在 nextNode 的后面，会有特殊的效果
-
参数检查：确保
prevNode和nextNode不为空。 -
正确链接：确保新节点的
next指向nextNode，prev指向prevNode，同时更新prevNode的next和nextNode的prev。
通过这种方式，可以在链表的两个节点之间高效地插入新的节点。
在链表内部删除节点
public void removeBetween(Node<T> prevNode, Node<T> nextNode) {
if (prevNode == null || nextNode == null || prevNode.next != nextNode) {
/* 可在此检查删除头部或尾部的情况，更改 if 的条件，调用删除尾部或头部的方法 */
throw new IllegalArgumentException("Invalid nodes provided");
}
Node<T> nodeToRemove = prevNode.next;
prevNode.next = nextNode;
nextNode.prev = prevNode; // 双向链表需要处理
// 清理待删除节点的链接
nodeToRemove.next = null;
nodeToRemove.prev = null; // 双向链表需要处理
}
删除步骤
-
如果 prevNode 在 nextNode 的后面，会有特殊的效果
-
检查节点有效性：确保
prevNode和nextNode不是null，并且prevNode.next应该指向nextNode。 -
调整链接：
prevNode.next指向nextNode，nextNode.prev指向prevNode。 -
清理删除节点：将
nodeToRemove的next和prev设为null，以帮助垃圾回收。