轉(zhuǎn)自：http://blog.csdn.net/oreo_go/article/details/52116214

一、線性表的定義

線性表：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列。

幾個(gè)關(guān)鍵的地方。
首先它是一個(gè)序列。也就是說，元素之間是有順序的，若元素存在多個(gè)，則第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，其他每個(gè)元素都只有一個(gè)前驅(qū)和后繼。

然后，線性表強(qiáng)調(diào)是有限的。事實(shí)上，在計(jì)算機(jī)中處理的對象都是有限的，那種無限的數(shù)列，只存在于數(shù)學(xué)的概念中。

如果用數(shù)學(xué)語言來定義。可如下：
**若將線性表記為(a1，…，ai-1，ai，ai+1，…，an)，則表中ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1，稱ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。當(dāng)i = 1，2，…，n-1時(shí)，ai有且僅有一個(gè)直接后繼，當(dāng)i = 2 , 3 , … , n時(shí)，ai有且僅有一個(gè)直接前驅(qū)。 **

所以線性表元素的個(gè)數(shù)n(n ≥ 0)定義為線性表長度，當(dāng)n=0時(shí)，稱為空表。

在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。

舉幾個(gè)例子，來判斷是否是線性表。
第一個(gè)：一年的星座列表，是不是線性表呢？

答：當(dāng)然是，星座通常都是白羊座開頭，雙魚座收尾，當(dāng)中的星座都有前驅(qū)后繼，而且一共才12個(gè)，所以完全符合線性表的定義。

第二個(gè)：公司的組織交媾，總經(jīng)理管理幾個(gè)總監(jiān)，每個(gè)總監(jiān)管理幾個(gè)經(jīng)理，每個(gè)經(jīng)理管理各自的下述和員工。這樣的組織架構(gòu)是不是線性關(guān)系呢？

答：不是，為什么不是呢？因?yàn)槊恳粋€(gè)元素，都有不止一個(gè)后繼，所以它不是線性表。

第三個(gè)：班級(jí)同學(xué)的友誼關(guān)系，是不是線性表呢？

答：不是，因?yàn)槊總€(gè)人都可以和多個(gè)同學(xué)建立友誼，不滿足線性的定義。

第四個(gè)：班級(jí)同學(xué)的點(diǎn)名冊，是不是線性表？是不是點(diǎn)名冊？

答：是，這和剛才的友誼關(guān)系是完全不同的，因?yàn)樗怯邢扌蛄?，也滿足類型相同特點(diǎn)，這個(gè)點(diǎn)名冊中，每個(gè)元素除學(xué)生的學(xué)號(hào)外，還可以有同學(xué)的姓名、性別、出生年月什么的，這其實(shí)就是我們之前將的數(shù)據(jù)項(xiàng)。在較復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。

二、線性表的抽象數(shù)據(jù)類型

線性表的抽象數(shù)據(jù)類型定義如下：

ADT 線性表(List)
Data
    線性表的數(shù)據(jù)對象集合為{a1,a2,....,an},每個(gè)元素的類型均為DataType。其中除了，第一個(gè)元素a1外，每一個(gè)元素有且只有一個(gè)直接前驅(qū)元素，除最后一個(gè)元素an外，每一個(gè)元素有且只有一個(gè)直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系。

Operation
    InitList(*L):初始化操作，建立一個(gè)空的線性表。
    ListEmpty(L):若線性表為空，返回true，否則返回false。
    ClearList(*L):線性表清空。
    GetElem(L,i,*e):將線性表L中第i個(gè)位置元素返回給e。
    LocateElem(L,e):在線性表L中查找與給定值e相等的元素，如果
        查找成功,返回該元素在表中的序列號(hào)；否則，返回0表示失敗。
    ListInsert(*L,i,e):在線性表的第i個(gè)位置插入元素e。
    ListDelete(*L,i,*e):刪除線性表L中的第i個(gè)元素，并用e返回其值
    ListLength(L):返回線性表L的元素個(gè)數(shù)。

對于不同的應(yīng)用，線性表的操作時(shí)不同的，上述操作時(shí)最基本的，問題中設(shè)計(jì)的關(guān)于線性表的更復(fù)雜操作，完全可以用這些基本操作的組合來實(shí)現(xiàn)。

比如，要實(shí)現(xiàn)兩個(gè)線性表集合A和B的并集操作。即要使得集合A = A ∪ B，說白了，就是把存在集合B中但并不存在中的數(shù)據(jù)元素插到A中即可。

仔細(xì)分析一下這個(gè)操作，發(fā)現(xiàn)我們只要循環(huán)集合B中的元素，判斷是否存在A中，若不存在，則插到A中即可。思路應(yīng)該是很容易想到的。

假設(shè)我們La表示集合A，Lb表示集合B，則實(shí)現(xiàn)代碼如下：

//將所有的在線性表Lb中但不在La中的元素插入到La中
void unionL(List *La , List Lb)
{
    int La_len,Lb_len,i;
    ElemType e;
    La_len = ListLength(*La);
    Lb_len = ListLength(*Lb);
    for(i = 0 ;i ≤ Lb;i++)
    {
        GetElem(Lb,i,*e);//取出Lb中第i個(gè)數(shù)據(jù)元素賦給e
        if(!LocateElem(*La,e))//La中不存在和e元素相同的數(shù)據(jù)元素
        {
            ListInsert(La,++La_len,e);//插入
        }
    }
}

這里我們對于union操作，用到了前面線性表基本操作ListLength、GetElem、LocateElem，ListLength等，可見，對于復(fù)雜的個(gè)性化的操作，其實(shí)就是把基本操作組合起來實(shí)現(xiàn)的。

