文章目录

• 一、双循环链表
• 二、双循环链表特点
• 三、双循环链表插入操作处理
• 四、代码示例 - 使用 Java 实现 双循环链表

一、双循环链表

" 双循环链表 " 是 在 单循环链表 的基础上 , 在每个 节点 中 , 新增一个 指针 , 指向 该节点 的 前驱节点 ;

双向循环链表 每个 节点 都包含 数据 和 两个指针 ,

一个指针指向前一个节点 , 一个指针指向后一个节点 ;

与 单循环链表相比 , 双循环链表 可以在两个方向上遍历整个链表 , 单循环链表 只能在一个方向上遍历链表 ;

二、双循环链表特点

双循环链表 特点 :

• 闭环结构 :
  • 第一个节点 的 前驱指针 指向最后一个节点 ;
  • 最后一个节点 的 后继指针 指向第一个节点 ;
• 遍历方向 : 双循环链表 可以从头部节点 向前遍历 , 也可以向后遍历 ;
• 高效增删节点 : 双循环链表 中 , 可以在 任意位置 增删节点 , 双循环链表中可以双向遍历 , 增删节点 效率更高 ;

LRU 缓存算法中 , 一般使用 双循环链表 数据结构 ;

三、双循环链表插入操作处理

双循环链表 中 , 需要对 插入 / 删除 / 遍历 操作 进行特殊处理 , 因为需要调节 前驱指针 和 后继指针 两个指针 ;

如 : 双循环链表 中 , 如果要插入元素 , 将 c 节点 插入到 a 节点 和 b 节点 之间 ,

当前的状态是 a 的后继指针 指向 b , b 的前驱指针指向 a ;

如果要实现插入 c 元素 , 则需要

• 将 a 的 后继指针 指向 c ,
• 将 c 的 前驱指针 指向 a ,
• 将 c 的 后继指针 指向 b ,
• 将 b 的 前驱指针 指向 c ;

插入节点操作 需要执行四个步骤 :

• ① 将 c 的 前驱指针 指向 a
• ② 将 a 的 后继指针 指向 c
• ③ 将 c 的 后继指针 指向 b
• ④ 将 b 的 前驱指针 指向 c
  

四、代码示例 - 使用 Java 实现 双循环链表

Node类来表示双向循环链表的节点 , 每个节点包含如下要素 :

• 数据项 data ;
• 指向 前一个节点 的 前驱指针 prev ;
• 指向 下一个节点 的 后继指针 next ;

使用 Java 实现 双循环链表 :

public class Node {public int data;public Node prev;public Node next;public Node(int data) {this.data = data;this.prev = null;this.next = null;}
}public class DoublyCircularLinkedList {private Node head;public DoublyCircularLinkedList() {this.head = null;}public void append(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;head.next = head;head.prev = head;} else {Node lastNode = head.prev;lastNode.next = newNode;newNode.prev = lastNode;newNode.next = head;head.prev = newNode;}}public void printList() {if (head == null) {System.out.println("Doubly Circular Linked List is empty.");return;}Node current = head;do {System.out.print(current.data + " ");current = current.next;} while (current != head);}public static void main(String[] args) {DoublyCircularLinkedList dcll = new DoublyCircularLinkedList();dcll.append(1);dcll.append(2);dcll.append(3);dcll.append(4);dcll.printList();}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！