在數(shù)據(jù)結(jié)構(gòu)中，根據(jù)不同的數(shù)據(jù)組織方式可以分為四類基本邏輯結(jié)構(gòu)(關(guān)系)：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)(網(wǎng)狀結(jié)構(gòu));根據(jù)存儲(chǔ)結(jié)構(gòu)可以分為：順序存儲(chǔ)、離散存儲(chǔ)。

　　鏈表是以線性結(jié)構(gòu)加上離散存儲(chǔ)組成，或者說是線性表的鏈?zhǔn)酱鎯?chǔ)，是各個(gè)對(duì)象按照線性順序排列的數(shù)據(jù)結(jié)構(gòu)，鏈表元素的線性順序是由對(duì)象里面的指針域決定的，所以在鏈?zhǔn)酱鎯?chǔ)中不僅要存數(shù)據(jù)元素的信息外，還要存儲(chǔ)它后一個(gè)元素的存儲(chǔ)地址來表示來表示每個(gè)元素和它之后的下一個(gè)元素的邏輯關(guān)系。鏈表為元素集合提供了一種簡單靈活的的表示方式，解決了順序表插入和刪除時(shí)需要移動(dòng)大量元素的(下面會(huì)講到)。

　　把n個(gè)數(shù)據(jù)元素用線性表的鏈?zhǔn)酱鎯?chǔ)這種數(shù)據(jù)結(jié)構(gòu)，通常可以表示如圖形式

　　鏈表可以有多種形式。它可以是單鏈接的或雙鏈接的，可以是以排序的或是未排序的，可以是循環(huán)的或非循環(huán)的

　　鏈表的操作：

　　在實(shí)現(xiàn)鏈表的通常情況下會(huì)給鏈表加上一個(gè)哨兵節(jié)點(diǎn)，來讓代碼更簡單些，哨兵是一個(gè)啞對(duì)象，其作用只有簡化邊界條件的處理，哨兵節(jié)點(diǎn)位置是在第一個(gè)元素結(jié)點(diǎn)之前(哨兵結(jié)點(diǎn)在插入、刪除元素為第一個(gè)元素時(shí)可以簡化操作)。我們把指向第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針，第一個(gè)結(jié)點(diǎn)叫做頭節(jié)點(diǎn)(即哨兵結(jié)點(diǎn))。

　　1、 創(chuàng)建空鏈表

　　2、 鏈表查找

　　從鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷是否為第i結(jié)點(diǎn)，若是則返回該結(jié)點(diǎn)的指針，否則查找下一結(jié)點(diǎn),依次類推

　　3、 鏈表插入

　　獲取結(jié)點(diǎn)ai-1的指針p(ai 之前驅(qū))，然后申請(qǐng)一個(gè)q結(jié)點(diǎn)，并將其插入p指向的結(jié)點(diǎn)之后

　　4、 鏈表刪除

　　找到結(jié)點(diǎn)ai的前驅(qū)，將結(jié)點(diǎn)ai刪除之

　　在鏈表的操作中，插入和刪除操作就只是改變了幾個(gè)指針的指向，時(shí)間復(fù)雜度都為O(1)，所以越是插入刪除操作越頻繁的數(shù)據(jù)集合采用鏈表的方式存儲(chǔ)效率越高。