1.1.4 線性鏈表

本節(jié)主要考查線性鏈表的存儲方式和基本操作。

1.線性表的鏈?zhǔn)酱鎯?/span>

在定義的鏈表中，若只含有一個指針域來存放下一個元素地址，稱這樣的鏈表為單鏈表或線性鏈表，如圖1-4所示。

在鏈?zhǔn)酱鎯Ψ绞街校竺總€節(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針用于指向該節(jié)點的前一個或后一個節(jié)點（即前件節(jié)點或后件節(jié)點）。

（1）線性鏈表的存儲結(jié)構(gòu)

用一組任意的存儲單元來依次存放線性表的節(jié)點，這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至可以是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中節(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示節(jié)點間的邏輯關(guān)系，在存儲每個節(jié)點值的同時，還必須存儲指示其后件節(jié)點的地址（或位置）信息，這個信息稱為指針（Pointer）或鏈（Link）。這兩部分組成了鏈表中的節(jié)點結(jié)構(gòu)，鏈表正是通過每個節(jié)點的鏈域?qū)⒕€性表的n個節(jié)點按其邏輯次序鏈接在一起。由于上述鏈表的每一個節(jié)點只有一個鏈域，故將這種鏈表稱為單鏈表（Single Linked）。

顯然，單鏈表中每個節(jié)點的存儲地址存放在其前驅(qū)節(jié)點Next域中，而開始節(jié)點無前驅(qū)節(jié)點，故應(yīng)設(shè)頭指針HEAD指向開始節(jié)點。同時，由于終端節(jié)點無后繼節(jié)點，故終端節(jié)點的指針域為空，即NULL。

（2）線性鏈表的基本運算

線性鏈表的基本運算包括在線性鏈表中查找指定元素、在線性鏈表中插入元素、在線性鏈表中刪除元素。

1）在線性鏈表中查找指定元素：在對線性鏈表進(jìn)行插入或刪除的運算中，總是首先需要找到插入或刪除的位置，這就需要對線性鏈表進(jìn)行掃描查找，在線性鏈表中尋找包含指定元素的前一個節(jié)點。

在鏈表中，查找是否有節(jié)點值等于給定值x的節(jié)點，若有的話，則返回首次找到的其值為x的節(jié)點的存儲位置；否則返回NULL。查找過程從開始節(jié)點出發(fā)，順著鏈表逐個將節(jié)點的值與給定值x做比較。

2）在線性鏈表中插入元素：線性鏈表的插入是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性鏈表中插入一個新元素。

插入運算是將值為x的新節(jié)點插入到表的第i-1個節(jié)點和第i個節(jié)點之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新節(jié)點*p，并令節(jié)點p的指針域指向新節(jié)點，新節(jié)點的指針域指向節(jié)點ai。

由線性鏈表的插入過程可以看出，由于插入的新節(jié)點取自于可利用棧，因此，只要可利用棧不空，在線性鏈表插入時總能取到存儲插入元素的新節(jié)點，不會發(fā)生“上溢”的情況。而且，由于可利用棧是公用的，多個線性鏈表可以共享它，從而可很方便地實現(xiàn)存儲空間的動態(tài)分配。另外，線性鏈表在插入過程中不發(fā)生數(shù)據(jù)元素移動的現(xiàn)象，只要改變有關(guān)節(jié)點的指針即可，從而提高了插入的效率。

3）在線性鏈表中刪除元素：線性鏈表的刪除是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性鏈表中刪除包含指定元素的節(jié)點。

刪除運算是將表的第i個節(jié)點刪去。因為在單鏈表中節(jié)點ai的存儲地址是在其直接前驅(qū)節(jié)點ai-1的指針域Next中，所以必須先找到ai-1的存儲位置p，然后令p->Next指向ai的直接后繼節(jié)點，即把ai從鏈上摘下，最后釋放節(jié)點ai的空間。

從線性鏈表的刪除過程可以看出，從線性鏈表中刪除一個元素后，不需要移動表中的數(shù)據(jù)元素，只要改變被刪除元素所在節(jié)點的前驅(qū)節(jié)點的指針域即可。另外，可利用棧收集計算機中所有的空閑節(jié)點，當(dāng)從線性鏈表中刪除一個元素后，該元素的存儲節(jié)點就變?yōu)榭臻e，應(yīng)將空閑節(jié)點送回到可利用棧。

2.雙向鏈表的結(jié)構(gòu)及其基本運算

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)節(jié)點中都有兩個指針，分別指向直接后繼節(jié)點和直接前驅(qū)節(jié)點，如圖1-5所示。所以，從雙向鏈表中的任意一個節(jié)點開始，都可以很方便地訪問它的前驅(qū)節(jié)點和后繼節(jié)點。

（1）雙向鏈表的基本運算

1）插入：在雙向鏈表的第i個元素前插入一個新節(jié)點的時候，首先，找到待插入的位置，用指針p指向該節(jié)點；然后，將新節(jié)點的前驅(qū)指針指向p節(jié)點的前一個節(jié)點；之后，將p節(jié)點的前一個節(jié)點的后驅(qū)指針指向新的節(jié)點；接下來，將新節(jié)點的后驅(qū)指針指向p節(jié)點；最后，將p節(jié)點的前驅(qū)指針指向新節(jié)點。

2）刪除：在雙向鏈表中刪除一個節(jié)點時，可用指針p指向該節(jié)點。首先，將p節(jié)點的前一個節(jié)點的Next指向p節(jié)點的下一個節(jié)點；然后，將p的下一個節(jié)點的前驅(qū)指針指向p的上一個節(jié)點。

（2）雙鏈表的結(jié)構(gòu)及其基本運算

在前面所討論的線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對于空表和對第一個節(jié)點的處理必須單獨考慮，使空表與非空表的運算不統(tǒng)一。

因此，可以考慮建立這樣的鏈表，具有單鏈表的特征，但又不需要增加額外的存儲空間，僅對表的鏈接方式稍做改變，使得對表的處理更加方便靈活。從單鏈表可知，最后一個節(jié)點的指針域為NULL，表示單鏈表已經(jīng)結(jié)束。如果將單鏈表最后一個節(jié)點的指針域改為存放鏈表中頭節(jié)點（或第一個節(jié)點）的地址，就使得整個鏈表構(gòu)成一個環(huán)，又沒有增加額外的存儲空間，而滿足這樣條件的鏈表叫循環(huán)鏈表。

循環(huán)鏈表具有以下兩個特點：

1）在循環(huán)鏈表中增加了一個表頭節(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的節(jié)點。循環(huán)鏈表的頭指針指向表頭節(jié)點。

2）循環(huán)鏈表中最后一個節(jié)點的指針域不是空，而是指向表頭節(jié)點。即在循環(huán)鏈表中，所有節(jié)點的指針構(gòu)成了一個環(huán)狀鏈。

在循環(huán)鏈表中，只要指出表中任何一個節(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的節(jié)點，而線性單鏈表做不到這一點。

由于在循環(huán)鏈表中設(shè)置了一個表頭節(jié)點，因此，在任何情況下，循環(huán)鏈表中至少有一個節(jié)點存在，從而使空表的運算與非空表統(tǒng)一。