作为一名对技术充满热情的学习者，我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代，我远非专家，而是一位不断追求进步的旅行者。通过这篇博客，我想分享我在某个领域的学习经验，与大家共同探讨、共同成长。请大家以开放的心态阅读，相信你们也会在这段知识之旅中找到启示。
前言
链表在数据结构中的重要性是无法替代的，无论是动态增删节点，还是对内存的利用，实现多种复杂结构，甚至在预分配内存等方面都有很好的表现。今天我们就依次对单链表，双向链表，循环链表进行讲解。
一、单链表，双向链表，循环链表
单链表(Singly Linked List)：
单链表由一系列节点构成，每个节点包含二个部分：一个是存储数据的部分（data），另一个是指向列表中下一个节点的指针（next）。列表的开始节点称为头节点（head）。列表的最后一个节点指针不是指向下一个节点，而是指向一个空值（通常是null或None），表示链表的结束。单链表的特点是每个节点只有一个指针连接到下一个节点，所以操作只能是单向的，例如，仅能从头节点开始顺着链表遍历到尾节点。
图示：
双向链表(Doubly Linked List)：
双向链表的每个节点除了包含数据和指向下一个节点的指针之外，还包含一个指向前一个节点的指针（prev）。这意味着你可以很容易地访问链表的前驱节点和后继节点。这种额外的指针使得双向链表可以从两个方向遍历（正向和反向），并且可以更方便地执行一些操作，比如在给定节点前后插入新节点或删除当前节点。不过这种灵活性是以额外的存储空间为代价的，因为双向链表的每个节点都需要额外存储一个指针。
图示：
循环链表(Circular Linked List)：
循环链表可以是单向的也可以是双向的。它的特点在于链表的尾节点指针并不是指向空值，而是指向头节点，形成一个闭环。这意味着从链表的任何一个节点出发都可以遍历整个列表，并且可以无限制地循环下去。在单向循环链表中，你可以从任意节点开始，沿一个方向遍历整个链表。而在双向循环链表中，每个节点既有向后的指针也有向前的指针，你可以沿任一方向遍历。循环链表特别适合解决那些需要循环访问列表中的数据的问题。
图示：
二、增删改查
单链表、双向链表和循环链表的增删改查（CRUD）操作
单链表（Singly Linked List）的操作：
- 增加（Add）：有两种常见的添加操作，头部添加和尾部添加。
- 头部添加：创建新节点，将新节点的next指针指向原头部节点，然后更新头部节点为新节点。
- 尾部添加：遍历到链表的尾部节点，然后将尾部节点的next指针指向新节点，最后将新节点的next指针设置为null。
- 删除（Delete）：要删除一个节点，你需要访问该节点的前一个节点，然后将前一个节点的next指针跳过当前节点指向下一个节点。
- 如果是删除头节点，直接将头指针指向原头节点的下一个节点即可。
- 如果是尾部节点，遍历找到尾节点的前一个节点，然后将该节点的next指针设为null。
- 查找（Search）：从头节点开始，遍历每一个节点，检查其数据字段是否匹配搜索条件。
- 更新（Update）：先执行查找操作找到目标节点，然后更改该节点的数据字段。
单链表：
class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } // 增加节点（尾部插入） public void add(ListNode head, int value) { ListNode newNode = new ListNode(value); ListNode cur = head; while(cur.next != null) { cur = cur.next; } cur.next = newNode; } // 删除节点（按值删除） public void delete(ListNode head, int value) { ListNode cur = head; while(cur.next != null) { if(cur.next.val == value) { cur.next = cur.next.next; return; } cur = cur.next; } } // 修改节点（按值修改第一个匹配的节点） public void update(ListNode head, int oldValue, int newValue) { ListNode cur = head; while(cur != null) { if(cur.val == oldValue) { cur.val = newValue; return; } cur = cur.next; } } // 查询节点（按值查询） public ListNode search(ListNode head, int value) { ListNode cur = head; while(cur != null) { if(cur.val == value) { return cur; } cur = cur.next; } return null; }
双向链表（Doubly Linked List）的操作：
- 增加（Add）：和单链表类似，但是添加节点时还需要设置前一个节点的指针。
- 头部添加：与单链表类似，但还需要将原头节点的prev指针指向新节点。
- 尾部添加：找到尾节点，将新节点的prev指针指向尾节点，然后把尾节点的next指针指向新节点。
- 删除（Delete）：找到目标节点，调整其前一个节点的next指针和后一个节点的prev指针，跳过该节点。
- 查找（Search）：可以从头部开始，也可以从尾部开始，视情况而定，因为双向链表可以双向遍历。
- 更新（Update）：和单链表一样，找到节点后更新其数据字段。
双向链表：
class DoublyListNode { int val; DoublyListNode prev; DoublyListNode next; DoublyListNode(int x) { val = x; prev = null; next = null; } } // 对于双向链表，增删改查的基本操作类似于单链表，但是需要额外处理前驱节点的引用。 // 增加节点（尾部插入） // ... // 删除节点（按值删除） // ... // 修改节点（按值修改第一个匹配的节点） // ... // 查询节点（按值查询） // ...
循环链表（Circular Linked List）的操作：
- 增加（Add）：与单链表相似，但在尾部添加时最后一个步骤是将新的尾节点的next指针指向头节点，而不是null。
- 删除（Delete）：操作类似，但如果删除的是尾节点，在单向循环链表中需要找到倒数第二个节点，让它的next指针指向头节点；在双向循环链表中，头节点的prev指针也要调整。
- 查找（Search）：因为是循环的，要小心处理，通常遍历时设置一个循环的次数限制，以防无限循环。
- 更新（Update）：和单链表一样，找到节点后更新其数据字段。
循环链表：
循环链表的实现与单链表相似，但尾节点指向头节点，创建时需要特殊处理。
class CircularListNode { int val; CircularListNode next; CircularListNode(int x) { val = x; next = this; // 指向自己形成循环 } } // 对于循环链表，增删改查的基本操作也类似于单链表，但遍历时需要防止无限循环。 // 增加节点（尾部插入） // ... // 删除节点（按值删除） // ... // 修改节点（按值修改第一个匹配的节点） // ... // 查询节点（按值查询） // ...
请注意，以上代码是简化的伪代码，并不完整，例如没有考虑头节点为空的情况，实际编码时还需要做更多的边界条件处理。此外，根据具体的应用场景和需求，增删改查操作中的细节可能会有所变化。
三、实战项目
单链表实现简单的任务队列:
// 单链表的节点 class TaskNode { String taskData; // 任务的具体数据 TaskNode next; // 指向下一个任务的指针 public TaskNode(String taskData) { this.taskData = taskData; this.next = null; } } // 任务队列，基于单链表 class TaskQueue { TaskNode head; // 指向队列头部的节点 public TaskQueue() { head = null; } // 将新任务加入队尾 public void enqueue(String taskData) { TaskNode newNode = new TaskNode(taskData); if (head == null) { head = newNode; } else { TaskNode current = head; while (current.next != null) { current = current.next; } current.next = newNode; } } // 从队头取出任务 public String dequeue() { if (head == null) { return null; // 队列为空时返回null } String taskData = head.taskData; head = head.next; // 头部节点向后移动 return taskData; } // 检查队列是否为空 public boolean isEmpty() { return head == null; } } // 使用案例 public static void main(String[] args) { TaskQueue queue = new TaskQueue(); queue.enqueue("Task1"); queue.enqueue("Task2"); while (!queue.isEmpty()) { System.out.println(queue.dequeue()); } }
这个单链表队列可以用于执行任务队列的管理，比如在多线程环境下，主线程添加任务，工作线程获取任务进行处理。
双向链表实现LRU缓存:
import java.util.HashMap; import java.util.Map; // 双向链表的节点 class LRUNode { int key; int value; LRUNode prev; LRUNode next; public LRUNode(int key, int value) { this.key = key; this.value = value; } } // LRU缓存机制的实现 class LRUCache { private Map<Integer, LRUNode> cache = new HashMap<>(); private int size; private int capacity; private LRUNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; head = new LRUNode(0, 0); tail = new LRUNode(0, 0); head.next = tail; tail.prev = head; } public int get(int key) { LRUNode node = cache.get(key); if (node == null) return -1; // 把访问过的节点移动到头部 moveToHead(node); return node.value; } public void put(int key, int value) { LRUNode node = cache.get(key); if (node == null) { LRUNode newNode = new LRUNode(key, value); cache.put(key, newNode); addToHead(newNode); if (++size > capacity) { LRUNode tail = removeTail(); cache.remove(tail.key); size--; } } else { node.value = value; moveToHead(node); } } private void addToHead(LRUNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(LRUNode node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(LRUNode node) { removeNode(node); addToHead(node); } private LRUNode removeTail() { LRUNode res = tail.prev; removeNode(res); return res; } }
这个双向链表实现的LRU缓存可以在需要快速访问最近使用过的数据时使用，如在Web服务器或数据库的缓存中。
循环链表实现时间轮调度器：
// 循环链表的节点 class TimerNode { int ticks; // 触发时刻 Runnable task; // 要执行的任务 TimerNode next; // 下一个节点 public TimerNode(int ticks, Runnable task) { this.ticks = ticks; this.task = task; } } // 时间轮调度器 class TimerWheel { TimerNode wheel; // 循环链表头结点，同时也模拟轮子 int currentTick; // 当前的tick public TimerWheel() { this.wheel = new TimerNode(-1, null); // 创建一个哨兵节点 this.wheel.next = this.wheel; // 初始化为循环链表 this.currentTick = 0; } // 增加一个计时任务 public void addTimer(int ticks, Runnable task) { TimerNode newNode = new TimerNode(ticks, task); TimerNode current = this.wheel; while (current.next != this.wheel) { // 遍历找到合适的插入位置 current = current.next; } // 插入新节点到链表中 newNode.next = this.wheel; current.next = newNode; } // 调度器运行 public void run() { while (true) { TimerNode current = this.wheel.next; while (current != this.wheel) { // 遍历链表执行任务 if (current.ticks == currentTick) { current.task.run(); // 移除已经执行的节点 current.ticks = -1; // 标记为已执行 } current = current.next; } // 更新当前tick，并清理已执行任务 cleanup(); currentTick++; // 添加延迟，模拟实际情况 try { Thread.sleep(1000); // 假设1秒一个tick } catch (InterruptedException e) { e.printStackTrace(); } } } // 清除已经执行的任务 private void cleanup() { TimerNode current = this.wheel; while (current.next != this.wheel) { if (current.next.ticks == -1) { // 移除节点 current.next = current.next.next; } else { current = current.next; } } } }
这个循环链表实现的时间轮调度器可以用于周期性任务的调度，常见于定时器实现。
四、使用链表注意哪些问题
在使用链表进行实际开发时，有几个值得深思熟虑的方面：
- 选择合适的链表类型：根据需求选择单链表、双向链表或者循环链表。例如，如果你需要频繁地在两端添加或移除元素，可能双向链表（或甚至是双端队列）会更适合。
- 空间和时间效率：尽管链表在插入和删除操作上时间复杂度较低，但是如果你需要频繁地随机存取元素，链表可能不是最佳选择，数组或者动态数组（如ArrayList）在这方面表现更好。
- 内存管理：与数组相比，链表的节点通常是动态分配的，它可能引入额外的内存开销和碎片化问题。某些情况下，这会影响性能。
- 并发访问：在多线程环境下，修改链表结构需要特别小心。在没有适当同步的情况下，链表可能会很容易出现竞态条件问题。因此，需要适当的锁或并发控制机制。
- 迭代器失效：某些情况下，链表的修改（如删除正在迭代的元素）可能会导致迭代器失效。需要确保迭代操作时不会对链表结构进行修改，或是正确地处理迭代器失效的情况。
- 递归与迭代：对链表的操作，特别是在单链表中，经常会使用递归方法。然而递归可能会导致堆栈溢出。因此，根据链表的大小和特定场景，可能需要考虑迭代解决方案。
- 边界条件处理：在链表的操作中，如插入、删除等，要小心处理边界条件，包括空链表、只有一个或两个节点以及操作在头结点和尾结点时的情况。
- 资源管理：在链表不再使用时，要确保适时地释放分配的资源，避免内存泄漏。
- 选择合适的数据结构：链表不一定总是最佳选择，了解问题的具体情况，并根据实际需要和性能分析选择最合适的数据结构。
始终记得，在软件设计中，没有一成不变的规则。选择合适的数据结构和算法需要根据具体应用场景的实际需求来定。
五、思考：链表在多线程环境下如何保证并发访问的安全性？
在多线程环境下保证链表并发访问的安全性涉及到几个关键策略：
- 互斥锁（Mutex）：
使用互斥锁来同步对链表的访问。任何线程在对链表进行修改之前必须先获取锁，在修改完成后释放锁。这确保了在同一时刻只有一个线程可以修改链表。 - 读写锁（Read-Write Lock）：
如果链表的读操作比写操作频繁得多，可以使用读写锁来提高效率。读写锁允许多个读操作并行执行，但写操作会独占访问。 - 细粒度锁：
如果链表非常大且操作频繁，为了提升性能，可以使用细粒度锁或锁分段。这种方式中，链表被分成多个部分，每个部分有其自己的锁。当线程访问一个部分时，只锁定那个部分，从而允许多个线程同时操作不同的链表段。 - 无锁编程（Lock-free Programming）：
使用原子操作来管理链表的节点，这可以通过原子指针（atomic references）或其他原子操作（如CAS - Compare-And-Swap）来实现。无锁数据结构可以在多核处理器上提供良好的性能，但它们通常很难正确实现。 - 软件事务内存（Software Transactional Memory, STM）：
STM提供了一种抽象，用于通过一系列原子操作来管理对共享内存的访问。这可以用于简化并发控制，尽管它可能带来开销并非所有语言和框架都支持。 - 不变性（Immutability）：
使用不变数据结构，也就是说，数据一旦创建就不能被修改。不变性可以大大降低并发编程复杂性，因为多个线程可以安全地访问数据而无需同步。 - Copy-on-Write（写时复制）：
在写操作时复制整个链表，这样读操作可以在无锁的情况下安全进行。这适用于读多写少的场景，并且写操作代价昂贵。 - 线程局部存储（Thread-Local Storage）：
如果每个线程只需访问它自己的链表副本，可以使用线程局部存储来防止冲突。
并发访问链表的保证策略应根据应用的具体需求、预期的操作类型（读多写少或读写平衡）以及性能要求来定。软件开发者应谨慎评估并确定最适合他们特定情况的策略。
总结
链表的介绍就到这里，链表虽然简单，但是贯穿整个数据结构，我们需要了解底层原理，便于我们更好的解决实际开发中遇到的问题。
感谢大家抽出宝贵的时间来阅读博主的博客,新人博主,感谢大家关注点赞,祝大家未来的学习工作生活一帆风顺,加油!!!
