🔗用Python 實現 Doubly Linked List 雙向鏈結串列(鍊表)

Emma Frances Logan null on Unsplash

在資料結構與演算法裡，

最簡單的線性資料結構除了array之外就是linked list鏈結串列了。

Linked list又有分為單向Singly linked list 和雙向Doubly linked list

在之前的教學中，已經學會了單向鏈結串列Singly linked list。

接著，我們將在今天學會更進階的雙向鏈結串列Doubly linked list。

定義

每個節點Node只有三個欄位

data: 儲存這個節點的資料

next: 指向下一個節點的reference (在C/C++ 就是指標pointer) 對應到綠色的箭頭

prev: 指向前一個節點的reference (在C/C++ 就是指標pointer) 對應到紫色的箭頭

而雙向連結串列就是由數個節點所構成，形成由頭部逐一串接到尾巴的串列。

並且支援雙向拜訪，可以從頭拜訪到尾，也可以從尾巴拜訪到頭部。

優點

1.在頭部、尾巴、或者已知節點的新增、刪除、修改都是O(1) 常數時間。

2.可以根據需求動態延伸或縮短，有效利用記憶體空間。

3.支援雙向拜訪，可以從頭拜訪到尾，也可以從尾巴拜訪到頭部。

缺點

1.不支援random acess，不支援Linkedlist[ index ] 這種操作。

2.如果要搜尋或者訪問某個元素，一定要從頭部或者尾巴開始拜訪(或搜尋)整個串列。

run-time成本相當昂貴，需要O(n)線性時間。

節點Node的Python實作

class Node:

  def __init__(self, data):

    # 儲存節點的資料
    self.data = data

    # 指向下一個節點，初始化為空 None
    self.next = None

    # 指向前一個節點，初始化為空 None
    self.prev = None

Doubly Linked List的class定義 與 建構子(初始化函式)

class LinkedList:

  def __init__(self): 

    # 頭部節點初始化為空
    self.head = None

    # 尾巴節點初始化為空
    self.tail = None  

    # 串列長度初始化為0
    self.size = 0

Doubly Linked List常見的操作

1.在頭部插入新節點

實作上的細節要留意，串列是空的還是已經有節點存在了。

如果是空的，直接加入即可。

如果已經有節點存在了，插入新節點之後，記得更新head頭部位置。

時間複雜度: O(1) 常數時間

  def insertAtHead(self,data):

    new_node = Node(data)

    self.size += 1

    # If the list is empty
    if self.tail is None:

      self.head = new_node
      self.tail = new_node

    else:
      # Update linkage
      new_node.next = self.head
      self.head.prev = new_node

      self.head = new_node

    return

2.在尾巴插入新節點

實作上的細節要留意，串列是空的還是已經有節點存在了。

如果是空的，直接加入即可。

如果已經有節點存在了，插入新節點之後，記得更新tail尾巴位置。

時間複雜度: O(1) 常數時間

  def insertAtTail(self, data):

    new_node = Node(data)

    self.size += 1

    # If the list is empty
    if self.head is None:

      self.head = new_node
      self.tail = new_node

    else:
      # Update linkage
      self.tail.next = new_node
      new_node.prev = self.tail

      self.tail = new_node

    return

3.在頭部刪除節點

實作上的細節要留意，串列是空的還是已經有節點存在了。

如果是空的，直接不做事return即可。

如果已經有節點存在了，刪除舊節點之後，記得更新head頭部位置。

時間複雜度: O(1) 常數時間

  def removeAtHead(self):

    if self.head is None:

      return

    else:

      self.size -= 1

      oldHead = self.head


      # Update linkage
      if self.head == self.tail:

        self.tail = None
        self.head = None

      else:

        self.head = self.head.next
     

      # Break linkage
      oldHead.next = None

      if self.head:
        self.head.prev = None

      return oldHead

4.在尾巴刪除節點

