和LinkedList相比，doublyLinkedList中的節(jié)點除了next指向下一個節(jié)點之外，還有一個prev之前的一個節(jié)點。所以被稱為doublyLinkedList。 doublyLinkedList是一個雙向鏈表，我們可以向前或者向后遍歷list。

今天我們來學(xué)習(xí)一下doublyLinkedList的基本操作和概念。

1、doublyLinkedList的構(gòu)建

和linkedList一樣，doublyLinkedList是由一個一個的節(jié)點構(gòu)成的。而每個節(jié)點除了要存儲要保存的數(shù)據(jù)之外，還需要存儲下一個節(jié)點和上一個節(jié)點的引用。

doublyLinkedList需要一個head節(jié)點，我們看下怎么構(gòu)建：

public class DoublyLinkedList {

    Node head; // head 節(jié)點

    //Node表示的是Linked list中的節(jié)點，包含一個data數(shù)據(jù)，上一個節(jié)點和下一個節(jié)點的引用
    class Node {
        int data;
        Node next;
        Node prev;
        //Node的構(gòu)造函數(shù)
        Node(int d) {
            data = d;
        }
    }
}

2、doublyLinkedList的操作

接下來，我們看一下doublyLinkedList的一些基本操作。

2.1 頭部插入

頭部插入的邏輯是：將新插入的節(jié)點作為新的head節(jié)點，并且將newNode.next指向原來的head節(jié)點。

同時需要將head.prev指向新的插入節(jié)點。

看下java代碼：

    //插入到linkedList的頭部
    public void push(int newData) {
        //構(gòu)建要插入的節(jié)點
        Node newNode = new Node(newData);
        //新節(jié)點的next指向現(xiàn)在的head節(jié)點
        //新節(jié)點的prev指向null
        newNode.next = head;
        newNode.prev = null;

        if (head != null)
            head.prev = newNode;

        //現(xiàn)有的head節(jié)點指向新的節(jié)點
        head = newNode;
    }

2.2 尾部插入

尾部插入的邏輯是：找到最后一個節(jié)點，將最后一個節(jié)點的next指向新插入的節(jié)點，并且將新插入的節(jié)點的prev指向最后一個節(jié)點。

 //新節(jié)點插入到list最后面
    public void append(int newData) {
        //創(chuàng)建新節(jié)點
        Node newNode = new Node(newData);
        //如果list是空，則新節(jié)點作為head節(jié)點
        if (head == null) {
            newNode.prev = null;
            head = newNode;
            return;
        }

        newNode.next = null;
        //找到最后一個節(jié)點
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        //插入
        last.next = newNode;
        newNode.prev = last;
        return;
    }

2.3 插入給定的位置

如果要在給定的位置插入節(jié)點，我們需要先找到插入位置的前一個節(jié)點，然后將前一個節(jié)點的next指向新節(jié)點。新節(jié)點的prev指向前一個節(jié)點。

同時我們需要將新節(jié)點的next指向下一個節(jié)點，下一個節(jié)點的prev指向新的節(jié)點。

   //插入在第幾個元素之后
    public void insertAfter(int index, int newData) {
        Node prevNode = head;
        for (int i = 1; i < index; i++) {
            if (prevNode == null) {
                System.out.println("輸入的index有誤，請重新輸入");
                return;
            }
            prevNode = prevNode.next;
        }
        //創(chuàng)建新的節(jié)點
        Node newNode = new Node(newData);
        //新節(jié)點的next指向prevNode的下一個節(jié)點
        newNode.next = prevNode.next;
        //將新節(jié)點插入在prevNode之后
        prevNode.next = newNode;
        //將新節(jié)點的prev指向prevNode
        newNode.prev = prevNode;

        //newNode的下一個節(jié)點的prev指向newNode
        if (newNode.next != null)
            newNode.next.prev = newNode;
    }

2.4 刪除指定位置的節(jié)點

刪除節(jié)點的邏輯是：找到要刪除節(jié)點的前一個節(jié)點，和下一個節(jié)點。前一個節(jié)點的next指向下一個節(jié)點，下一個節(jié)點的prev指向前一個節(jié)點。

 //刪除特定位置的節(jié)點
    void deleteNode(int index)
    {
        // 如果是空的，直接返回
        if (head == null)
            return;

        // head節(jié)點
        Node temp = head;

        // 如果是刪除head節(jié)點
        if (index == 1)
        {
            head = temp.next;
            return;
        }

        // 找到要刪除節(jié)點的前一個節(jié)點
        for (int i=1; temp!=null && i<index-1; i++)
            temp = temp.next;

        // 如果超出范圍
        if (temp == null || temp.next == null)
            return;

        // temp->next 是要刪除的節(jié)點，刪除節(jié)點
        Node next = temp.next.next;
        temp.next = next;
        Node prev = temp.next.prev;
        prev.prev = prev;
    }

到此這篇關(guān)于看動畫學(xué)算法之Java實現(xiàn)doublyLinkedList的文章就介紹到這了,更多相關(guān)Java實現(xiàn)doublyLinkedList內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: