Link Lists

發表於 Disqus：
文章字數： 4.5k 所需閱讀時間 ≈ 8 分鐘

定義

由一組節點 (Node) 所組成的有序串列，各 Node 除了 Data 欄之外，另外有 ≥ 1 個 Link 欄 (或稱 Pointer)，用以指向其它 Node 之位址。

特質

  • 各Node不一定要佔用連續的Memory空間
  • 各Node之型態 (Data Type) (Data Type) 不一定要相同
  • 僅支援Sequential Access
  • Insert/Delete Node Insert/Delete Node 容易

Link list的種類

由一組節點 (Node)所組成的有序串列，各 Node 除了 Data 欄之外，另外有 1 個Link欄 (或稱 Pointer)，用以指向下一個 Node 之位址。

Create List

Insert Node

  • begin
  New(t);             //跟系統要求記憶體空間以配置一個新節點，且讓指標 t 指向該節點
  t → data = item;    //把item塞到這個新節點t的Data欄位中
1 t → link = x → link;//先把新節點t掛到x節點之後!!
2 x → link = t;       //再將x節點接到節點t
end
  • begin
  New(t);
  t → data = x → data;
  t → link = x → link;
  x → link = t;
  x → data = 20;
  x = t;
end;

Delete Node

刪除鏈節串列的節點時，會先:

  1. 改變串列指標，以做到邏輯性移除(Logically Remove)的動作
  2. 再將要被移除的節點做實際刪除(Physically Delete) 的動作，讓節點從記憶體中刪除

需要準備兩個輔助指標 x 與 pPre：

  • x用以指向欲刪除的節點
  • pPre指向節點x所在之前一個node
1 if (pPre = nil) then     //表示 x 為第一個節點
    list = x → link;
  else                     //表示 x 節點是中間節點
    pPre → link = x → link;
2 Ret(x);                  //將 “節點 x” 回收. 有的書是用delete(x), release(x), dispose(x)…etc.

Storage Pool

可用節點 (Free Node) 之集合 (集中管理之處)，通常O.S.以 Single link list 來管理 Free Nodes，稱為 AV-list(Available list) 提供兩個動作:

  • New(t): 相當於刪除 AV-list 中 Free Node (if AV-list ≠ nil)
  • Ret(t): 相當於 Insert 節點到 AV-list 中

New(t)

if (AV ≠ nil) then
1 t = AV
2 AV = AV → link;
else
  print(“No Free Node.”);

Ret(t)

begin
1 t → link = AV;
2 AV = t;
end

將 Single link list 中，最後一個 node 的指標指回第一個 node

  • 不論從哪個 Node 開始，必定能夠拜訪 (經過) 所有 Node
    • 並無明顯的頭尾節點
    • Single Link List 必須從頭開始才可以
  • 回收整個串列的時間為 O(1) (即: 與 Link list 長度無關)
    • Single Link List 回收時間為 O(n) 其中, n 為長度或 Node 數目

回收時間的比較(單向 vs. 環狀)

Single Linked List

Procedure Release list(list: pointer to S.L.)
  if (list≠nil) then
    S = list;
1   while (S → link ≠ nil) do //while迴圈會讓S一直前進至最後一節點
      S = S → link;
2     S → link = AV;
3     AV = list;              //回收節點至AV list AV list 中

Time Complexity: O(N)

Circular Linked List

Procedure Release C(C: pointer to S.L.)
  begin
    if (C≠nil) then
1     p = C → link;
2     C → link = AV;
3     AV = P
  end

Time Complexity: O(1)

串列中各節點除了 Data 欄之外，另外有 2 個 Link 欄，用以指向前一個與下一個節點之位址

  • 一般使用雙向鏈結串列時，通常會加入串列首 (Head Node)，此 Node 不存資料

  • 此時，雙向鏈結串列可視為2個 Circular Link List

Insertion

插入Node t 在Node x之後: 

begin
1 t → RLink = x → RLink;
2 t → LLink = x;
3 (x → RLink) → LLink = t;
4 x → RLink = t;
end

