【数据结构】线性表 ⑤ ( 双循环链表 | 双循环链表特点 | 双循环链表插入操作处理

这篇具有很好参考价值的文章主要介绍了【数据结构】线性表 ⑤ ( 双循环链表 | 双循环链表特点 | 双循环链表插入操作处理 | 代码示例 - 使用 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 实现双循环链表 :文章来源地址https://www.toymoban.com/news/detail-647198.html

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();
    }
}