1. 再談數(shù)組—順序存儲(chǔ)

我們在開始計(jì)算機(jī)課程沒多久后就已經(jīng)知曉了數(shù)組的概念，數(shù)組作為一個(gè)順序儲(chǔ)存方式數(shù)據(jù)結(jié)構(gòu)為我們的程序設(shè)計(jì)帶來了大量的便利，幾乎任何的高級(jí)程序設(shè)計(jì)，算法設(shè)計(jì)都離不開數(shù)組的靈活使用，但是，數(shù)組最大的缺點(diǎn)就是我們的插入和刪除時(shí)需要移動(dòng)大量的元素，顯然這需要消耗大量的時(shí)間。

以C語言數(shù)組插入一個(gè)元素為例，當(dāng)我們需要在一個(gè)數(shù)組{1,2,3,4,5,6,7}的第1個(gè)元素后（即第2個(gè)元素）的位置插入一個(gè)’A’時(shí)

我們需要做的有，將第1個(gè)元素后的整體元素后移，形成新的數(shù)組{1,2,2,3,4,5,6,7}，再將第2個(gè)元素位置的元素替換為我們所需要的元素’A’,最終形成我們的預(yù)期，一個(gè)簡單的插入操作要進(jìn)行那么多的步驟，顯然不是很核算。

由示意圖的操作，我們可以看出這樣做的弊端有二

其一：所需要移動(dòng)的元素很多，浪費(fèi)算力。

其二：必須為數(shù)組開足夠多的空間，否則有溢出風(fēng)險(xiǎn)。

2. 鏈表—鏈?zhǔn)酱鎯?chǔ)

C語言使用中，由于以上出現(xiàn)的這些問題，我們鏈表的概念就應(yīng)運(yùn)而生，鏈表通過不連續(xù)的儲(chǔ)存方式，以及指針的靈活使用，巧妙的簡化了上訴的內(nèi)容，同時(shí)鏈表是自適應(yīng)內(nèi)存大小的，也就是說無論我們設(shè)多大的數(shù)據(jù)，理論上都可以實(shí)現(xiàn)（當(dāng)然不能超過你的機(jī)器承載），注意，有許多較晚的語言通過底層的方式解決了數(shù)組插入和刪除時(shí)的時(shí)間浪費(fèi)，如PYTHON。

鏈表的基本思維是，利用結(jié)構(gòu)體的設(shè)置，額外開辟出一份內(nèi)存空間去作指針，它總是指向下一個(gè)結(jié)點(diǎn)，一個(gè)個(gè)結(jié)點(diǎn)通過NEXT指針相互聯(lián)系，串聯(lián)，這就形成了我們的鏈表。

（圖為單鏈表的一個(gè)結(jié)點(diǎn)結(jié)構(gòu)）

其中DATA為自定義的數(shù)據(jù)類型，可以是簡單的int型，也可以是復(fù)雜的struct結(jié)構(gòu)體類型，而NEXT為指向下一個(gè)鏈表結(jié)點(diǎn)的指針，通過訪問NEXT，可以引導(dǎo)我們?nèi)ピL問鏈表的下一個(gè)結(jié)點(diǎn)。

對(duì)于一連串的結(jié)點(diǎn)而言，就形成了我們的鏈表：

我們要進(jìn)行上文所說的插入刪除操作也就相當(dāng)簡單，只需要修改指針?biāo)赶虻膮^(qū)域就可以了，不需要進(jìn)行大量的數(shù)據(jù)移動(dòng)操作。

相比起數(shù)組，鏈表解決了數(shù)組不方便移動(dòng)，插入，刪除元素的弊端，但相應(yīng)的，鏈表付出了更加大的內(nèi)存犧牲換來的這些功能的實(shí)現(xiàn)。

上文介紹的是單鏈表，接下來的本章節(jié)會(huì)依次給各位介紹：單鏈表，雙鏈表，循環(huán)單鏈表，其功能不同但實(shí)現(xiàn)方式均大同小異。

（圖示為接下來學(xué)習(xí)的幾種鏈表的區(qū)別）