三、線性表的順序存儲(chǔ)結(jié)構(gòu)

1.順序存儲(chǔ)定義

說了這么多的線性表，我們來看線性表的物理結(jié)構(gòu)第一種——順序存儲(chǔ)結(jié)構(gòu)。

線性表的順序存儲(chǔ)結(jié)構(gòu)，指定的是用一段地址連續(xù)的存儲(chǔ)單元一次存儲(chǔ)線性表的數(shù)據(jù)元素。

2.順序存儲(chǔ)方式

線性表的順序存儲(chǔ)方式，說白了，就是在內(nèi)存中找了一塊地方，把一定內(nèi)存空間占了，然后把相同數(shù)據(jù)類型的數(shù)據(jù)元素一次存在在里面。既然線性表的數(shù)據(jù)元素的類型都相同，所以用C語言的一維數(shù)組來實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)，即把第一個(gè)數(shù)據(jù)元素存儲(chǔ)到數(shù)組下表為0的位置中，接著把線性表相鄰的元素存儲(chǔ)在數(shù)組中相鄰的位置。

為了建立一個(gè)線性表，要在內(nèi)存中找一塊地，于是這塊地的第一個(gè)位置就非常關(guān)鍵，它是存儲(chǔ)空間的起始位置。

線性表中，我們估算這個(gè)線性表的最大存儲(chǔ)容量，建立一個(gè)數(shù)組，數(shù)組的長度就是最大存儲(chǔ)容量。

我們已經(jīng)有了起始位置，也有了最大的容量，于是我們可以在里面增加數(shù)據(jù)了。隨著數(shù)據(jù)的插入，我們線性表的長度開始變大，不過線性表的當(dāng)前長度不能超過存儲(chǔ)容量，即數(shù)組的長度。

來看線性表的順序存儲(chǔ)的結(jié)構(gòu)代碼。

 #define MAXSIZE 20 //存儲(chǔ)空間初始分配量
 typedef int ElemType;//ElemType根據(jù)實(shí)際情況而定，這里假設(shè)為int
 typedef struct
 {
     ElemType data[MAXSIZE];//數(shù)組存儲(chǔ)數(shù)據(jù)元素,最大值為MAXSIZE
     int length;//線性表當(dāng)前長度
 }SqList;

這里我們發(fā)現(xiàn)描述順序存儲(chǔ)結(jié)構(gòu)需要三個(gè)屬性：
①存儲(chǔ)空間的起始位置：數(shù)組data，它的存儲(chǔ)位置就是存儲(chǔ)空間的存儲(chǔ)位置。

②線性表的最大存儲(chǔ)容量：數(shù)組長度MaxSize。

③線性表的當(dāng)前長度：length。

3.數(shù)組長度與線性表長度區(qū)別

數(shù)組長度是存放線性表的存儲(chǔ)空間的長度，存儲(chǔ)空間分配完一般是不變的。

線性表長度是線性表中元素?cái)?shù)據(jù)的個(gè)數(shù)，隨著線性表插入和刪除操作的進(jìn)行，這個(gè)量是變化的。

在任意時(shí)刻，線性表的長度應(yīng)該小于等于數(shù)組的長度。

4.地址計(jì)算方法

線性表的起始是從1開始的，可數(shù)組卻是從0開始第一個(gè)下標(biāo)的，于是線性表中第i個(gè)元素，存儲(chǔ)在數(shù)組下標(biāo)為i - 1的位置。

用數(shù)組存儲(chǔ)順序表意味著要分配固定長度的數(shù)組空間，由于線性表中可以進(jìn)行插入和刪除操作，因此分配的數(shù)組空間要大于等于當(dāng)前線性表的長度。

由于每個(gè)數(shù)據(jù)元素，不管他是整型、實(shí)型還是字符型，它都是需要占用一定的存儲(chǔ)空間的。假設(shè)占用的是c個(gè)存儲(chǔ)單元，那么線性表中第i + 1個(gè)元素的存儲(chǔ)位置和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置滿足下列關(guān)系（LOC表示獲得存儲(chǔ)位置的函數(shù)）。

LOC(ai+1) = LOC(ai) + c

所以對于第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置可以由a1推算得出：

LOC(ai) = LOC(ai) + (i - 1) * c

通過這個(gè)公式，隨時(shí)可以算出線性表中任意位置的地址，不管他是第一個(gè)還是最后一個(gè)，都是相同的事件。那么我們對每個(gè)線性表位置的存入或者取出數(shù)據(jù)，對于計(jì)算機(jī)來說都是相等的時(shí)間，也就是一個(gè)常數(shù)，因此我們算法中學(xué)到的時(shí)間復(fù)雜度的概念來說，它的存取時(shí)間的性能為O(1)。我們通常把具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)稱為隨機(jī)存取結(jié)構(gòu)。

四、順序存儲(chǔ)結(jié)構(gòu)的插入與刪除

1.獲得元素操作

對于線性表的順序存儲(chǔ)結(jié)構(gòu)來說，我們要實(shí)現(xiàn)GetElem操作，即將線性表L中的第i個(gè)位置元素返回，其實(shí)是非常簡單的。就程序而言，只要第i個(gè)元素在下標(biāo)范圍內(nèi)，就是把數(shù)組第i - 1下表值返回即可。
來看代碼：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等
//初始條件：順序線性表L已經(jīng)存在，1 ≤ i ≤ ListLength(L)
//操作結(jié)果：用e返回L中第i個(gè)元素的值
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length == 0 || i < 1 || i > L.length)
        return ERROR;
    *e = L.data[i - 1];
    return OK;
}

注意這里返回值類型Status是一個(gè)整型，返回OK代表1，ERROR代表0。

2.插入操作

