目錄
- 簡介
- 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/
最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！
歡迎關注我的公衆号:「程式那些事」,懂技術，更懂你！