淄博网络,长沙百度推广优化排名,下载应用商店app,5118关键词挖掘工具环形链表 文章目录 环形链表1.结构图2.具体实现2.1.环形链表结构2.2.头部添加数据2.2.1.具体实现2.2.2.测试添加数据 2.3.尾部添加数据2.3.1.具体实现2.3.2.添加测试数据 2.4.删除头部数据2.4.1.具体实现2.4.2.测试删除数据 2.5.删除尾部数据2.5.1.具体实现2.5.2.测试删除数据 …环形链表 文章目录 环形链表1.结构图2.具体实现2.1.环形链表结构2.2.头部添加数据2.2.1.具体实现2.2.2.测试添加数据 2.3.尾部添加数据2.3.1.具体实现2.3.2.添加测试数据 2.4.删除头部数据2.4.1.具体实现2.4.2.测试删除数据 2.5.删除尾部数据2.5.1.具体实现2.5.2.测试删除数据 2.6.根据内容删除节点2.6.1.具体实现 2.7.遍历环形链表2.7.1.迭代器遍历2.7.2.使用递归进行遍历 2.7.3.测试 3.具体应用场景3.1.优点3.2.缺点3.3.应用场景 1.结构图
双向环形链表带哨兵这个时候的哨兵可以当头也可做尾 带哨兵双向循环链表结构稍微复杂实现简单。一般用来单独存储数据实际中使用的链表数据结构都是带头双向链表。另外这个结构虽然结构复杂但是使用代码实现后会发现结构会带来很多优势。 双向环形链表是一种链式数据结构其每个节点包含指向前一个节点和后一个节点的指针形成了一个闭环。这意味着链表的尾部节点指向头部节点而头部节点指向尾部节点形成了一个环状的结构。 带哨兵的双向环形链表在头部和尾部都有一个特殊的哨兵节点这个哨兵节点不存储任何数据仅用于简化链表的操作。哨兵节点使得链表中始终存在一个不变的头部和尾部即使链表为空也如此。具体而言 头部哨兵节点 位于链表的头部它的前驱节点指向链表的尾部节点而它的后继节点指向链表的第一个真实节点。头部哨兵节点使得在头部执行操作时变得更加简单不需要特殊处理链表为空的情况也不需要区分头部和尾部的操作。尾部哨兵节点 位于链表的尾部它的后继节点指向链表的头部节点而它的前驱节点指向链表的最后一个真实节点。尾部哨兵节点同样简化了尾部操作使得在尾部进行插入、删除等操作更加方便。
带哨兵的双向环形链表在实现时通常会带来一些优势
简化操作 哨兵节点的存在使得对链表头部和尾部的操作变得更加统一和简化。不需要特别处理头部或尾部为空的情况使得代码更加清晰和简洁。增强鲁棒性 哨兵节点可以避免出现空指针异常因为链表中始终存在一个不变的头部和尾部。这增强了代码的鲁棒性和可靠性。逻辑统一 哨兵节点的存在使得链表的逻辑更加统一不需要在特殊情况下单独处理头部或尾部节点使得代码更加一致性和可读性。 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.添加测试数据 TestDisplayName(测试-双向环形链表-尾部添加元素)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指向head2.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 IterableInteger 接口 重写/*** 通过实现迭代器 进行循环遍历*/
Override
public IteratorInteger iterator() {return new IteratorInteger() {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(ConsumerInteger before,ConsumerInteger after){recursion(sentinel.next,before,after);
}/*** 递归进行遍历* param node 下一个节点* param before 遍历前执行的方法* param after 遍历后执行的方法* deprecated 递归遍历,不建议使用,递归深度过大会导致栈溢出。建议使用迭代器,或者循环遍历,或者使用尾递归,或者使用栈* see #loop(Consumer, Consumer)*/
public void recursion(Node node, ConsumerInteger before, ConsumerInteger after){// 表示链表没有节点了那么就退出(注意 环形链表的 末尾 不是null 而是头节点)if (node sentinel){return;}// 反转位置就是逆序了before.accept(node.value);recursion(node.next, before, after);after.accept(node.value);
}2.7.3.测试 TestDisplayName(测试-双向环形链表-遍历)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.优点
循环遍历简便 由于双向环形链表形成了一个闭环因此在需要循环遍历链表时可以更加简便地实现不需要额外的指针变量来记录链表的尾部或头部。高效的插入和删除操作 双向环形链表的节点结构允许在任意位置进行节点的插入和删除操作并且这些操作通常比较高效尤其是在头部和尾部进行操作时。适用于循环结构数据 对于需要处理循环结构的数据或需要实现环形队列等特定功能的场景双向环形链表是一种很自然的数据结构选择。
3.2.缺点
强引用导致的内存泄漏 如果双向环形链表中的节点持有对外部对象的强引用并且这些外部对象的生命周期比链表更长那么即使链表中的节点不再被使用这些节点仍然被链表中的引用所持有从而无法被垃圾回收器回收导致内存泄漏。未正确处理节点的引用关系 在双向环形链表中节点之间相互引用如果在节点删除或者替换的过程中未正确地处理节点之间的引用关系可能会导致链表中的节点无法被回收从而引发内存泄漏。长期持有迭代器 如果在遍历双向环形链表的过程中长期持有迭代器对象而没有正确地释放迭代器对象可能会导致链表中的节点无法被回收造成内存泄漏。容易产生死循环 由于环形链表的特性编写循环遍历的代码时需要特别小心如果没有正确地处理循环结束的条件可能会产生死循环导致程序崩溃或陷入无限循环。实现复杂度较高 相比于普通的单向链表双向环形链表的实现复杂度较高需要更多的代码来维护节点之间的引用关系尤其是在节点的插入和删除操作时需要考虑更多的边界条件。
3.3.应用场景
LRU Cache最近最少使用缓存 在LRU缓存中双向环形链表可以用于维护最近使用的数据项的顺序。每次访问缓存中的数据时可以将该数据项移到链表的头部而最少使用的数据项则会被移动到链表的尾部当缓存空间不足时可以删除链表尾部的数据项。双向环形链表使得在链表头尾进行插入和删除操作更加高效。循环队列 在某些情况下需要实现循环队列以存储和处理数据比如在生产者-消费者模型中。双向环形链表可以用作循环队列的基础数据结构使得在队列头尾进行数据插入和删除操作更加高效。哈希表的冲突解决 在哈希表中如果多个键散列到相同的槽位上就会发生冲突。双向环形链表可以用作哈希表中槽位的链表用于解决冲突实现链地址法Separate Chaining的哈希表。