剛才我們也談到，這里的時(shí)間復(fù)雜度為O(1)。我們現(xiàn)在來考慮，如果我們要實(shí)現(xiàn)ListInsert(*L，i，e)，即在線性表L中第i個(gè)位置插入新元素e，應(yīng)該如何操作？

插入算法的思路：

①如果插入位置不合理，拋出異常；

②如果線性表長度大于等于數(shù)組長度，則拋出異?；騽?dòng)態(tài)增加容量；

③從最后一個(gè)元素開始向前遍歷到第i個(gè)元素，分別將它們都向后移一位；

④將要插入元素填入位置i處；

⑤表長加1。
實(shí)現(xiàn)代碼如下：

//初始條件:順序線性表L已存在,1 ≤ i ≤ ListLength(L)
//操作結(jié)果:在L的第i個(gè)位置插入新的數(shù)據(jù)元素e,L的長度加1
Status ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if(L->length == MAXSIZE)//當(dāng)線性表已滿
        return ERROR;
    if(i < 1 || i >L->length + 1)//當(dāng)i不在范圍內(nèi)時(shí)
    {
        return ERROR;
    }
    if(i <= L->length)//若插入數(shù)據(jù)位置不在表尾
    {
        for(k = L->length-1;k > i-1;k--)
        {
            L->data[k + 1] = L->data[k];
        }
    }
    L->data[i - 1] = e;//將新元素插入
    L->length++;
    return OK;
}

3.刪除操作

刪除算法的思路：
①如果刪除位置不合理，拋出異常；

②取出刪除元素；

③從刪除元素位置開始遍歷到最后一個(gè)元素位置，分別將它們向前移動(dòng)一個(gè)位置；

④表長減1。

實(shí)現(xiàn)代碼如下：

//初始條件:順序線性表L已經(jīng)存在，1 <= i <= ListLength(L)
//操作結(jié)果:刪除L的第i個(gè)元素,并用e返回其值,L的長度減1
Status ListDelete(SqList *L ,int i , ElemType *e)
{
    int k;
    if(L->length == 0)//線性表為空
        return ERROR;
    if(i < 1 || i > L->length)//刪除位置不正確
        return ERROR;
    *e = L->data[I];
    if(i < L->length)
    {
        for(k = i;k < L->length;k++)
            L->data[k - 1] = L->data[k];
    }
    L->length--;
    return OK;
}

現(xiàn)在，我們來分析一下，插入和刪除的事件復(fù)雜度。
現(xiàn)在我們來看最好的情況，如果一個(gè)元素要插入到最后一個(gè)位置，或者刪除最后一個(gè)位置，此時(shí)時(shí)間復(fù)雜度為O(1)，因?yàn)椴恍枰苿?dòng)元素的。

最壞的情況呢，如果元素要插入到第一個(gè)位置或者刪除第一個(gè)元素，此時(shí)時(shí)間復(fù)雜度是多少呢？那就意味著所有元素向后或者向前，所以這個(gè)時(shí)間復(fù)雜度為O(n)。

至于平均的情況，由于元素插入到第i個(gè)位置，或者刪除第i個(gè)元素，需要移動(dòng)n - i個(gè)元素，每個(gè)位置插入或刪除元素的可能性是相同的，也就是位置靠前，移動(dòng)元素多，位置靠后，移動(dòng)元素少。最終平均移動(dòng)次數(shù)和最中間那個(gè)元素的移動(dòng)次數(shù)相等，為(n - 1)/ 2。

根據(jù)時(shí)間復(fù)雜度的推導(dǎo)，平均時(shí)間復(fù)雜度還是O(n)。

這說明說明？線性表的順序存儲(chǔ)結(jié)構(gòu)，在存、讀數(shù)據(jù)時(shí)，不管是哪個(gè)位置，時(shí)間復(fù)雜度都是O(1)；而插入或刪除時(shí)，時(shí)間復(fù)雜度都是O(n)。這就說明，它比較適合元素個(gè)數(shù)不太變化，而更多是存取數(shù)據(jù)的應(yīng)用。

4線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)
①無須為表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間

②可以快速地存取表中任一位置的元素

缺點(diǎn)
①插入和刪除需要移動(dòng)大量元素

②當(dāng)線性表長度變化較大時(shí)，難以確定存儲(chǔ)空間的容量

③造成存儲(chǔ)空間的“碎片”

五、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1.線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。這就意味著，這些元素可以存在內(nèi)存未被占用的任意位置。

以前在順序結(jié)構(gòu)中，每個(gè)元素?cái)?shù)據(jù)只需要存儲(chǔ)數(shù)據(jù)元素信息就可以了。現(xiàn)在在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存數(shù)據(jù)元素信息外，還要存儲(chǔ)它的后繼元素的存儲(chǔ)地址。

因此，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后級(jí)元素ai+1之間的邏輯關(guān)系，對數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲(chǔ)直接后繼位置的域稱為指針域。指針域中存儲(chǔ)的信息稱作指針或鏈。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)(Node)。

n個(gè)結(jié)點(diǎn)(ai的存儲(chǔ)映像)鏈結(jié)成一個(gè)鏈表，即為線性表(a1,a2,….,an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，所以叫做單鏈表。單鏈表正是通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起。

對于線性表來說，總得有個(gè)頭有個(gè)尾，鏈表也不例外。我們把鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針，那么整個(gè)鏈表的存取就必須是從頭指針開始進(jìn)行了。之后的每一個(gè)結(jié)點(diǎn)，其實(shí)就是上一個(gè)的后繼指針指向的位置。

最后一個(gè)，當(dāng)然意味著直接后繼不存在了，所以我們規(guī)定，線性鏈表的最后一個(gè)結(jié)點(diǎn)指針為“空”（通常用NULL或“^”符號(hào)表示）。

有時(shí)，我們?yōu)榱烁臃奖愕貙︽湵磉M(jìn)行操作，會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線性表的長度等附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。

