前言

紀錄一下之前上 Coursera 的 Data Structure (UCSD開的)的課程筆記，不然當初在紙上寫的這些筆記都要爛了XD

相較於上一個專項課程 “Algorithm Toolbox”，DS 的教授在討論區的回覆幫助程度稍遜色@@，大部分都滿慢才回覆大家的留言

但整體上還是很棒的一堂課，教材與每份作業的 starter code 都很有架構

Array

在記憶體中有連續的儲存地址，每個元素的記憶體大小空間一樣

read / write 任何數值的時間複雜度是constant的

compiler會根據base address (就是[0]的地址)，計算第n個元素的address

n_addr = base_addr + n * element size

linkedlist1

Array從資料後面做新增/刪除容易，複雜度是O(1)
但如果要從資料前面、中間做新增/刪除，複雜度就較高，要把後面的元素往前推，複雜度是O(n)

Singly-Linked list

並不是連續的儲存地址，利用指標的方式串聯資料 (C++、JAVA是用Abstract class)

每一組資料都存有下一組資料的地址

linkedlist2

1
2
3
4
5
// Definition for singly-linked list.
struct ListNode {
	int val;
	struct ListNode *next;
};

新增/刪除只要修改指到該組資料的位址即可，適合用在常變動的資料上

通常會用一個 head pointer 指向list的第一筆資料，永遠紀錄list的頭

如果只有紀錄head，做尾端資料的處理時間複雜度會較高

可以再用一個指標 tail pointer 指向最後一筆資料，永遠紀錄list的尾

新增資料

  • 從後面新增
    linkedlist3
1
2
3
4
5
6
7
8
9
PushBack(key)
  node ← new node
  node.key ← key
  node.next = null
  if tail = null  // empty list
    head ← tail ← node
  else
    tail.next ← node
    tail ← node
  • 從前面新增
    linkedlist4
1
2
3
4
5
6
7
PushFront(key)
  node ← new node
  node.key ← key
  node.next ← head
  head ← node
  if tail = null  // empty list
    head ← tail
  • 從中間新增
    linkedlist5
1
2
3
4
5
6
7
8
AddAfterk(node, key) // 新增資料在特定資料後面
  // node = 特定資料, node2 = 要新增的資料
  node2 ← new node
  node2.key ← key
  node2.next = node.next
  node.next = node2
  if tail = node  // 如果特定資料是尾端, 要更新tail pointer
    tail ← node2

刪除資料

  • 從後面刪除
    • 該筆資料的前一筆資料的儲存地址的pointer指向NULL，tail pointer指向前一筆資料
    • free(delete)該筆資料
1
2
3
4
5
6
7
8
9
10
11
12
PopBack()
  if head = null
    ERROR: empty list // return
  if head = tail  // 只有1筆資料
    head ← tail ← null
  else  // 須第三個指標指到尾端資料的前一個
    ptr ← head
    // 瀏覽list 
    while ptr.next.next != null
      ptr ← ptr.next
    ptr.next = null  // 尾端資料的前一筆指向null 
    tail ← ptr
  • 從前面刪除
    • 該筆資料儲存地址的pointer指向NULL，head pointer指向該筆資料
    • free(delete)該筆資料
1
2
3
4
5
6
PopFront()
  if head = null
    ERROR: empty list // return
  head ← head.next  // 直接繞過去
  if head = null // 如果原本只有一筆資料, 做完前面的動作會被清空, tail pointer要指回null
    tail ← tail
  • 從中間刪除
    • 先判斷此筆資料是否為head或tail，都不是的話就需要做中間刪除
    • 在singly-linked list中，我們無法知道每個資料的上一筆是誰，必須要額外用兩個指標去跑迴圈，例如target & prev
    • target找到要刪除的資料，prev則一直指在target的前一個資料

另一種解法是，雖然不能知道上一筆是誰，但可以知道下一筆是誰，可以運用這個原理，讓ptr->next->value找到要刪除的資料，ptr就會指在要刪除的資料的前一筆，但必須先判斷要刪除的資料是否為頭或尾

linkedlist6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Erase(key)
    if key = head.value
       PopFront
       return
    if key = tail.value
       PopBack
       return 
    ptr ← head
    // 瀏覽list 
    while ptr.next.next != null
      if ptr.next.value = key
         break
      else
         ptr ← ptr.next

    // ptr指在要刪除的資料的前一個
    ptr.next = ptr.next.next

時間複雜度比較

singly-linked list no tail pointer with tail pointer
PushFront(key) O(1) O(1)
PushBack(key) O(n) O(1)
AddAfter(node, key) O(1) O(1)
AddBefore(node, key) O(n) O(n)
PopFront() O(1) O(1)
PopBack() O(n) O(n)
Erase(key) O(n) O(n)
Find(key) O(n) O(n)

Find(key) 就不貼pesudo code了，就是跑迴圈找到match的資料

Doubly-Linked list

由於單向的連結串列在處理尾端資料時因為無法知道前一筆是誰，需要耗費O(n)的時間複雜度搜尋，所以又出現了另一種串聯資料結構，叫做雙向連結串列

linkedlist7

相較於單向的資料結構，程式的處理上會比較複雜難讀一些，因為要處理2個指標 *prev 、 *next 的位址變化

雙向的新增與刪除資料再製圖太麻煩了OTZ
以下直接貼部分函式的pesudo code，跟著程式碼紙上演練一遍就會懂了

1
2
3
4
5
6
7
8
9
10
11
12
PushBack(key)
  //新增一個指向null的node
  node ← newnode
  node.key ← key
  node.next ← null
  if tail = null // empty list
    head ← tail ← node
    node.prev ← null
  else
    tail.next ← node
    node.prev = tail
    tail ← node
1
2
3
4
5
6
7
8
PopBack()
  if head = null
    ERROR: empty list // return
  if head = tail  // 只有一筆資料
    head ← tail ← null
  else
    tail ← tail.prev  // tail指到目前尾端資料的上一個資料
    tail.next ← null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
AddAfter(node, key)
  // node 的後面為 node2 要插入的位置
  node2 ← new node
  node2.key ← key
  node2.next ← node.next
  node2.prev ← node
  node.next ← node2

  /* 不是加在最後一筆資料後的話，
     要把原來node的下一筆資料的prev改指到node2 */
  if node2.next != null
    node2.next.prev ← node2

  // 如果是加在最後一筆資料後的話, tail pointer要更新為node2
  if tail = node  
    tail ← node2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
AddBefore(node, key)
  // node 的後面為 node2 要插入的位置
  node2 ← new node
  node2.key ← key
  node2.next ← node
  node2.prev ← node.prev
  node.prev ← node2

  /* 不是加在第一筆資料前的話，
     要把原來node的前一筆資料的next改指到node2 */
  if node2.prev != null
    node2.prev.next ← node2

  // 如果是加在第一筆資料前的話, head pointer要更新為node2
  if head = node  
    head ← node2

簡單小結

Array是一個有界限的長度，適合用在已知要處理多少大小資料的情況上
Array的好處是可以用O(1)的時間去存取資料

Linked list較有彈性，適合用在不知道有多少大小的資料上(新增或刪除很頻繁)
但是相較Array存取元素而言顯得較慢，必須花費一定的時間跑遍list