从零开始学习数据结构—【链表】—【探索环形链的设计之美】

环形链表

1.结构图

双向环形链表带哨兵，这个时候的哨兵，可以当头，也可做尾

带哨兵双向循环链表：结构稍微复杂，实现简单。一般用来单独存储数据，实际中使用的链表数据结构都是带头双向链表。另外，这个结构虽然结构复杂，但是使用代码实现后会发现结构会带来很多优势。

双向环形链表是一种链式数据结构，其每个节点包含指向前一个节点和后一个节点的指针，形成了一个闭环。这意味着链表的尾部节点指向头部节点，而头部节点指向尾部节点，形成了一个环状的结构。

带哨兵的双向环形链表在头部和尾部都有一个特殊的哨兵节点，这个哨兵节点不存储任何数据，仅用于简化链表的操作。哨兵节点使得链表中始终存在一个不变的头部和尾部，即使链表为空也如此。具体而言：

1. 头部哨兵节点： 位于链表的头部，它的前驱节点指向链表的尾部节点，而它的后继节点指向链表的第一个真实节点。头部哨兵节点使得在头部执行操作时变得更加简单，不需要特殊处理链表为空的情况，也不需要区分头部和尾部的操作。
2. 尾部哨兵节点： 位于链表的尾部，它的后继节点指向链表的头部节点，而它的前驱节点指向链表的最后一个真实节点。尾部哨兵节点同样简化了尾部操作，使得在尾部进行插入、删除等操作更加方便。

带哨兵的双向环形链表在实现时通常会带来一些优势：

• 简化操作： 哨兵节点的存在使得对链表头部和尾部的操作变得更加统一和简化。不需要特别处理头部或尾部为空的情况，使得代码更加清晰和简洁。
• 增强鲁棒性： 哨兵节点可以避免出现空指针异常，因为链表中始终存在一个不变的头部和尾部。这增强了代码的鲁棒性和可靠性。
• 逻辑统一： 哨兵节点的存在使得链表的逻辑更加统一，不需要在特殊情况下单独处理头部或尾部节点，使得代码更加一致性和可读性。

2.具体实现

2.1.环形链表结构

public class DoubleLinkedListSentinel {private static final Logger logger = LoggerFactory.getLogger(MethodHandles.lookup().lookupClass());public DoubleLinkedListSentinel(){// 初始化时 环形连链表创建指向自身sentinel.next = sentinel;sentinel.prev = sentinel;}/*** 创建哨兵*/private Node sentinel = new Node(null,-1,null);private static class Node{Node prev;     // 头指针Integer value; // 值Node next;     // 尾指针public Node(Node prev, Integer value, Node next) {this.prev = prev;this.value = value;this.next = next;}}/*** 重写toString 用于Json输出* @return*/@Overridepublic String toString() {StringBuffer sb = new StringBuffer();Node p = sentinel.next;while (p != sentinel){sb.append(","+p.value);p = p.next;}//  StringUtils.strip(sb.toString() 去除首位固定字符return "Node[ " + StringUtils.strip(sb.toString(), ",") +" ]";}
}

2.2.头部添加数据

# 思路找到哨兵，找到哨兵的下一个节点，创建新的对象（指定新节点的前后节点），将哨兵next指向新创建的节点，将哨兵的下一个节点指向新加的节点

2.2.1.具体实现