2.頭指針與頭結(jié)點(diǎn)的異同

頭指針與頭結(jié)點(diǎn)的異同點(diǎn)。
頭指針
① 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針

②頭指針具有標(biāo)識(shí)作用，所以常用頭指針冠以鏈表的名字

③無論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素。

頭結(jié)點(diǎn)
①頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一元素的結(jié)點(diǎn)之間，其數(shù)據(jù)域一般無意義。

②有了頭結(jié)點(diǎn)，對在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)，其操作與其它結(jié)點(diǎn)的操作就統(tǒng)一了。

③頭結(jié)點(diǎn)不一定是鏈表必須要素。

3.線性鏈表式存儲(chǔ)結(jié)構(gòu)代碼描述

若線性鏈表為空表，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡薄?/p>

單鏈表中，我們在C語言中可用結(jié)構(gòu)指針來描述。

//線性表的單鏈表存儲(chǔ)結(jié)構(gòu)
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;//定義LinkList

在這個(gè)結(jié)構(gòu)定義中，我們也就知道，結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結(jié)點(diǎn)地址的指針域組成。 假設(shè)p是指向線性表第i個(gè)元素的指針，則該結(jié)點(diǎn)ai的數(shù)據(jù)域我們可以用p->data來表示，p->data的值是一個(gè)數(shù)據(jù)元素，結(jié)點(diǎn)ai的指針可以用p->next來表示，p->next的值是一個(gè)指針。p->next指向誰呢？當(dāng)然是指向第i + 1個(gè)元素，即指向ai+1。也就是說p->data = ai，那么p->next->data=ai+1

六、單鏈表的讀取

在線性表的順序存儲(chǔ)結(jié)構(gòu)中，我們要計(jì)算任意一個(gè)元素的存儲(chǔ)位置使很容易的。但在單鏈表中，由于第i個(gè)元素到底在哪？沒辦法一開始就知道，必須從頭開始找。因此，對于單鏈表實(shí)現(xiàn)獲取第i個(gè)元素的操作GetElem，在算法上，相對麻煩一些。

獲得鏈表第i個(gè)數(shù)據(jù)的算法思路：
1. 聲明一個(gè)指針p指向鏈表第一個(gè)結(jié)點(diǎn)，初始化j從1開始。
2. 當(dāng)j < i 時(shí)，就遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn)，j累加1;
3. 若鏈表末尾p為空，則說明第i個(gè)結(jié)點(diǎn)不存在；
4. 否則查找成功，返回結(jié)點(diǎn)p的數(shù)據(jù)。
實(shí)現(xiàn)代碼如下：

//初始條件:順序線性表L已存在,1 ≤ i ≤ ListLength(L)
//操作結(jié)果:用e返回L中第i個(gè)數(shù)據(jù)元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;//聲明一指針
    p = L->next;//讓p指向鏈表L的第一個(gè)結(jié)點(diǎn)
    j = 1;//j為計(jì)數(shù)器
    while(p && j < i)//p不為空且計(jì)數(shù)器j還沒有等于i時(shí)，循環(huán)繼續(xù)
    {
        p = p->next;//讓p指向下也結(jié)點(diǎn)
        ++j;
    }
    if(p || j > i)
        return ERROR;//第i個(gè)結(jié)點(diǎn)不存在
    *e = p->data;//取第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)
    return OK;
}

說白了，就是從頭開始找，直到第i個(gè)結(jié)點(diǎn)為止。由于這個(gè)算法復(fù)雜度取決于i的位置，當(dāng)i = 1時(shí)，不需要變量，而當(dāng)i = n時(shí)則遍歷n - 1次才可以。因此最壞情況的時(shí)間復(fù)雜度是O(n)。

由于單鏈表的結(jié)構(gòu)沒有定義表長，所以不知道事先循環(huán)多少次，因此也就不方便使用for來控制循環(huán)。其主要核心思想是“工作指針后移”，這其實(shí)也是很多算法常用技術(shù)。

八、單鏈表的插入與刪除

1.單鏈表的插入

假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s，要實(shí)現(xiàn)結(jié)點(diǎn)p、p->next和s之間的邏輯關(guān)系的變化，只需要將s插到結(jié)點(diǎn)p和p->next之間即可。
根本不需要驚動(dòng)其他結(jié)點(diǎn)，只需要讓s->next和p->next的指針做一點(diǎn)改變。

//下面兩句不可交換順序
s->next = p->next;
p->next = s;

單鏈表第i個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路：
1. 聲明一指針p指向鏈表頭結(jié)點(diǎn)，初始化j從1開始;
2. 當(dāng)j < i時(shí)，就遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn),j累加1
3. 若到鏈表末尾p為空，則說明第i個(gè)結(jié)點(diǎn)不存在;
4. 若查找成功，在系統(tǒng)中生成一個(gè)空節(jié)點(diǎn)s；
5. 將數(shù)據(jù)元素e賦給s->data；
6. 單鏈表的插入標(biāo)準(zhǔn)語句s->next = p->next; p->next = s;
7. 返回成功

實(shí)現(xiàn)代碼算法如下：

