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

小松鼠

發佈於動手學Python 從小專案體驗樂趣

更新於 2024/08/27發佈於 2024/08/19閱讀時間約 30 分鐘

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題

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

小松鼠的演算法樂園動手學Python 從小專案體驗樂趣從範例學python小松鼠的演算法樂園動手學Python 從小專案體驗樂趣資料結構&演算法

留言

留言分享你的想法！

林燃（創作小說家）

2024/08/19

小松鼠

發文者

2024/08/19

林燃（創作小說家）海倫仙度絲~~~~

小松鼠

發文者

2024/08/22

在動手學Python 的引言與目錄提及了這篇文章，趕快過去看看吧！

小松鼠的演算法樂園

96會員

427內容數

由有業界實戰經驗的演算法工程師，手把手教你建立解題的框架，一步步寫出高效、清晰易懂的解題答案。著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。

小松鼠的演算法樂園的其他內容

2024/10/10

🔗Python deque 與 Queue 相關的常用操作

從Python 內建deque資料結構的角度切入，同時了解deque 與 FIFO Queue相關的function用法。 collections.deque是一種兩端點皆可進出的雙端佇列在兩端點高效地在O(1)常數時間內添加和刪除元素。這使得deque非常適合實現FIFO Queue