	/*** 在头部添加值* @param value 待添加的元素*/public void addFirst(int value){// 找到哨兵Node head = sentinel;// 找到哨兵的下一个节点Node next = sentinel.next;// 创建新的对象Node addNode = new Node(head, value, next);// 将哨兵next指向新创建的节点head.next = addNode;//将哨兵的下一个节点的头节点指向新加的节点next.prev = addNode;}

2.2.2.测试添加数据

@Test
@DisplayName("测试双向环形链表")
public void test(){DoubleLinkedListSentinel node = new DoubleLinkedListSentinel();logger.error("add after node :{}",node);node.addFirst(1);node.addFirst(2);node.addFirst(3);logger.error("add after node :{}",node);
}

2.3.尾部添加数据

# 思路找到最后一个节点，找到头节点，创建新的节点（指明前后节点），将最后一个节点的next指向新创建的节点，将头节点的prev指向新创建的节点

2.3.1.具体实现

/*** 向链表的最后一个节点添元素* @param value 需要添加元素的值*/
public void addLast(int value){// 找到最后一个节点Node next = sentinel.prev;// 找到头节点Node head = sentinel;// 创建新的节点Node node = new Node(next, value, head);// 将最后一个节点的next指向新创建的节点next.next = node;// 将头节点的prev指向新创建的节点head.prev = node;
}

2.3.2.添加测试数据

	@Test@DisplayName("测试-双向环形链表-尾部添加元素")public void tes2(){DoubleLinkedListSentinel node = new DoubleLinkedListSentinel();node.addLast(1);node.addLast(2);node.addLast(3);node.addLast(4);logger.error("linked list is: :{}",node);}

2.4.删除头部数据

# 思路 找到需要删除的节点，找到上一个节点，找到删除节点的下一个节点，将头节点的next指向删除节点的下一个节点，将删除节点的prev指向head

2.4.1.具体实现

/*** 删除第一个节点*/
public void removedFirst(){// 先找到需要删除的节点Node deleteNode = sentinel.next;// 如果删除的节点等于哨兵 那么不能删除if (deleteNode == sentinel){throw new IllegalArgumentException("delete node is null!");}// 找到上一个节点Node head = sentinel;// 找到删除节点的下一个节点Node next = deleteNode.next;// 将头节点的next指向删除节点的下一个节点head.next = next;// 将删除节点的prev指向headnext.prev = head;
}

2.4.2.测试删除数据

@Test
@DisplayName("测试-双向环形链表-删除第一个数据")
public void tes2(){DoubleLinkedListSentinel node = new DoubleLinkedListSentinel();node.addLast(1);node.addLast(2);node.addLast(3);node.addLast(4);logger.error("remove first node :{},size :{}",node,node.size());logger.error("------------------ remove ----------------");node.removedFirst();logger.error("remove first node :{},size :{}",node,node.size());node.removedFirst();logger.error("remove first node :{},size :{}",node,node.size());node.removedFirst();logger.error("remove first node :{},size :{}",node,node.size());node.removedFirst();logger.error("remove first node :{},size :{}",node,node.size());node.removedFirst();
}

2.5.删除尾部数据

# 思路找到最后一个节点，找到删除节点的上一个节点，找到删除节点的下一个节点，将删除节点的上一个节点 next指向头部，将哨兵执行最后一个节点

2.5.1.具体实现

/*** 删除最后一个节点*/public void removeLast(){// 找到最后一个节点Node deleteNode = sentinel.prev;// 如果删除的节点等于哨兵 那么不能删除if (deleteNode == sentinel){throw new IllegalArgumentException("delete node is null!");}// 找到删除节点的上一个节点Node head = deleteNode.prev;// 将删除节点的下一个节点Node next = sentinel;// 将删除的节点的上一个节点 next指向头部head.next = next;// 将哨兵执行最后一个节点next.prev = head;}

2.5.2.测试删除数据

@Test
@DisplayName("测试-双向环形链表-删除最后一个数据")
public void tes2(){DoubleLinkedListSentinel node = new DoubleLinkedListSentinel();node.addLast(1);node.addLast(2);node.addLast(3);node.addLast(4);logger.error("remove last node :{},size :{}",node,node.size());logger.error("------------------ remove ----------------");node.removeLast();logger.error("remove last node :{},size :{}",node,node.size());node.removeLast();logger.error("remove last node :{},size :{}",node,node.size());node.removeLast();logger.error("remove last node :{},size :{}",node,node.size());node.removeLast();logger.error("remove last node :{},size :{}",node,node.size());node.removeLast();
}

2.6.根据内容删除节点

# 思路找到需要删除的节点，找到删除节点的上一个节点，找到删除节点的下一个节点，将删除节点的上一个节点 next指向删除节点的下一个节点，将删除节点的下一个节点 prev指向删除节点的上一个节点

2.6.1.具体实现

@Test
@DisplayName("测试-双向环形链表-根据内容删除元素")
public void tes2(){DoubleLinkedListSentinel node = new DoubleLinkedListSentinel();node.addLast(1);node.addLast(2);node.addLast(3);node.addLast(4);int r1 = RandomUtils.nextInt(1, 5);int r2 = RandomUtils.nextInt(1, 10);logger.error("linked list :{}",node);int i = node.removeByIndex(r1);if (i == -1){logger.error("未找到需要删除的元素,{}",r1);}else {logger.error("删除成功,{}",r1);}int j = node.removeByIndex(r2);if (j == -1){logger.error("未找到需要删除的元素,{}",r2);}else {logger.error("删除成功,{}",r2);}logger.error("find linked list :{}",node);
}

2.7.遍历环形链表

2.7.1.迭代器遍历

// 实现 public class DoubleLinkedListSentinel implements Iterable<Integer> 接口  重写/*** 通过实现迭代器 进行循环遍历*/
@Override
public Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = sentinel.next;@Overridepublic boolean hasNext() {return p != sentinel;}@Overridepublic Integer next() {Integer value = p.value;p = p.next;return value;}};
}

2.7.2.使用递归进行遍历

/*** 递归遍历(递归遍历)*/
public void loop(Consumer<Integer> before,Consumer<Integer> after){recursion(sentinel.next,before,after);
}/*** 递归进行遍历* @param node   下一个节点* @param before 遍历前执行的方法* @param after  遍历后执行的方法* @deprecated  递归遍历,不建议使用,递归深度过大会导致栈溢出。建议使用迭代器,或者循环遍历,或者使用尾递归,或者使用栈* @see #loop(Consumer, Consumer)*/
public void recursion(Node node, Consumer<Integer> before, Consumer<Integer> after){// 表示链表没有节点了，那么就退出(注意 环形链表的 末尾 不是null 而是头节点)if (node == sentinel){return;}// 反转位置就是逆序了before.accept(node.value);recursion(node.next, before, after);after.accept(node.value);
}

2.7.3.测试