//初始條件:順序線性表L已存在,1≤i≤ListLength(L)
//操作結(jié)果:在L中第i個(gè)結(jié)點(diǎn)位置之前插入新的數(shù)據(jù)元素,L的長度加1
Status ListInsert(LinkList *L , int i , ElemType e)
{
    int j = 1;
    LinkList p,s;
    p = *L;
    while( p && j < i) //尋找第I個(gè)結(jié)點(diǎn)
    {
        p = p->next;
        ++j;
    }
    if( !p || j > 1)
    {
        return ERROR;//第i個(gè)結(jié)點(diǎn)不存在
    }
    s = (LinkList)malloc(sizeof(Node));//生成新結(jié)點(diǎn)
    s->data = e;
    s->next = p->next;//將p的后繼結(jié)點(diǎn)賦值給s的后繼
    p->next = s;//將s賦給p的后繼
    return OK;
}

在這段算法代碼中，我們用到了C語言的malloc標(biāo)準(zhǔn)函數(shù)，它的作用就是生成一個(gè)新的結(jié)點(diǎn)，其類型與Node是一樣的，其實(shí)質(zhì)就是在內(nèi)存中開辟了一段空間，用了存放數(shù)據(jù)e的s結(jié)點(diǎn)。

2.單鏈表的刪除

現(xiàn)在我們再來看單鏈表的刪除。設(shè)存儲(chǔ)元素ai的結(jié)點(diǎn)為q，要實(shí)現(xiàn)將結(jié)點(diǎn)q刪除單鏈表的操作，其實(shí)就是將它的前繼結(jié)點(diǎn)的指針繞過，指向他的后繼結(jié)點(diǎn)即可。

我們所要做的，實(shí)際上就是一步，p->next = p->next->next;，用q來取代p->next即是：

q = p->next;
p->next = q->next;

也就是說把p的后繼結(jié)點(diǎn)改成p的后繼的后繼結(jié)點(diǎn)。

單鏈表第i個(gè)數(shù)據(jù)刪除結(jié)點(diǎn)的算法思路：
1. 聲明一指針p指向鏈表頭指針，初始化j從1開始；
2. 當(dāng)j < i時(shí)，就遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，i累加1；
3. 若到鏈表末尾p為空，則說明第i個(gè)結(jié)點(diǎn)不存在；
4. 否則查找成功，將欲刪除的結(jié)點(diǎn)p->next 賦給q；
5. 單鏈表的刪除標(biāo)準(zhǔn)與p->next = q->next；
6. 將q結(jié)點(diǎn)中的數(shù)據(jù)賦給e，作為返回;
7. 釋放q結(jié)點(diǎn)
8. 返回成功

實(shí)現(xiàn)代碼算法如下：

//初始條件:順序線性表L已存在,1≤ i ≤ListLength(L)
//操作結(jié)果:刪除L的i個(gè)結(jié)點(diǎn),并用e返回其值,L的長度減1
Status ListDelete(LinkList *L,int i,ElemType *e)
{
    int j;
    Link p,q;
    p = *L;
    j = 1;
    while(p->next && j < i)//遍歷尋找第i - 1個(gè)結(jié)點(diǎn)
    {
        p = p->next;
        ++j;
    }
    if( !(p->next) || j > i)
        return ERROR;//第i個(gè)結(jié)點(diǎn)不存在
    q = p->next;
    p->next = q->next;//將q的后繼賦給p的后繼
    *e = q->data;//將q結(jié)點(diǎn)中的數(shù)據(jù)給e
    free(q);//讓系統(tǒng)回收此結(jié)點(diǎn)，釋放內(nèi)存
    return OK;
}

分析一下剛才我們講解的單鏈表插入和刪除算法，我們發(fā)現(xiàn)，它們其實(shí)都是由兩部分組成：第一部分就是遍歷查找第i個(gè)結(jié)點(diǎn)；第二部分就是插入和刪除結(jié)點(diǎn)。

從整個(gè)算法來說，我們很容易推導(dǎo)出：它們的時(shí)間復(fù)雜度都是O(n)。
如果我們不知道第i個(gè)結(jié)點(diǎn)的指針位置，單鏈表數(shù)據(jù)結(jié)構(gòu)在插入和刪除操作上，與線下順序存儲(chǔ)結(jié)構(gòu)是沒有太大優(yōu)勢的。但如果，我們希望從第i個(gè)位置，插入10個(gè)結(jié)點(diǎn)，對于順序結(jié)構(gòu)意味著，每次都要移動(dòng)n - i個(gè)結(jié)點(diǎn)，每次都是O(n)。而單鏈表，我們只需在第一次時(shí)，找到第i個(gè)位置的指針，此時(shí)為O(n)，接下來只是簡單地通過賦值移動(dòng)指針而已，事件復(fù)雜度為O(1)。
顯然，對于插入和刪除數(shù)據(jù)越頻繁的操作，單鏈表的優(yōu)勢就越明顯。

八、單鏈表的整表創(chuàng)建

順序存儲(chǔ)結(jié)構(gòu)的創(chuàng)建，其實(shí)就是一個(gè)數(shù)組的初始化，即聲明一個(gè)類型和大小的數(shù)組并賦值的過程。而單鏈表和順序存儲(chǔ)結(jié)構(gòu)就不一樣，它不像順序存儲(chǔ)結(jié)構(gòu)這么幾種，它可以很散，是一種動(dòng)態(tài)結(jié)構(gòu)。對于每個(gè)鏈表來說，它所占用空間的大小和位置使不需要預(yù)先分配劃定的，可以根據(jù)系統(tǒng)的情況和實(shí)際的需求即可生成。

所以創(chuàng)建單鏈表的過程就是一個(gè)動(dòng)態(tài)生成鏈表的過程。即從“空表”的初始狀態(tài)起，一次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。
單鏈表整表創(chuàng)建的思路算法：

1. 聲明一指針p和計(jì)數(shù)器變量1；

2. 初始化一空鏈表；

3. 讓L的頭結(jié)點(diǎn)的指針指向NULL，即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表；