Deletion

刪除一個節點 x: 

begin
1 (x → LLink) → RLink = x → RLink;
2 (x → RLink) → LLink = x → LLink ;
3 Ret(x);
end

Double linked list 與 Single linked list 的比較

Link list 三個常見的動作

Length

Single linked list

Procedure Length list(list: pointer to S.L.)
  count = 0;
  p = list;
  while (p≠ nil) do
    count++;
    p = p → link;
  return count;

Time Complexity: O(N)

Circular linked list

Procedure Length C(C: pointer to S.L.)
  if (C = nil) then
    return 0;
  else
    count = 0;
    p = C;
    repeat            //不能用while迴圈!!∵一定至少要做一次!!!
      count++;
      p = p → link;
    until p = C;

Time Complexity: O(N)

Concatenate

Single linked list

假設連結A, B串列成為C串列:

  • Case 1: A = nil and B ≠ nil, 則 C = B
  • Case 2: A ≠ nil and B = nil, 則 C = A
  • Case 3: A ≠ nil and B ≠ nil, 則 C = A+B
  • Case 4: A = nil and B = nil, 則 C = nil
Procedure Con.two.S(A, B, C: pointer to S.L.)
  C = nil;
  if (A = nil and B ≠ nil) then C = B;   //Case 1 
  elif (A ≠ nil and B = nil) then C = A; //Case 2 
  elif (A ≠ nil and B ≠ nil) then        //Case 3
    p = A;
1   while(p → link ≠ nil)  do
        p = p → link;
2     p → link = B;
3     C = A;
  return C;                       //回傳Case 1~4

Time Complexity: O(N) 或 O(M)

Circular linked list

假設連結A, B串列成為C串列:

  • Case 1: A = nil and B ≠ nil, 則 C = B
  • Case 2: A ≠ nil and B = nil, 則 C = A
  • Case 3: A ≠ nil and B ≠ nil, 則 C = A+B
  • Case 4: A = nil and B = nil, 則 C = nil
Procedure Con.two.S(A, B, C: pointer to C.L.)
  C = nil;
  if (A = nil and B ≠ nil) then C = B;   //Case 1 
  elif (A ≠ nil and B = nil) then C = A; //Case 2 
  elif (A ≠ nil and B ≠ nil) then        //Case 3
1   C = A → link;
2   A → link = B → link;
3   B → link = C;
  return C;                             //回傳 Case 1~ 4 的結果

Time Complexity: O(1)

Invert ( Reverse )

Single linked list

需要三個指標: r, q, p

  • r 跟著 q 走， q 跟著 p 走， p 往前進

Procedure Invert S(S: pointer to S.L.)
  p = S; q = nil;
  while (p ≠ nil) do
    r = q;    //r 一開始會在此被設為 nil
    q = p;
    p = p → link;
    q → link = r;
  S = q;       //S可能指向反轉後的第一個節點或是null list

PYTHON - Iterative 

def reverseList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    prev = None
    while head:
        curr = head
        head = head.next
        curr.next = prev
        prev = curr
    return prev
#    python 簡潔寫法
#    cur, prev = head, None
#    while cur:
#        cur.next, prev, cur = prev, cur, cur.next
#    return prev
Time Complexity: O(N)

  • Recursive 

    class Solution:
# @param {ListNode} head
# @return {ListNode}
    def reverseList(self, head):
        return self._reverse(head)

    def _reverse(self, node, prev=None):
        if not node:
	    return prev
        n = node.next
        node.next = prev
        return self._reverse(n, node)
    ### Circular linked list 亦需要三個指標: r, q, p

  • r跟著q走，q跟著p走，p往前進

Procedure Invert C(C: pointer to C.L.)
  if (C ≠ nil) then
    p = C → link;    //p指向C的下一個node
    q = C;          //初值
    while (p ≠ c) do
      r = q;
      q = p;
      p = p → link;
      q → link = r;
    C → link = q;
    C = q;

Time Complexity: O(N)

Array 與 Link List 的比較

參考資料

國立聯合大學陳士杰資料結構