順序表與鏈表是非常基本的數據結構，它們可以被統稱為線性表。
線性表（Linear List）是由 n（n≥0）個數據元素（結點）a[0]，a[1]，a[2]…，a[n-1] 組成的有限序列。
順序表和鏈表，是線性表的不同存儲結構。它們各自有不同的特點和適用范圍。針對它們各自的缺點，也有很多改進的措施。
一、順序表
順序表一般表現為數組，使用一組地址連續的存儲單元依次存儲數據元素，如圖 1 所示。它具有如下特點：
- 長度固定，必須在分配內存之前確定數組的長度。
- 存儲空間連續，即允許元素的隨機訪問。
- 存儲密度大，內存中存儲的全部是數據元素。
- 要訪問特定元素，可以使用索引訪問，時間復雜度為?O(1)O(1)。
- 要想在順序表中插入或刪除一個元素，都涉及到之后所有元素的移動，因此時間復雜度為?O(n)O(n)。
圖 1 順序表
順序表最主要的問題就是要求長度是固定的，可以使用倍增-復制的辦法來支持動態擴容，將順序表變成“可變長度”的。
具體做法是初始情況使用一個初始容量（可以指定）的數組，當元素個數超過數組的長度時，就重新申請一個長度為原先二倍的數組，并將舊的數據復制過去，這樣就可以有新的空間來存放元素了。這樣，列表看起來就是可變長度的。
一個簡單的實現如下所示，初始的容量為 4。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <string.h>struct?sqlist {????int?*items, size, capacity;????sqlist():size(0), capacity(4) {????????// initial capacity = 4????????items =?new?int[capacity];????}????void?doubleCapacity() {????????capacity *= 2;????????int* newItems =?new?int[capacity];????????memcpy(newItems, items,?sizeof(int)*size);????????delete[] items;????????items = newItems;????}????void?add(int?value) {????????if?(size >= capacity) {????????????doubleCapacity();????????}????????items[size++] = value;????}}; |
這個辦法不可避免的會浪費一些內存，因為數組的容量總是倍增的。而且每次擴容的時候，都需要將舊的數據全部復制一份，肯定會影響效率。不過實際上，這樣做還是直接使用鏈表的效率要高，具體原因會在下一節進行分析。
二、鏈表
鏈表，類似它的名字，表中的每個節點都保存有指向下一個節點的指針，所有節點串成一條鏈。根據指針的不同，還有單鏈表、雙鏈表和循環鏈表的區分，如圖 2 所示。
圖 2 鏈表
單鏈表是只包含指向下一個節點的指針，只能單向遍歷。
雙鏈表即包含指向下一個節點的指針，也包含指向前一個節點的指針，因此可以雙向遍歷。
循環單鏈表則是將尾節點與首節點鏈接起來，形成了一個環狀結構，在某些情況下會非常有用。
還有循環雙鏈表，與循環單鏈表類似，這里就不再贅述。
由于鏈表是使用指針將節點連起來，因此無需使用連續的空間，它具有以下特點：
- 長度不固定，可以任意增刪。
- 存儲空間不連續，數據元素之間使用指針相連，每個數據元素只能訪問周圍的一個元素（根據單鏈表還是雙鏈表有所不同）。
- 存儲密度小，因為每個數據元素，都需要額外存儲一個指向下一元素的指針（雙鏈表則需要兩個指針）。
- 要訪問特定元素，只能從鏈表頭開始，遍歷到該元素，時間復雜度為?O(n)O(n)。
- 在特定的數據元素之后插入或刪除元素，不涉及到其他元素的移動，因此時間復雜度為?O(1)O(1)。雙鏈表還允許在特定的數據元素之前插入或刪除元素。
在上一節說到，利用倍增-復制的辦法，同樣可以讓順序表長度可變，而且效率比鏈表還要好，下面就簡單的實現一個單鏈表來驗證這一點，至于元素插入的順序就不要在意了。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <stdio.h>#include <time.h>??struct?node {????int?value;????node *next;};struct?llist {????node *head;????void?add(int?value) {????????node *newNode =?new?node();????????newNode->value = value;????????newNode->next = head;????????head = newNode;????}};int?main() {????int?size = 100000;????sqlist list1;????llist list2;????long?start =?clock();????for?(int?i = 0;i < size;i++) {????????list1.add(i);????}????long?end =?clock();????printf("sequence list: %d\n", end - start);????start =?clock();????for?(int?i = 0;i < size;i++) {????????list2.add(i);????}????end =?clock();????printf("linked list: %d\n", end - start);????return?0;} |
在我的電腦上，鏈表的耗時大約是順序表的 4~8 倍。會這樣，是因為數組只需要很少的幾次大塊內存分配，而鏈表則需要很多次小塊內存分配，內存分配操作相對是比較慢的，因而大大拖慢了鏈表的速度。這也是為什么會出現內存池。
因此，鏈表并不像理論分析的那樣美好，在實際應用中要受很多條件制約，一般情況下還是安心用順序表的好。
函數獲取時間的設置和使用方法)