	@Test@DisplayName("测试-双向环形链表-遍历")public void tes3(){DoubleLinkedListSentinel node = new DoubleLinkedListSentinel();node.addLast(1);node.addLast(2);node.addLast(3);node.addLast(4);logger.error("=========== 迭代器遍历链表 ===========");for (Integer i : node) {logger.error("迭代器遍历链表 :{}",i);}logger.error("=========== 递归遍历链表 ===========");node.loop(it->{logger.error("从头部开始遍历 :{}",it);},it ->{logger.error("从尾部开始遍历 :{}",it);});}

3.具体应用场景

3.1.优点

1. 循环遍历简便： 由于双向环形链表形成了一个闭环，因此在需要循环遍历链表时，可以更加简便地实现，不需要额外的指针变量来记录链表的尾部或头部。
2. 高效的插入和删除操作： 双向环形链表的节点结构允许在任意位置进行节点的插入和删除操作，并且这些操作通常比较高效，尤其是在头部和尾部进行操作时。
3. 适用于循环结构数据： 对于需要处理循环结构的数据或需要实现环形队列等特定功能的场景，双向环形链表是一种很自然的数据结构选择。

3.2.缺点

1. 强引用导致的内存泄漏： 如果双向环形链表中的节点持有对外部对象的强引用，并且这些外部对象的生命周期比链表更长，那么即使链表中的节点不再被使用，这些节点仍然被链表中的引用所持有，从而无法被垃圾回收器回收，导致内存泄漏。
2. 未正确处理节点的引用关系： 在双向环形链表中，节点之间相互引用，如果在节点删除或者替换的过程中未正确地处理节点之间的引用关系，可能会导致链表中的节点无法被回收，从而引发内存泄漏。
3. 长期持有迭代器： 如果在遍历双向环形链表的过程中长期持有迭代器对象，而没有正确地释放迭代器对象，可能会导致链表中的节点无法被回收，造成内存泄漏。
4. 容易产生死循环： 由于环形链表的特性，编写循环遍历的代码时需要特别小心，如果没有正确地处理循环结束的条件，可能会产生死循环，导致程序崩溃或陷入无限循环。
5. 实现复杂度较高： 相比于普通的单向链表，双向环形链表的实现复杂度较高，需要更多的代码来维护节点之间的引用关系，尤其是在节点的插入和删除操作时需要考虑更多的边界条件。

3.3.应用场景

1. LRU Cache（最近最少使用缓存）： 在LRU缓存中，双向环形链表可以用于维护最近使用的数据项的顺序。每次访问缓存中的数据时，可以将该数据项移到链表的头部，而最少使用的数据项则会被移动到链表的尾部，当缓存空间不足时，可以删除链表尾部的数据项。双向环形链表使得在链表头尾进行插入和删除操作更加高效。
2. 循环队列： 在某些情况下，需要实现循环队列以存储和处理数据，比如在生产者-消费者模型中。双向环形链表可以用作循环队列的基础数据结构，使得在队列头尾进行数据插入和删除操作更加高效。
3. 哈希表的冲突解决： 在哈希表中，如果多个键散列到相同的槽位上，就会发生冲突。双向环形链表可以用作哈希表中槽位的链表，用于解决冲突，实现链地址法（Separate Chaining）的哈希表。