初稿：2017-11-19 13:05:57 4種鏈表 鏈表和數組的區別 數組初始容量一旦確定，不能再改變，適合要處理的數據量已知的情況。 未知要處理的數據量使用數組，可能造成空間浪費或容量不足，雖然有動態數組可擴容，但是頻繁擴容會使系統產生很大的開銷。 鏈表容量不限，長度與元素個數相同，但是需要額 ...
初稿：2017-11-19 13:05:57
4種鏈表
- 不迴圈單鏈表：加頭結點，使得插入刪除操作相同，不必特別處理插入或刪除的是第一個位置的情況。
- 迴圈單鏈表：引用參數是最後一個結點的指針pTail，這樣既能迅速找到首結點pHead = pTail->next，也能迅速獲取表尾。
- 不迴圈雙向鏈表：p所指結點後插入結點q. q->next = p->next; p->next->pre = q; p->next = q; q->pre = p;
- 迴圈雙向鏈表：引用參數首或尾都可。
鏈表和數組的區別
數組初始容量一旦確定，不能再改變，適合要處理的數據量已知的情況。
未知要處理的數據量使用數組，可能造成空間浪費或容量不足，雖然有動態數組可擴容，但是頻繁擴容會使系統產生很大的開銷。
鏈表容量不限，長度與元素個數相同，但是需要額外的空間存放下一元素的地址，空間使用率不如數組。
按index查找，數組存取元素時間複雜度是O（1），鏈表是O（n）
鏈表插入和刪除時間複雜度是O（1），數組是O（n）
查找值是value的某個元素，速度則相同。