實作上的細節要留意，串列是空的還是已經有節點存在了。

如果是空的，直接不做事return即可。

如果已經有節點存在了，刪除舊節點之後，記得更新tail尾巴位置。

時間複雜度: O(1) 常數時間

  def removeAtTail(self):
  
    if self.tail is None:
      return
      
    else:
      self.size -= 1
      oldTail = self.tail

      # Update linkage
      if self.tail == self.head:
        self.tail = None
        self.head = None
        
      else:
        self.tail = self.tail.prev

      # Break linkage
      oldTail.prev = None

      if self.tail:
        self.tail.next = None

      return oldTail

5.順向拜訪整個串列

從頭拜訪整個串列，直到尾巴。

最後順便輸出整個串列長度。

時間複雜度: O(n) 線性時間

  def traverse(self):

    print("Forward traversal")
    cur = self.head

    while cur:
      print(cur.data, end=' -> ')
      cur = cur.next
    print("None")

    print(f"Size of singly linked list: {self.size} \n", )
    return

6.反向拜訪整個串列

從尾巴反向拜訪整個串列，直到頭部。

最後順便輸出整個串列長度。

時間複雜度: O(n) 線性時間

  def backward_traverse(self):

    print("Backward traversal")
    cur = self.tail

    while cur:
      print(cur.data, end=' -> ')
      cur = cur.prev
    print("None")

    print(f"Size of singly linked list: {self.size} \n", )
    return

7.查詢某筆資料是否存在

從頭拜訪整個串列，查詢某筆資料是否存在。

如果存在，返回該節點。

如果不存在，返回None(空)。

時間複雜度: O(n) 線性時間

  def search(self, target):
  
    cur = self.head
    while cur:
      if cur.data == target:
        return cur

      cur = cur.next

    return None

8.刪除已知節點的下一個節點

實作上的細節要留意。

記得把串列長度減一。

並且串接後面剩下的節點。

時間複雜度: O(1) 常數時間

  def removeAfter(self, node):

    self.size -= 1

    removed = node.next
    the_one_after_removal = node.next.next if node.next else None

    # Update linkage
    if the_one_after_removal:
      the_one_after_removal.prev = node

    node.next = the_one_after_removal
    
    # Break linkage
    if removed:
      removed.next = None
      removed.prev = None

    return removed

9.在已知節點的後面新增一個節點

實作上的細節要留意。

記得把串列長度加一。

並且在新節點之後串接上原本後面的節點。

時間複雜度: O(1) 常數時間

  def insertAfter(self, node, new_node):

    self.size += 1

    the_one_after_insertion = node.next

    # Update linkage
    node.next = new_node
    new_node.prev = node

    the_one_after_insertion.prev = new_node
    new_node.next = the_one_after_insertion
    return

完整的Doubly Linked List實作和程式碼

class Node:
  def __init__(self, data):
    # 儲存節點的資料
    self.data = data

    # 指向下一個節點，初始化為空 None
    self.next = None

    # 指向前一個節點，初始化為空 None
    self.prev = None


