如果要保存一些數據類型相同的變量，比如n個int類型的變量，就可以存放在一個數組中，然後通過下標方便的訪問。可是數組的缺點也比較多，第一個就是在聲明數組的時候，數組的長度必須是明確的，即便是動態聲明一個數組，處理器必須要知道長度才能在內存中找出一段連續的內存來保存你的變量。第二個缺點也就是上一句中說到的，數組在內存中的地址必須是連續的，這樣就可以通過數組首地址再根據下標求出偏移量，快速訪問數組中的內容。現在計算機內存越來越大，這也算不上什麼缺點。第三個缺點，也是非常難以克服的缺點，就是在數組中插入一個元素是非常費勁的。比如一個長度為n的數組，你要在數組下標為0處插入一個元素，在不額外申請內存的情況下，就需要把數組中的元素全部後移一位，還要捨棄末尾元素，這個時間開銷是很大的，時間復雜度為o(n)。
數組的改良版本就是vector向量，它很好的克服了數組長度固定的缺點，vector的長度是可以動態增加的。如果明白向量的內部實現原理，那麼我們知道，vector的內部實現還是數組，只不過在元素數量超過vector長度時，會按乘法或者指數增長的原則，申請一段更大的內存，將原先的數據復制過去，然後釋放掉原先的內存。
如果你的數據不需要在數組中進行插入操作，那麼數組就是個很好的選擇，如果你的元素數組是動態增長的，那麼vector就可以滿足。
鏈表很好的克服了數組的缺點，它在內存中不需要連續的內存，插入或者刪除操作o(1)時間復雜度就能解決，長度也是動態增長。如果你的元素需要頻繁的進行插入、刪除操作，那麼鏈表就是個很好的選擇。下圖是數組和鏈表在內存中的組織形式
可以看到數組在內存中是連續的，用起始地址加上偏移地址就可以直接取出其中的元素，起始地址就是數組名，偏移地址就是數組的下標index*sizeof(t)，t就是數組的類型。
但是鏈表在內存中是不連續，為什麼叫鏈表，就是感覺像是用鏈子把一個個節點串起來的。那麼一個個節點是怎麼串接起來的呢，就是指針，每一個節點（末尾節點除外）都包含了指向下一個節點的指針，也就是說指針中保存著下一個節點的首地址，這樣，1號節點知道2號節點保存在什麼地址，2號節點知道3號節點保存在什麼地址...以此類推。就像現實中尋寶一樣，你只知道1號藏寶點，所以你先到達1號藏寶點，1號藏寶點你會得到2號藏寶點的地址，然後你再到達2號藏寶點...直到你找到了你需要的寶藏。鏈表的遍歷就是用這種原理。
鏈表已經超出了基本數據類型的范圍，所以要使用鏈表，要麼使用STL庫，要麼自己用基本數據類型實現一個鏈表。如果是編程中正常的使用，當然是推薦前者，如果想真正搞懂鏈表這個數據結構，還是推薦後者。那樣不僅知道標准庫提供的API，也知道這種數據結構內部 的實現原理。這樣的一個好處就是在你編程的時候，尤其是對時間空間復雜度比較敏感的程序，你可以根據要求選擇一種最適合的數據結構，提高程序運行的效率。
一個個節點按順序串接起來，就構成了鏈表。顯然這一個個節點是很關鍵的，假設我們要構造一個int類型的鏈表，那麼一個節點中就需要包含兩個元素，一個是當前節點所保存的值，設為int value。另一個就是指向下一個節點的指針，我們再假設這個節點類是node，那麼這個指針就是 node *next。這裡一定不是int *next。因為這個指針指向的下一個元素是一個類的實例，而不是int類型的數據。那麼node這個類最簡單的實現就如下
class node
{
public:
int value;
node *next;
node()
{
value = 0;
next = NULL;
}
};
這個類名字為node，包含兩個元素，一個是當前node的值，一個是指向下一個節點的指針，還有一個構造函數，分別將value初始化為0、next初始化為NULL。
拿到這個類以後，假設我們生成兩個這個類的實例，node1和node2，再將node1的next指針指向node2，就構成了有兩個元素的鏈表。這樣如果我們拿到node1這個節點，就可以通過next指針訪問node2。比如下面的代碼
#include先生成兩個node類的實例，node1和node2，分別將它們的value初始化為1和2。再用&運算符取出node2的首地址，賦值給node1.next。這樣node1的next指針就指向了node2。這樣我們就可以先拿到node1的next指針，在通過“->”運算符訪問node2的value值，輸出就是2。using namespace std; class node { public: int value; node *next; node() { value = 0; next = NULL; } }; int main() { node node1,node2; node1.value = 1; node2.value = 2; node1.next = &node2; cout << (node1.next)->value << endl; }
將剛剛的代碼稍作修改
#includeusing namespace std; class node { public: int value; node *next; node() { value = 0; next = NULL; } }; int main() { node node1,node2; node1.value = 1; node2.value = 2; node1.next = &node2; cout << sizeof(node) << endl; cout << &node1 << endl; cout << &node2 << endl; }
輸出是這樣的
這樣我們就可以根據輸出畫出它們在內存中的非常詳細結構圖
這樣就構成了一個最簡單的鏈表，如果還有新的節點出現，那麼就如法炮制，鏈在表尾或者表頭，當然插在中間也是沒問題的。
但是這樣還有個問題就是node1和node2是我們提前聲明好的，而且知道這兩個實例的名稱，如果我們需要1000甚至跟多節點，這種方式顯然是不科學的，而且在很多時候，我們都是動態生成一個類的實例，返回的是這個實例的首地址。下面的代碼我們用一個for循環，生成11個節點，串起來形成一個鏈表
#include原理就是先生成一個頭結點，然後動態生成10個節點，每生成一個節點，就將這個節點指向頭結點，然後更新頭結點為當前節點。為了驗證正確性，在程序末尾輸出head節點的值，為9。using namespace std; class node { public: int value; node *next; node() { value = 0; next = NULL; } }; int main() { node *head,*curr; head = new node(); head->next = NULL; head->value = 15; for (size_t i = 0; i < 10; i++) { curr = new node(); curr->value = i; curr->next = head; head = curr; } cout << head->value << endl; }
那麼鏈表該如何遍歷呢，剛開頭的時候就說，遍歷鏈表需要從頭到尾，訪問每一個元素，直到鏈表尾。也就是說不斷地訪問當前節點的next，直到NULL。下面是鏈表的遍歷輸出
#include下面是輸出結果using namespace std; class node { public: int value; node *next; node() { value = 0; next = NULL; } }; int main() { node *head,*curr; head = new node(); head->next = NULL; head->value = 15; for (size_t i = 0; i < 10; i++) { curr = new node(); curr->value = i; curr->next = head; head = curr; } while (head!=NULL) { cout << head->value << endl; head = head->next; } }
鏈表相對於數組有個非常明顯的優點就是能以時間復雜度o(1)完成一個節點的插入或者刪除操作。
插入操作的原理很簡單，假設現在有三個節點，一個是當前節點curr，一個是當前節點的下一個節點，也就是後繼節點，假設為next，還有一個待插入的節點，假設為insert。插入操作就是讓當前節點的後繼節點指向insert節點，insert節點的後繼節點指向next節點。以下是示意圖
刪除操作的原理也是類似的，就是讓當前節點的後繼節點指向它後繼節點的後繼節點。示意圖如下
那麼插入和刪除操作用代碼如何實現呢，我們還有原先的鏈表，先插入一個值為20的節點，輸出鏈表的全部元素。然後再刪除鏈表中這個值為20的元素，輸出元素的全部內容。代碼如下
