LINKED LISTS Prof. Michael Tsai 2013/3/12
2 大家來吐 Array 的槽 Array 有什麼不好? 插入新 element 1 3 4新的 24 52 空 5 刪除原本的 element 1 3 42 25 5 Time complexity= O(??)
3 Array 的複雜度 Indexing ( 拿某一個元素 ) 在開頭 Insert/Delete 在尾巴 Insert/Delete 在中間 Insert/Delete Array Dynamic Array ( 滿了以後擴充成兩倍 ) O(1) O(1)?? O(n), only feasible if not full O(1), only feasible if not full O(n), only feasible if not full O(n)?? O(1), if not full O(n), if full Linked List ( 今天要學的 )?? O(n)?? 浪費的空間 0 O(n)??
4 新朋友 : Linked List 要怎麼讓資料 1. 可以隨便亂排 2. 但是我們仍然知道他的順序? 答案 : 資料亂排 但是, 另外存 下一個是誰 index [0] [1] [2] [3] [4] 資料 下一個是誰 ㄇㄆㄅㄉㄈ 4 0 1-1 3 開始 1
5 概念上, 應該是長這樣 開始 ㄅㄆㄇㄈㄉ Null 真正的樣子 : index [0] [1] [2] [3] [4] 資料 下一個是誰 ㄇㄆㄅㄉㄈ 4 0 1-1 3 開始 2
6 增加一個人? 開始 ㄅㄆㄇㄈㄉ Null ㄐ index [0] [1] [2] [3] [4] [5] 資料 下一個是誰 ㄇ ㄆ ㄅ ㄉ ㄈ ㄐ 4 50 1-1 3 0 開始 2
7 刪掉一個人 開始 ㄅㄆㄇㄈㄉ Null ㄐ index [0] [1] [2] [3] [4] [5] 資料 下一個是誰 ㄇㄆㄅㄉㄈㄐ 4 5 1-1 3 04 開始 2
8 來看一些 code ( 用 malloc/free) 怎麼宣告一個 node 的 struct? struct ListNode { int data; struct ListNode *next; }; 怎麼拿一個新的 node? struct ListNode *new; new=(struct ListNode*)malloc(sizeof(struct listnode));
9 來看一些 code new 是指標, 指到一個 struct listnode 的變數. 那如果要拿這個變數裡面的 data 呢? 可以這樣寫 : (*new).data 或者, new->data 要拿 next 呢? (*new).next 或者, new->next
10 來看一些 code head 342 551 假設 head 指到第一個 struct ListNode 那麼我要拿到 551 的下一個 ListNode 的位址怎麼寫? head->link->link ( 連續技 )
11 製造兩個 node head 342 551 struct ListNode *head, *tmp; tmp=(struct ListNode*)malloc(sizeof(struct ListNode)); if (tmp==null) exit(-1); // exit program on error tmp->data=551; tmp->next=null; head=tmp; tmp=(struct ListNode*)malloc(sizeof(struct ListNode)); tmp->data=342; tmp->next=head; head=tmp;
12 插入一個新 node 在某 node 後面 struct ListNode *x; // 指到要插入的 node 的位置 struct ListNode *new; new=(struct ListNode*)malloc(sizeof(struct ListNode)); new->data=123; 下一步呢? 先處理 new->next 還是 x->next? new->next=x->next; x->next=new; x 123 new 342 342 551
13 刪除某一個 node struct ListNode *head; // 指到一開始的 node 的位置 struct ListNode *x; // 指到要刪除的 node 的位置 struct ListNode *trail; // 指到 x 的前一個 node 的位置 分兩種狀況處理 : x 是頭, 還有 x 不是頭 if (trail) //x 不是第一個 node trail->next=x->next; head x 551 else free(x); head=x->next; trail x 342 342 342 551
14 Examples 印出整個 linked list struct ListNode *tmp; for(tmp=head; tmp!=null; tmp=tmp->next) printf( %d, tmp->data); 找到某個 node 有 data 的前一個 node 的位置 int a=123; // 假設我們要找資料是 123 的 node 的前一個 node 位置 struct ListNode *tmp; for(tmp=head; tmp!=null; tmp=tmp->next) { if (tmp->next!=null) { // 因為 tmp->next 可能是 NULL! if (tmp->next->data==a) break; // break 出去的時候, tmp 就是我們要的 } }
15 Array 和 Linked List 的複雜度比較 Indexing ( 拿某一個元素 ) 在開頭 Insert/Delete 在尾巴 Insert/Delete 在中間 Insert/Delete 浪費的空間 ( 不是拿來存資料的部分 ) Array Dynamic Array ( 滿了以後擴充成兩倍 ) O(1) O(1) O(n) O(n), only feasible if not full O(1), only feasible if not full O(n), only feasible if not full O(n) O(1), if not full O(n), if full O(n) 0 ( 存滿以後 ) O(n) ( 最多可能有一半的空間是空的 ) Linked List O(1) O(n) 找到尾巴 O(1) insert/delete O(n) 找到位置 O(1) insert/delete O(n) ( 每個 node 都有拿來存 next node 的位址欄位 )
16 < 動腦時間 > 有沒有什麼是 array 比 linked list 好的? 什麼時候用 array? 什麼時候用 linked list? < 練習題 1> 我想要找 linked list 裡面從尾巴數過來的第 k 個 node, 要怎麼寫 code? 時間複雜度為? 練習題 1 答案 : O(n), Karumanchi 3.10 problem 2,4,5
17 Example: Stacks & Queues 如果是一塊記憶體要放很多 stack 或 queue 就很難做到很 efficient 例如如果某一 stack 滿了, 就要把一堆資料往後擠 就不是 O(1) 了 T_T 解決 : 跟 Linked List 當朋友
18 Stack 要怎麼拿來當 stack 呢? ( 想想怎麼做主要的 operation) push & pop 請一位同學來講解 head 資 訊 工 程 系 Null 例 : push( 學 ) head 當作 stack top 怎麼寫 code? 那 pop 呢?
19 Queue 類似 stack 的作法 不過頭尾都要有一個指標 從頭拿, 從尾放 front rear 資訊工程 Null 怎麼拿? (DeQueue) struct ListNode* tmp; tmp=front; front=front->link; tmp_data=tmp->data; free(tmp); return tmp_data;
Queue new 20 系 front rear 資 訊 工 程 那怎麼放? 假設 new 是指到新的 node rear->next=new; new->next=null; rear=new;
21 練習題 2: 把 linked list 反過來 反過來 : 把 a 3 14 2 8 1 0 變成 b 1 0 2 8 3 14 怎麼弄? 答案 : Karumanchi 3.10 problem 16
22 Singly v.s. doubly linked list Singly linked list: head Doubly linked list: 3 14 2 8 1 0 head 3 14 2 8 1 0 什麼時候需要用雙? Singly linked list 只能往後, 不能往前 ( 要從最前面開始重新找 ) Doubly linked list 用在常常需要 倒帶 的時候 好處 : 倒帶方便 (O(1)) ( 想想在 singly linked list 裡面要刪掉一個 node 時, 必須要找到前一個 node) 壞處 : 兩個 pointer 的儲存空間 Insert/delete 的時候稍微慢一點 ( 要處理兩個 pointer, next & prev)
23 回收很慢 要把一個用完的 linked list 每個 node 都 free 掉 (Why?) 有幾項就要幾項的時間 : O(n) 懶人方法 : 丟到一個 回收桶, 之後需要的時候再撿出來 希望丟 =O(1), 而且撿 =O(1) 怎麼做? 回收桶 3 14 a 2 8 1 0 關鍵 : 找尾巴很慢. ( 不是 O(1)) 但是又不想多花空間紀錄尾巴
24 Circular List 開始 的那個箭頭, 指在尾巴 最後一個 node 指回開頭 有什麼好處? 串接很方便! 丟進回收桶 =O(1)!! temp 3 14 2 8 1 0 回收桶 head 也可以有 doubly circular linked list!
25 暫停! 來回想一下我們學了哪些種類的 linked list Singly linked list Circular Non-circular (chain) Doubly linked list Circular Non-circular (chain)
26 Today s Reading Assignments Karumanchi 3.1-3.8 有很多的 source code, 特別是 3.6 的部分是基礎, 一定要看懂! Karumanchi 3.10 problem {2,4,5},{15,16},{24,25,27}