4. 循環(huán)：

   生成一新結(jié)點(diǎn)賦值給p;
   隨機(jī)生成一數(shù)字賦給p的數(shù)據(jù)域p->data;
   將p插到頭結(jié)點(diǎn)與前一個(gè)新節(jié)點(diǎn)之間的位置。

實(shí)現(xiàn)代碼如下：

//隨機(jī)產(chǎn)生n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈表線性表L(頭插法)
void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int I;
    srand(time(0));//初始化隨機(jī)數(shù)種子
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表
    for(i = 0;i < n;i++)
    {
        p = (LinkList)malloc(sizoef(Node));//生成新的結(jié)點(diǎn)
        p->data = rand() % 100 + 1;//隨機(jī)生成100以內(nèi)的數(shù)字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表頭
    }
}

這段代碼里，我們始終讓新結(jié)點(diǎn)在第一的位置上，我們把這種算法簡稱為頭插法。

可事實(shí)上，我們還可以把新結(jié)點(diǎn)放在最后。這才是排隊(duì)時(shí)的正常思維。我們每次新結(jié)點(diǎn)都插在終端結(jié)點(diǎn)的后面，這種算法稱之為尾插。

實(shí)現(xiàn)代碼算法如下：

//隨機(jī)產(chǎn)生n個(gè)元素的值,建立帶表頭結(jié)點(diǎn)的單鏈線性表L(尾插法)
void CreateListTail(LinkList *L,int n)
{
    LinkList p,r;
    int I;
    srand(time(0));//初始化隨機(jī)數(shù)種子
    *L = (LinkList)malloc(sizeof(Node));//為整個(gè)線性表
    r = *L;//r為指向尾部的結(jié)點(diǎn)
    for(i = 0;i < n;i++)
    {
        p = (Node *)malloc(sizeof(Node));//生成新結(jié)點(diǎn)
        p->data = rand() % 100 + 1;//隨機(jī)生成100以內(nèi)的數(shù)字
        r->next = p;//將表尾終端結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)
        r = p; //就那個(gè)當(dāng)前新結(jié)點(diǎn)定義為表尾終端結(jié)點(diǎn)
    }
    r->next = NULL;//表示當(dāng)前鏈表結(jié)束
}

注意L與r的關(guān)系，L指整個(gè)單鏈表，而r指向尾節(jié)點(diǎn)的變量，r會(huì)隨著循環(huán)不斷地變化結(jié)點(diǎn)，而L則是隨著循環(huán)增長為一個(gè)多結(jié)點(diǎn)的鏈表。

這里需要解釋一下，r->next = p的意思，其實(shí)就是將剛才的表尾終端結(jié)點(diǎn)r的指針指向新結(jié)點(diǎn)p。

九、單鏈表的整表刪除

當(dāng)我們不打算使用這個(gè)單鏈表時(shí)，我們需要把它銷毀，其實(shí)也就是在內(nèi)存中將它釋放掉，以便于留出空間給其他程序或軟件使用。

單鏈表整表刪除的算法思路如下：
1. 聲明一結(jié)點(diǎn)p和q；
2. 將第一個(gè)結(jié)點(diǎn)賦值給p；
3. 循環(huán)
將下一結(jié)點(diǎn)賦值給q;
釋放p;
將q賦值給p。

實(shí)現(xiàn)代碼算法如下:

//初始條件:順序線性表L已經(jīng)存在，操作結(jié)果：將L重置為空表
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;//p指向第一個(gè)結(jié)點(diǎn)
    while(p)//沒到表尾
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;//頭結(jié)點(diǎn)指針域?yàn)榭?    return OK;
}

十、單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)

簡單地對單鏈表結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)作對比。
1、存儲(chǔ)分配方式：
順序存儲(chǔ)結(jié)構(gòu)有一段連續(xù)的存儲(chǔ)單元依然存儲(chǔ)線性表的數(shù)據(jù)元素。
單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線性表的玩意。

2、時(shí)間性能：
查找：

• 順序存儲(chǔ)結(jié)構(gòu)O(1)
• 單鏈表O(n)

插入與刪除

• 順序存儲(chǔ)結(jié)構(gòu)需要平均移動(dòng)表長一半的元素，時(shí)間為O(n)
• 單鏈表在線出某位置的指針后，插入和刪除時(shí)間僅為O(1)

3、空間性能

• 順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間，分大了，浪費(fèi)，分小了易發(fā)生上溢。
• 單鏈表不需要分配存儲(chǔ)空間，只要有就可以分配，元素個(gè)數(shù)也不受限制。

通過上面的對比，我們可以得出一些經(jīng)驗(yàn)性的結(jié)論：

①
若線性表需要頻繁查找，很少進(jìn)入插入和刪除操作時(shí)，宜采用順序存儲(chǔ)結(jié)構(gòu)。
若需要頻繁插入和刪除時(shí)，宜采用單鏈表結(jié)構(gòu)。
比如游戲開發(fā)中，對于用戶注冊的個(gè)人信息，除了注冊時(shí)插入數(shù)據(jù)外，絕大多數(shù)情況下都是讀取，所以應(yīng)該考慮用順序存儲(chǔ)結(jié)構(gòu)。而游戲中的玩家的武器或者裝備列表，隨著玩家游戲過程中，可能隨時(shí)增加或刪除，此時(shí)應(yīng)該用單鏈表比較合適。當(dāng)然，這只是簡單地類比?，F(xiàn)實(shí)生活中的軟件開發(fā)，要考慮的問題會(huì)復(fù)雜得多。

