[数据结构与算法]双向循环链表及其实现

目录

1.什么是双向循环链表？

2.双向循环链表的具体实现方法有哪些？

1.什么是双向循环链表？

? ? ? ?双向循环链表结构是两个指针，一个头指针（指向链表的头部），一个尾指针（指向链表的尾部），当前循环链表的长度size. 每个节点LinkedNode由一个前向的指针，一个后向的指针，一个当前节点的值。

2.双向循环链表的具体实现方法有哪些？

? ? ? ? int get(int index)? 获得指定的元素

? ? ? ? int?addAtHead(int val) 头结点新增元素

? ? ? ? int?addAtTail（int val）尾节点新增元素

? ? ? ? int?addAtIndex(int index,int val) 指向索引的值

? ? ? ?void?deleteAtIndex(int index) 按照索引删除元素

? ? ? void printLinkedList()? 输出链表中的元素

代码如下

//双向循环链表
class MyLinkedList {
    int size;//当前链表的长度
    // sentinel nodes as pseudo-head and pseudo-tail
    ListNode head; //头结点
    ListNode tail; //尾节点

    //双向链表的初始化
    public MyLinkedList() {
        size = 0;
        head = new ListNode(-1);
        tail = new ListNode(-1);
        head.next = tail;
        tail.prev = head;
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        ListNode node = getNode(index);
        if (node == null) {
            return -1;
        }
        return node.val;
    }

    public ListNode getNode(int index) {
        // if index is invalid
        if (index < 0 || index >= size){
            return null;
        }

        // choose the fastest way: to move from the head
        // or to move from the tail
        ListNode curr = head;
        if (index < (size - 1) / 2) {
            //在左边从头结点进行寻找
            for (int i = 0; i < index + 1; ++i) {
                curr = curr.next;
            }
        } else {
            //在右边从尾节点进行寻找
            curr = tail;
            for (int i = 0; i < size - index; ++i) {
                curr = curr.prev;
            }
        }
        return curr;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        ListNode pred = head, succ = head.next;

        ++size;
        ListNode newNode = new ListNode(val);
        newNode.prev = pred;
        newNode.next = succ;

        pred.next = newNode;
        succ.prev = newNode;
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        ListNode succ = tail, pred = tail.prev;

        ++size;
        ListNode newNode = new ListNode(val);
        newNode.prev = pred;
        newNode.next = succ;

        pred.next = newNode;
        succ.prev = newNode;
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        // If index is greater than the length,
        // the node will not be inserted.
        if (index <0) {
            addAtHead(val);
            return;
        }
        if (index >(size - 1)) {
            addAtTail(val);
            return;
        }

        //找到前驱和后继
        // find predecessor and successor of the node to be added

        ListNode node = getNode(index);

        ListNode pred = node.prev;
        ListNode succ = node;
        // insertion itself
        ++size;
        ListNode toAdd = new ListNode(val);
        toAdd.prev = pred;
        toAdd.next = succ;
        pred.next = toAdd;
        succ.prev = toAdd;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        // if the index is invalid, do nothing
        if (index < 0 || index >= size) {
            return;
        }

        // find predecessor and successor of the node to be deleted
        ListNode node = getNode(index);
        ListNode pred = node.prev;
        ListNode succ = node.next;
        // delete pred.next
        --size;
        pred.next = succ;
        succ.prev = pred;
    }

    public void printLinkedList() {
        for (int i = 0; i < size; i++) {
            System.out.println(get(i));
        }
    }

    class ListNode {
        int val;
        ListNode next;
        ListNode prev;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
//        ["MyLinkedList","addAtIndex","addAtIndex","addAtIndex","get"]
//[[],[0,10],[0,20],[1,30],[0]]
//        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addAtTail(1);
//        myLinkedList.addAtTail(2);
//        myLinkedList.addAtTail(3);
//        myLinkedList.addAtHead(4);
//        System.out.println("====================");
//        myLinkedList.printLinkedList();
//        System.out.println("====================");
//        int num = myLinkedList.get(1);
//        System.out.println(num);
//        System.out.println("====================");
//        myLinkedList.addAtIndex(1,10);
//        myLinkedList.printLinkedList();

//        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addAtIndex(0,10);
//        myLinkedList.addAtIndex(0,20);
//        myLinkedList.addAtIndex(1,30);
//        System.out.println("===================");
//        myLinkedList.printLinkedList();
//        System.out.println("===================");
//        int num = myLinkedList.get(0);
//        System.out.println(num);

//        ["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
//[[],[1],[3],[1,2],[1],[1],[1]]

        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtHead(1);
        myLinkedList.addAtTail(3);
        myLinkedList.addAtIndex(1,2);
        System.out.println("===================");
        myLinkedList.printLinkedList();
        System.out.println("===================");
        int num = myLinkedList.get(1);
        System.out.println(num);
        myLinkedList.deleteAtIndex(1);
        System.out.println("===================");
        int num2 = myLinkedList.get(1);
        System.out.println(num2);
    }
}

我是厚积薄发，欢迎大家点赞，欢迎大家留言。