Linked Lists

Size: px

Start display at page:

Download "Linked Lists"

鱼霓郑
5 years ago
Views:

1 LINKED LISTS Prof. Michael Tsai 2013/3/12

2 2 大家來吐 Array 的槽 Array 有什麼不好? 插入新 element 1 3 4新的空 5 刪除原本的 element Time complexity= O(??)

3 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 4 新朋友 : Linked List 要怎麼讓資料 1. 可以隨便亂排 2. 但是我們仍然知道他的順序? 答案 : 資料亂排但是, 另外存下一個是誰 index [0] [1] [2] [3] [4] 資料下一個是誰ㄇㄆㄅㄉㄈ開始 1

5 5 概念上, 應該是長這樣開始ㄅㄆㄇㄈㄉ Null 真正的樣子 : index [0] [1] [2] [3] [4] 資料下一個是誰ㄇㄆㄅㄉㄈ開始 2

6 6 增加一個人? 開始ㄅㄆㄇㄈㄉ Null ㄐ index [0] [1] [2] [3] [4] [5] 資料下一個是誰ㄇㄆㄅㄉㄈㄐ開始 2

7 7 刪掉一個人開始ㄅㄆㄇㄈㄉ Null ㄐ index [0] [1] [2] [3] [4] [5] 資料下一個是誰ㄇㄆㄅㄉㄈㄐ開始 2

8 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 9 來看一些 code new 是指標, 指到一個 struct listnode 的變數. 那如果要拿這個變數裡面的 data 呢? 可以這樣寫 : (*new).data 或者, new->data 要拿 next 呢? (*new).next 或者, new->next

10 10 來看一些 code head 假設 head 指到第一個 struct ListNode 那麼我要拿到 551 的下一個 ListNode 的位址怎麼寫? head->link->link ( 連續技 )

11 11 製造兩個 node head 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 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

13 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

14 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 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 16 < 動腦時間 > 有沒有什麼是 array 比 linked list 好的? 什麼時候用 array? 什麼時候用 linked list? < 練習題 1> 我想要找 linked list 裡面從尾巴數過來的第 k 個 node, 要怎麼寫 code? 時間複雜度為? 練習題 1 答案 : O(n), Karumanchi 3.10 problem 2,4,5

17 17 Example: Stacks & Queues 如果是一塊記憶體要放很多 stack 或 queue 就很難做到很 efficient 例如如果某一 stack 滿了, 就要把一堆資料往後擠就不是 O(1) 了 T_T 解決 : 跟 Linked List 當朋友

18 18 Stack 要怎麼拿來當 stack 呢? ( 想想怎麼做主要的 operation) push & pop 請一位同學來講解 head 資訊工程系 Null 例 : push( 學 ) head 當作 stack top 怎麼寫 code? 那 pop 呢?

19 19 Queue 類似 stack 的作法不過頭尾都要有一個指標從頭拿, 從尾放 front rear 資訊工程 Null 怎麼拿? (DeQueue) struct ListNode* tmp; tmp=front; front=front->link; tmp_data=tmp->data; free(tmp); return tmp_data;

20 Queue new 20 系 front rear 資訊工程那怎麼放? 假設 new 是指到新的 node rear->next=new; new->next=null; rear=new;

21 21 練習題 2: 把 linked list 反過來反過來 : 把 a 變成 b 怎麼弄? 答案 : Karumanchi 3.10 problem 16

22 22 Singly v.s. doubly linked list Singly linked list: head Doubly linked list: head 什麼時候需要用雙? Singly linked list 只能往後, 不能往前 ( 要從最前面開始重新找 ) Doubly linked list 用在常常需要倒帶的時候好處 : 倒帶方便 (O(1)) ( 想想在 singly linked list 裡面要刪掉一個 node 時, 必須要找到前一個 node) 壞處 : 兩個 pointer 的儲存空間 Insert/delete 的時候稍微慢一點 ( 要處理兩個 pointer, next & prev)

23 23 回收很慢要把一個用完的 linked list 每個 node 都 free 掉 (Why?) 有幾項就要幾項的時間 : O(n) 懶人方法 : 丟到一個回收桶, 之後需要的時候再撿出來希望丟 =O(1), 而且撿 =O(1) 怎麼做? 回收桶 3 14 a 關鍵 : 找尾巴很慢. ( 不是 O(1)) 但是又不想多花空間紀錄尾巴

24 24 Circular List 開始的那個箭頭, 指在尾巴最後一個 node 指回開頭有什麼好處? 串接很方便! 丟進回收桶 =O(1)!! temp 回收桶 head 也可以有 doubly circular linked list!

25 25 暫停! 來回想一下我們學了哪些種類的 linked list Singly linked list Circular Non-circular (chain) Doubly linked list Circular Non-circular (chain)

26 26 Today s Reading Assignments Karumanchi 有很多的 source code, 特別是 3.6 的部分是基礎, 一定要看懂! Karumanchi 3.10 problem {2,4,5},{15,16},{24,25,27}

Linked Lists

LINKED LISTS Prof. Michael Tsai 2012/3/13 作業一今天 5pm 到期下次作業起 2:20pm 到期作業二今晚公布兩周後到期 2 大家來吐 Array 的槽 Array 有什麼不好? 插入新 element 1 3 4 新的 24 52 空 5 刪除原本的 element 1 3 42 25 5 Time complexity= O(??) 3 Array 的複雜度