②當(dāng)線性表中的元素個(gè)數(shù)變化較大或者根本不知道有多大時(shí)，最好用單鏈表結(jié)構(gòu)，這樣可以不用考慮存儲(chǔ)空間大小問題。
而如果事先知道線性表的大致長度，比如一年12個(gè)月，這種用順序存儲(chǔ)結(jié)構(gòu)效率會(huì)高很多。

總之，線性表的順序存儲(chǔ)結(jié)構(gòu)和單鏈表結(jié)構(gòu)各有其優(yōu)點(diǎn)，不是簡單地說哪個(gè)不好，需要根據(jù)實(shí)際情況，來綜合平衡采用哪種數(shù)據(jù)更能滿足和達(dá)到需求和性能。

十一、靜態(tài)鏈表

C語言具有指針能力，使得它可以非常容易地操作內(nèi)存中的地址和數(shù)據(jù)，這比其他高級(jí)語言更加方便靈活。
后來的面向?qū)ο笳Z言，如Java、C#等，雖不使用指針，但因?yàn)閱⒂昧藢ο笠脵C(jī)制，從某種角度上也間接實(shí)現(xiàn)了指針的某些作用。但對于一些語言，如Basic、Fortran等早期的編程高級(jí)語言，由于沒有指針，鏈表結(jié)構(gòu)就沒辦法實(shí)現(xiàn)。

有人想出用數(shù)組來代替指針，來描述鏈表。

首先我們用數(shù)組的元素都是由兩個(gè)數(shù)據(jù)域組成，data和cur。也就是說，數(shù)組的每個(gè)下表都對應(yīng)一個(gè)data和一個(gè)cur。數(shù)據(jù)域data，用來存放數(shù)據(jù)元素，也就是通常我們要處理的數(shù)據(jù)；而cur相當(dāng)于單鏈表中的next指針，存放該元素后繼在數(shù)組中的下表，我們把cur叫做游標(biāo)。

我們把這種用數(shù)組描述的鏈表叫靜態(tài)鏈表，這種描述方法還有起名叫做游標(biāo)實(shí)現(xiàn)法。

為了我們方便插入數(shù)據(jù)，我們通常會(huì)把數(shù)組建立得大一些，以便有一些空閑空間可以方便插入不至于溢出。

//線性表的靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)
#define MAXSIZE 1000//假設(shè)鏈表的最大長度1000
typedef struct
{
    ElemType data;
    int cur;//游標(biāo)(Cursor),為0時(shí)表示無指向
}Component,StaticLinkList[MAXSIZE];

另外我們對數(shù)組的第一個(gè)和最后一個(gè)元素作為特殊元素處理，不存數(shù)據(jù)。我們通常把未被使用的數(shù)組元素稱為備用鏈表。而數(shù)組第一個(gè)元素，即下標(biāo)為0的元素的cur就存放備用鏈表的第一個(gè)結(jié)點(diǎn)的下表;而數(shù)組的最后一個(gè)元素的cur則存放第一個(gè)有數(shù)值的元素的下表，相當(dāng)于單鏈表中的頭結(jié)點(diǎn)作用，當(dāng)整個(gè)鏈表為空時(shí)，則為02。

//將一維數(shù)組space中個(gè)分量鏈成一備用鏈表
//space[0].cur為頭指針，"0"表示空指針
Status InitList(StaticLinkList space)
{
    int I;
    for(i = 0;i < MAXSIZE - 1;i++)
        space[i].cur = i + 1;
    space[MAXSIZE - 1].cur = 0;//目前靜態(tài)鏈表為空
    return OK;
}

1.靜態(tài)鏈表的插入操作

靜態(tài)鏈表中要解決的是：如何用靜態(tài)模擬動(dòng)態(tài)鏈表結(jié)構(gòu)的存儲(chǔ)空間的分配，需要時(shí)申請，不需要時(shí)釋放。

我們前面說過，在動(dòng)態(tài)鏈表中，結(jié)點(diǎn)的申請和釋放分別借用malloc()和free()兩個(gè)函數(shù)來實(shí)現(xiàn)。在靜態(tài)鏈表中，操作的是數(shù)組，不存在像動(dòng)態(tài)鏈表一樣的申請和釋放問題，所以我們需要自己實(shí)現(xiàn)這兩個(gè)函數(shù)。

為了辨明數(shù)組中哪些分量未被使用，解決的辦法是將所有未被使用過的以及已被刪除的分量用游標(biāo)鏈成一個(gè)備用的鏈表，每當(dāng)進(jìn)行插入時(shí)，便可從備用鏈表上取得第一個(gè)結(jié)點(diǎn)作為待插入的新結(jié)點(diǎn)。

//若備用空間鏈表為空，則返回分配的結(jié)點(diǎn)下表，否則返回0
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;//當(dāng)前數(shù)組的第一個(gè)元素的Cur存的值
    if(space[0].cur)
    {
        space[0].cur = space[i].cur;//由于要拿出一個(gè)分量來使用
                        //所以我們,就得把它的下一個(gè)分量用作備用
    }
    return I;
}

插入元素