class LinkedList:

  def __init__(self):

    # 頭部節點初始化為空
    self.head = None
    # 尾巴節點初始化為空
    self.tail = None
    
    # 串列長度初始化為0
    self.size = 0


  def insertAtHead(self,data):
  
    new_node = Node(data)

    self.size += 1

    # If the list is empty
    if self.tail is None:
      self.head = new_node
      self.tail = new_node
    else:

      # Update linkage
      new_node.next = self.head
      self.head.prev = new_node

      self.head = new_node
    return


  def insertAtTail(self, data):
  
    new_node = Node(data)

    self.size += 1

    # If the list is empty
    if self.head is None:
      self.head = new_node
      self.tail = new_node
    else:

      # Update linkage
      self.tail.next = new_node
      new_node.prev = self.tail

      self.tail = new_node

    return


  def removeAtHead(self):
  
    if self.head is None:
      return
    else:
      self.size -= 1
      oldHead = self.head

      # Update linkage
      if self.head == self.tail:
        self.tail = None
        self.head = None
      else:
        self.head = self.head.next
      
      # Break linkage
      oldHead.next = None

      if self.head:
        self.head.prev = None

      return oldHead


  def removeAtTail(self):
  
    if self.tail is None:
      return
    else:
      self.size -= 1
      oldTail = self.tail

      # Update linkage
      if self.tail == self.head:
        self.tail = None
        self.head = None
      else:
        self.tail = self.tail.prev

      # Break linkage
      oldTail.prev = None

      if self.tail:
        self.tail.next = None

      return oldTail


  def traverse(self):

    print("Forward traversal")
    cur = self.head

    while cur:
      print(cur.data, end=' <-> ')
      cur = cur.next
    print("None")

    print(f"Size of singly linked list: {self.size} \n", )
    return


  def backward_traverse(self):

    print("Backward traversal")
    cur = self.tail

    while cur:
      print(cur.data, end=' <-> ')
      cur = cur.prev
    print("None")

    print(f"Size of singly linked list: {self.size} \n", )
    return

  def search(self, target):
    cur = self.head
    while cur:
      if cur.data == target:
        return cur

      cur = cur.next

    return None


  def removeAfter(self, node):

    self.size -= 1

    removed = node.next
    the_one_after_removal = node.next.next if node.next else None

    # Update linkage
    if the_one_after_removal:
      the_one_after_removal.prev = node

    node.next = the_one_after_removal
    # Break linkage
    if removed:
      removed.next = None
      removed.prev = None

    return removed


  def insertAfter(self, node, new_node):

    self.size += 1

    the_one_after_insertion = node.next

    # Update linkage
    node.next = new_node
    new_node.prev = node

    the_one_after_insertion.prev = new_node
    new_node.next = the_one_after_insertion
    return


def test():

  print(f"Empty list\n")
  linkedlist = LinkedList()
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Insert 3 on tail\n") 
  linkedlist.insertAtTail(3)
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Insert 4 on tail\n")
  linkedlist.insertAtTail(4)
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Insert 5 on tail\n")
  linkedlist.insertAtTail(5)
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Insert 2 on head\n") 
  linkedlist.insertAtHead(2)
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Insert 1 on head\n") 
  linkedlist.insertAtHead(1)
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Search 3 in linked list\n")
  result = linkedlist.search(3)
  print( result.data )

  print("--------------------")
  print(f"Remove node 4, which is after node 3\n")
  linkedlist.removeAfter(result)
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  node_100 = Node(100)  
  print(f"Insert node 100 after node 3\n")
  linkedlist.insertAfter(result, node_100)
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Remove 1 on Head\n")
  linkedlist.removeAtHead()
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Remove 2 on Head\n") 
  linkedlist.removeAtHead()
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Remove 3 on Head\n")
  linkedlist.removeAtHead()
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Remove 5 on Tail\n")
  linkedlist.removeAtTail()
  linkedlist.traverse()
  linkedlist.backward_traverse()

  print("--------------------")
  print(f"Remove 100 on Tail\n")
  result = linkedlist.removeAtTail()
  print(f"Removed node value = {result.data} \n")
  linkedlist.traverse()
  linkedlist.backward_traverse()
  
  return

if __name__ == "__main__":
  test()

測試輸出

Empty list

Forward traversal
None
Size of singly linked list: 0 

Backward traversal
None
Size of singly linked list: 0 

--------------------
Insert 3 on tail

Forward traversal
3 <-> None
Size of singly linked list: 1 

Backward traversal
3 <-> None
Size of singly linked list: 1 

--------------------
Insert 4 on tail

Forward traversal
3 <-> 4 <-> None
Size of singly linked list: 2 

Backward traversal
4 <-> 3 <-> None
Size of singly linked list: 2 

