看動畫學算法之:doublyLinkedList

目錄

• 簡介
• doublyLinkedList的建構
• doublyLinkedList的操作
  • 頭部插入
  • 尾部插入
  • 插入給定的位置
  • 删除指定位置的節點

今天我們來學習一下複雜一點的LinkedList：doublyLinkedList。

和LinkedList相比，doublyLinkedList中的節點除了next指向下一個節點之外，還有一個prev之前的一個節點。是以被稱為doublyLinkedList。 doublyLinkedList是一個雙向連結清單，我們可以向前或者向後周遊list。

今天我們來學習一下doublyLinkedList的基本操作和概念。

和linkedList一樣，doublyLinkedList是由一個一個的節點構成的。而每個節點除了要存儲要儲存的資料之外，還需要存儲下一個節點和上一個節點的引用。

doublyLinkedList需要一個head節點，我們看下怎麼建構：

public class DoublyLinkedList {

    Node head; // head 節點

    //Node表示的是Linked list中的節點，包含一個data資料，上一個節點和下一個節點的引用
    class Node {
        int data;
        Node next;
        Node prev;
        //Node的構造函數
        Node(int d) {
            data = d;
        }
    }
}
           

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

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

同時需要将head.prev指向新的插入節點。

看下java代碼：

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

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

        //現有的head節點指向新的節點
        head = newNode;
    }
           

尾部插入的邏輯是：找到最後一個節點，将最後一個節點的next指向新插入的節點，并且将新插入的節點的prev指向最後一個節點。

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

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

如果要在給定的位置插入節點，我們需要先找到插入位置的前一個節點，然後将前一個節點的next指向新節點。新節點的prev指向前一個節點。

同時我們需要将新節點的next指向下一個節點，下一個節點的prev指向新的節點。

//插入在第幾個元素之後
    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;
        }
        //建立新的節點
        Node newNode = new Node(newData);
        //新節點的next指向prevNode的下一個節點
        newNode.next = prevNode.next;
        //将新節點插入在prevNode之後
        prevNode.next = newNode;
        //将新節點的prev指向prevNode
        newNode.prev = prevNode;

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

删除節點的邏輯是：找到要删除節點的前一個節點，和下一個節點。前一個節點的next指向下一個節點，下一個節點的prev指向前一個節點。

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

        // head節點
        Node temp = head;

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

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

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

        // temp->next 是要删除的節點，删除節點
        Node next = temp.next.next;
        temp.next = next;
        Node prev = temp.next.prev;
        prev.prev = prev;
    }
           

本文的代碼位址：

learn-algorithm

本文收錄于 http://www.flydean.com/algorithm-doubly-linked-list/