//在L中第i個(gè)元素之前插入新的數(shù)據(jù)元素e
Status ListInsert(StaticLinkList L, int i,ElemType e)
{
    int j,k,l;
    k = MAX_SIZE - 1;//注意k首先是最后一個(gè)元素的下表
    if(i < 1 || i > ListLength(L) + 1)
        return ERROR;
    j = Malloc_SSL(L);//獲得空閑分量的下標(biāo)
    if(j)
    {
        L(j).data = e;//將數(shù)據(jù)賦值給此分量的下表
        for(l = 1;l <= i - 1;l++)//相當(dāng)于循環(huán)鏈表，找到第i-1位
        {
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;//新的第i個(gè)元素元素指向原本第i個(gè)元素
        L[k].cur = j;//第i - 1個(gè)元素指向新的第i個(gè)元素
        return OK;
    }
    return ERROR;
}

就這樣，我們實(shí)現(xiàn)了在數(shù)組中，實(shí)現(xiàn)不移動(dòng)元素，卻插入了數(shù)據(jù)的操作。

2.靜態(tài)鏈表的刪除操作

和前面一樣，刪除元素時(shí)，原來是需要釋放結(jié)點(diǎn)的函數(shù)free()。我們也要自己實(shí)現(xiàn)它。

//刪除在L中第i個(gè)數(shù)據(jù)元素e
Status ListDelete(StaticLinkList L,int i)
{
    int j , k;
    if(i < 1 || i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 1;
    for(j = 1;j < = i - 1;j++)//相當(dāng)于遍歷鏈表
    {
        k = L[k].cur;
    }
    j = L[k].cur;//把要?jiǎng)h除的數(shù)組下標(biāo)賦值給j
    Free_SLL(L,j);//調(diào)用刪除函數(shù)
    return OK;
}

//將下表為k的空閑結(jié)點(diǎn)回收到備用鏈表
void Free_SSL(StaticLinkList space,int k)
{
   space[k] = space[0].cur;//把原來第一位指向的下標(biāo)賦給新第一位
   space[0].cur = k;//要?jiǎng)h除的分量賦給第一個(gè)元素cur
}

靜態(tài)鏈表也就是相應(yīng)其他操作的相關(guān)實(shí)現(xiàn)。比如ListLength

//初始條件:靜態(tài)鏈表L已存在。操作結(jié)果:返回L中數(shù)據(jù)元素個(gè)數(shù)
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while(i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

3.靜態(tài)鏈表優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：在插入和刪除操作時(shí)，只要修改游標(biāo)，不需要移動(dòng)元素，從而改進(jìn)了在順序存儲(chǔ)結(jié)構(gòu)中的插入和刪除操作需要移動(dòng)大量元素的缺點(diǎn)。

缺點(diǎn)：
①?zèng)]有解決連續(xù)存儲(chǔ)分配帶來表長難以確定的問題
②失去了順序存儲(chǔ)結(jié)構(gòu)隨機(jī)存儲(chǔ)的特性

十二、循環(huán)鏈表

對于單個(gè)鏈表，由于每個(gè)結(jié)點(diǎn)只存儲(chǔ)了向后的指針，到了尾標(biāo)志就停止了向后鏈的操作，這樣當(dāng)中某一結(jié)點(diǎn)就無法找到它的前驅(qū)結(jié)點(diǎn)了。

將單鏈表中終端結(jié)點(diǎn)的指針由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成一個(gè)環(huán)， 這種頭尾相接的單鏈表稱為單循環(huán)鏈表，簡稱循環(huán)鏈表。

循環(huán)鏈表解決了一個(gè)很麻煩的問題，如何從當(dāng)中一個(gè)結(jié)點(diǎn)出發(fā)，訪問到鏈表的全部結(jié)點(diǎn)。

循環(huán)鏈表和單鏈表的主要差異就是在于循環(huán)的判斷條件上，原來是判斷p->next是否為空，現(xiàn)在則是p->next不等于頭結(jié)點(diǎn)，則循環(huán)未結(jié)束。

十三、雙向鏈表

在單鏈表中，有了next指針，這就使得我們要查找下一結(jié)點(diǎn)的事件復(fù)雜度為O(1)。可是如果我們要查找的是上一節(jié)點(diǎn)的話，那最壞的時(shí)間復(fù)雜度就是O(n)了，因?yàn)槲覀兠看味家獜念^開始遍歷尋找。

為了克服單向性這一缺點(diǎn)，設(shè)計(jì)出了雙向鏈表。雙向鏈表(double linked list)是在單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域。所以在雙向鏈表中的結(jié)點(diǎn)都有兩個(gè)指針域，一個(gè)指向直接后繼，一個(gè)指向直接前驅(qū)。

//線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)
typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior;//直接前驅(qū)指針
    struct DuLNode *next;//直接后繼指針
}DulNode,*DuLinkList;

既然單鏈表可以有循環(huán)，那么雙向鏈表當(dāng)然可以是循環(huán)表。

由于是雙向鏈表，對于鏈表中某一結(jié)點(diǎn)p，它的后繼的前驅(qū)是它自己。它的前驅(qū)的后繼自然也是它自己。即：

p->next->prior = p = p->prior->next

插入操作時(shí)，其實(shí)并不復(fù)雜，但是順序很重要。
假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s，要實(shí)現(xiàn)將結(jié)點(diǎn)s插入到p和p->next之間需要下面幾部。

s->prior = p;//把p賦給s的前驅(qū)
s->next = p->next;//把p->next賦給s的后繼
p->next->prior = s;//把s賦給p->next的前驅(qū)
p->next = s;//把s賦給p的后繼

如要?jiǎng)h除結(jié)點(diǎn)p，只要下面兩步驟。

p->prior->next = p->next;//把p->next賦給p->prior的后繼
p->next->prior = p->prior;//把p->proir賦給p->next的前驅(qū)
free(p);//釋放p的空間

雙向鏈表對于單鏈表來說，要更復(fù)雜一些，對于插入和刪除時(shí)，需要小心。
另外由于它每個(gè)結(jié)點(diǎn)需要幾輪兩份指針，所以在空間上是要占用略多一些的。不過由于良好的對稱性，使得對某個(gè)結(jié)點(diǎn)的前后結(jié)點(diǎn)的操作，帶來了方便，可以有效提高算法的時(shí)間性能。

說白了，也就是空間換時(shí)間。