--------------------
Insert 5 on tail

Forward traversal
3 <-> 4 <-> 5 <-> None
Size of singly linked list: 3 

Backward traversal
5 <-> 4 <-> 3 <-> None
Size of singly linked list: 3 

--------------------
Insert 2 on head

Forward traversal
2 <-> 3 <-> 4 <-> 5 <-> None
Size of singly linked list: 4 

Backward traversal
5 <-> 4 <-> 3 <-> 2 <-> None
Size of singly linked list: 4 

--------------------
Insert 1 on head

Forward traversal
1 <-> 2 <-> 3 <-> 4 <-> 5 <-> None
Size of singly linked list: 5 

Backward traversal
5 <-> 4 <-> 3 <-> 2 <-> 1 <-> None
Size of singly linked list: 5 

--------------------
Search 3 in linked list

3
--------------------
Remove node 4, which is after node 3

Forward traversal
1 <-> 2 <-> 3 <-> 5 <-> None
Size of singly linked list: 4 

Backward traversal
5 <-> 3 <-> 2 <-> 1 <-> None
Size of singly linked list: 4 

--------------------
Insert node 100 after node 3

Forward traversal
1 <-> 2 <-> 3 <-> 100 <-> 5 <-> None
Size of singly linked list: 5 

Backward traversal
5 <-> 100 <-> 3 <-> 2 <-> 1 <-> None
Size of singly linked list: 5 

--------------------
Remove 1 on Head

Forward traversal
2 <-> 3 <-> 100 <-> 5 <-> None
Size of singly linked list: 4 

Backward traversal
5 <-> 100 <-> 3 <-> 2 <-> None
Size of singly linked list: 4 

--------------------
Remove 2 on Head

Forward traversal
3 <-> 100 <-> 5 <-> None
Size of singly linked list: 3 

Backward traversal
5 <-> 100 <-> 3 <-> None
Size of singly linked list: 3 

--------------------
Remove 3 on Head

Forward traversal
100 <-> 5 <-> None
Size of singly linked list: 2 

Backward traversal
5 <-> 100 <-> None
Size of singly linked list: 2 

--------------------
Remove 5 on Tail

Forward traversal
100 <-> None
Size of singly linked list: 1 

Backward traversal
100 <-> None
Size of singly linked list: 1 

--------------------
Remove 100 on Tail

Removed node value = 100 

Forward traversal
None
Size of singly linked list: 0 

Backward traversal
None
Size of singly linked list: 0 

結語

一開始接觸linked list可能會覺得有點卡卡的，不像array 那樣操作起來那麼直覺。

可以透過紙筆追蹤演算法和程式執行邏輯，測試幾個簡單的小範例，

會有更深刻的了解和體會！

Linked List相關的演算法練習題與詳解

經典串列題 合併已排序好的兩條串列 Merge Two Sorted Lists Leetcode #21

串列應用題 移除尾巴數來的第n個節點 Leetcode #19

鍊表應用: 簡化鏈結串列 Remove Zero Sum Nodes_Leetcode #1171

嵌套娃娃 用遞迴解 串列化簡題 Leetcode #2487

串列應用: 合併非零的節點 Merge Nodes in Between Zeros_Leetcode #2181

複製客製化鏈結串列 Copy List w/ Random Pointer_Leetcode #138

一魚多吃 用雙指針找出串列的中點 Middle of Linked list_Leetcode #876

串列應用: 反轉整個串列Reverse Linked List_Leetcode #206_Leetcode 精選75

串列應用: 刪除鏈結串列的中央節點_Leetcode #2095_Leetcode精選75題

鏈結串列中的Twin Sum的最大值_Leetcode #2130_Leetcode 75題精選

重組為奇串列和偶串列 Odd Even Linked List_Leetcode #328 精選75題

合縱連橫: 從鏈結串列應用題 理解 遞回 背後的本質