# Linked List ## 11/17社課 --- ## Linked List 鏈結串列 不常用的(?)指標結構 ---- ### Linked List是啥 一種struct 包含元素、連接下一個元素的指標 ---- ### 建立 Link List 的 struct ```cpp= struct exp{ int A; exp * next; } ``` exp1 >> next 指標 >> exp2... 這裡的int也能用其他型別替代 ---- ### 建置 head 結構起點 ```cpp= exp * head; head = new exp;//簡寫 exp * head = new exp; ``` 建立一個指向exp的指標 向記憶體要一個exp結構的空間 ---- ### 建置節點 ```cpp= head = new exp; exp * p1 = head; ``` 向記憶體要一塊結構後 用一個臨時指標p1指向head 表示目前p1節點的位置(head) ---- ### 建置下個節點 ```cpp= p1 -> next = new exp;// p1->next 可視為 p1指向next p1 = p1 -> next; p1 -> next = NULL;//如果不需要建置下個節點則指向NULL ``` 再和記憶體要一塊新的 exp 空間 讓 exp 空間中的 next 指向下一個 exp 的 head 最後讓 p1 指向 next(p1移動到新節點) ---- 利用迴圈建立Linked List ```cpp= exp * p1 = head; for( i = 1; i < n; i++ ){ cin >> a; p1 -> next = new exp(); p1 = p1 -> next; p1 -> A = a; p1 -> next = NULL; }; ``` --- ## 刪除節點 ---- ### 刪除首項 ```cpp= p2 = head;//將head紀錄位置存放到p2 head = head -> next; delete p2;//刪除原本head紀錄所占用空間 ``` ---- ### 刪除值在中間 ```cpp= int find; cin>>find; //要被刪掉的值 exp *p2, *follow; p2 = head; if ( head == NULL ){ //head為空的空鏈結 cout<<"Not Found"; //找不到 } if( head -> value == find ){ //第一個節點是要刪除的目標值 head = head -> next; //把head移到下一格去 delete p2; //刪掉存head值的p2 } //尋找要刪除的目標 while(( p2 != NULL ) && ( p2 -> value != find) ){ follow = p2; //把p2和follow往下移動 p2 = p2 -> next; } if( p2 == NULL ){ //找到最後一格還沒找到 cout<<"Not Found"; } else{ //刪除該節點 follow -> next = p2 -> next; delete p2; } ``` --- ### 優點 - 可快速刪除、新增元素 - 元素的類別不一定相同 - 不須先得知資料大小 - 不需要連續的記憶體空間 ---- ### 缺點 - 無法隨機存取(只知道首項) - 不知道值在第幾項的情況尋找很耗時 - 指標指來指去，很亂容易出錯 --- ## 練習 [b938](https://zerojudge.tw/ShowProblem?problemid=b938) 0u0 ...... ?