知識(shí)回顧
? ? ? ? 到這里我們已經(jīng)了解到線性表是具有相同數(shù)據(jù)類型的有限個(gè)數(shù)據(jù)元素序列，而線性表的順序存儲(chǔ)也就是順序表，順序表的存儲(chǔ)形式十分直觀，我們?cè)趯?shí)現(xiàn)時(shí)使用數(shù)組進(jìn)行實(shí)現(xiàn)，但順序表在插入或者刪除元素時(shí)需要移動(dòng)大量元素，那么怎么樣才能在插入刪除元素時(shí)不需要大費(fèi)周章的移動(dòng)如此之多的元素呢？為了解決這個(gè)問題，今天我們就來繼續(xù)了解一下線性表的鏈?zhǔn)酱鎯?chǔ)——鏈表。
單鏈表定義
? ? ? ? 線性表的鏈?zhǔn)酱鎯?chǔ)又叫單鏈表，既然是屬于線性表的一種存儲(chǔ)方式，那么其應(yīng)該滿足線性表的特征（具有相同數(shù)據(jù)類型的有限個(gè)數(shù)據(jù)元素序列）。
????????那么什么是鏈?zhǔn)酱鎯?chǔ)呢？我們不難想象，就像鏈條一樣，我們存在很多個(gè)相同的結(jié)點(diǎn)，這些結(jié)點(diǎn)之間進(jìn)行相連最終稱為一個(gè)鏈條；那么鏈?zhǔn)酱鎯?chǔ)也跟其類似，其也是有很多個(gè)相同的結(jié)點(diǎn)所組成，之后我們?cè)趯⑵浣Y(jié)點(diǎn)按次序逐個(gè)串聯(lián)，這樣就可以形成一個(gè)鏈表。
? ? ? ? 不過這樣的定義顯然是不準(zhǔn)確的，我們線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)指用一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的)?；既然我們不對(duì)其存儲(chǔ)單元做連續(xù)的要求的話，我們應(yīng)該去設(shè)法建立其數(shù)據(jù)間的存儲(chǔ)關(guān)系；那么為了保持鏈表中的元素和其下一個(gè)元素??之間的邏輯關(guān)系，那么對(duì)于數(shù)據(jù)元素??來說，其不僅需要存儲(chǔ)其本身的信息，還需要開辟一塊空間去存放其直接后續(xù)的信息（也就是直接后續(xù)的存儲(chǔ)位置）；那么我們?cè)谠O(shè)計(jì)時(shí)，就可以使用指針去指向該元素的直接后續(xù)元素存儲(chǔ)位置，這樣在查找時(shí)就可以通過指針去直接查找出當(dāng)前元素的直接后續(xù)元素；所以我們的數(shù)據(jù)元素并不單單指的是其本身的信息，而是由這兩個(gè)部分同時(shí)構(gòu)成其數(shù)據(jù)元素???（我們稱其為 結(jié)點(diǎn) ）。
定義單鏈表結(jié)點(diǎn)類型
? ? ? ? 我們已經(jīng)了解到其結(jié)點(diǎn)的構(gòu)成，那么我們?cè)趯?shí)現(xiàn)時(shí)就需要使用代碼去構(gòu)造出其結(jié)點(diǎn)類型。
//結(jié)點(diǎn)
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList; ? ? ? ? ?這里我們同樣使用struct關(guān)鍵字定義一個(gè)新類型，通過前面的分析，我們不難觀察出其中需要一個(gè)data存放數(shù)據(jù)本身，因此其類型也就和我們需要存放數(shù)據(jù)本身類型一致即可；之后我們需要存放一個(gè)指針去存放下一個(gè)結(jié)點(diǎn)的地址，其類型自然也就是我們struct新定義的類型了。
如何增加新結(jié)點(diǎn)
? ? ? ? 前面我們已經(jīng)可以將鏈表中單個(gè)結(jié)點(diǎn)的數(shù)據(jù)類型定義出來了，可是這里我們只是存在這個(gè)類型，但我們?cè)趯?shí)際的使用中是需要不斷的開辟新的空間去存放這一個(gè)個(gè)的結(jié)點(diǎn)；那么我們就需要了解如何去添加新結(jié)點(diǎn)（開辟出一個(gè)新空間去存放新節(jié)點(diǎn)的數(shù)據(jù)）。
? ? ? ? 這里我們需要使用到malloc函數(shù)去申請(qǐng)一片新的內(nèi)存空間，下面的代碼也就是使用malloc函數(shù)去申請(qǐng)一個(gè)新的內(nèi)存空間存放結(jié)點(diǎn)；下面的代碼中malloc內(nèi)部寫明的是需要開辟空間的大小，這里也就是使用sizeof求出我們前面定義新類型的大?。ㄔ谶@里也就是int + LNode*），至于malloc前面的括號(hào)則是C++中的強(qiáng)制類型轉(zhuǎn)換，將其轉(zhuǎn)換為LNode * 類型。
LNode * p = (LNode *) malloc(sizeof(LNode));? ? ? ? 由于單鏈表的元素都是一個(gè)個(gè)單獨(dú)的結(jié)點(diǎn)，且其元素離散的分布在存儲(chǔ)空間之中，我們只能通過指針去按順序一個(gè)個(gè)尋找其元素，因此單鏈表是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)?（也就是不可以直接找到表中的某個(gè)特定的結(jié)點(diǎn)）。
分析LNode和*LinkList
? ? ? ? 我們?cè)谟^察結(jié)點(diǎn)類型的構(gòu)造時(shí)會(huì)發(fā)現(xiàn)，其存在兩個(gè)命名（LNode，*LinkList）?，對(duì)于這兩個(gè)實(shí)際上存在這樣的關(guān)系：
LNode * = LinkList? ? ? ? 既然這樣為什么這里我們要去分別起兩個(gè)名字呢？其實(shí)只有一個(gè)也是可以完成該鏈表的代碼實(shí)現(xiàn)的，只不過為了提升我們代碼的可讀性，也就是方便我們以后在閱讀代碼時(shí)可以更好的理解，我們?cè)谶@里使用這兩個(gè)命名。
? ? ? ? 在這里我們?nèi)绻诖a中想要，強(qiáng)調(diào)我們傳入或者返回的是一個(gè)單鏈表，需要使用LinkList；如果我們想要強(qiáng)調(diào)傳入或者返回的是一個(gè)結(jié)點(diǎn)，需要使用LNode *;通過這樣分辨，我們可以很好的將代碼中的結(jié)點(diǎn)和鏈表區(qū)分開，提高我們代碼的閱讀性。
單鏈表頭結(jié)點(diǎn)的分析
? ? ? ? 在鏈表中，我們通常需要一個(gè)頭指針去標(biāo)識(shí)一個(gè)鏈表，其指向我們鏈表的頭部，如果單鏈表的頭指針為NULL，也就意味著此時(shí)為一個(gè)空鏈表；此時(shí)為了操作的方便我們可以選擇去在頭指針后加上一個(gè)空的結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)被稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)數(shù)據(jù)域不需要設(shè)置任何信息，當(dāng)然也可以去記錄表長。
不帶頭結(jié)點(diǎn)的單鏈表
? ? ? ? 如果我們不設(shè)置頭節(jié)點(diǎn)的話，我們?cè)趩捂湵沓跏蓟瘯r(shí)其頭指針將直接指向NULL，此時(shí)也就說明其單鏈表為空，當(dāng)我們后續(xù)插入元素時(shí)，再更改其頭指針的指向即可。?
?
帶頭結(jié)點(diǎn)的單鏈表
? ? ? ? 對(duì)于含有頭結(jié)點(diǎn)的指針，我們的頭指針就需要指向頭結(jié)點(diǎn)，而頭結(jié)點(diǎn)指向NULL才表明我們的鏈表為空，當(dāng)然使用這種方法我們?cè)偬砑咏Y(jié)點(diǎn)時(shí)就只需要更改頭結(jié)點(diǎn)的指向即可，不需要更改頭指針的指向（其主要原因也是其頭部已經(jīng)固定，就是我們的頭結(jié)點(diǎn)）。
兩種方式的分析?
????????不論鏈表是否帶頭結(jié)點(diǎn)，我們的頭指針始終指向鏈表的第一個(gè)結(jié)點(diǎn)，只不過頭結(jié)點(diǎn)是帶頭結(jié)點(diǎn)鏈表的第一個(gè)結(jié)點(diǎn)，只不過該結(jié)點(diǎn)不存儲(chǔ)信息。
? ? ? ? 如果單鏈表中不帶頭結(jié)點(diǎn)，我們?cè)趯懘a時(shí)相對(duì)麻煩，對(duì)第一個(gè)數(shù)據(jù)結(jié)點(diǎn)和后續(xù)數(shù)據(jù)結(jié)點(diǎn)的 處理需要用不同的代碼邏輯 對(duì)空表和非空表的處理需要用不同的代碼邏輯。
而使用頭結(jié)點(diǎn)會(huì)使我們?cè)谑褂脮r(shí)更加方便：
- 由于第一個(gè)數(shù)據(jù)結(jié)點(diǎn)位置被存放在頭結(jié)點(diǎn)的指針域，因此在鏈表上第一個(gè)位置上的操作就與在其他位置上的操作一致，不需要特殊處理。
- 不論鏈表是否為空，其頭結(jié)點(diǎn)都是指向頭結(jié)點(diǎn)的非空指針（空表中的頭結(jié)點(diǎn)指針域?yàn)榭眨?，因此空表和非空表的處理也就得到了統(tǒng)一。???
????????因此我們可以發(fā)現(xiàn) 使用頭結(jié)點(diǎn)可以避免掉我們不少的麻煩。
單鏈表的基本操作實(shí)現(xiàn)
? ? ? ? 既然我們了解了單鏈表，也知道了其類型的定義，那么接下來我們就需要嘗試著去實(shí)現(xiàn)它的功能。
單鏈表的插入
? ? ? ? ?既然要學(xué)習(xí)一個(gè)鏈表，那么首先我們就要知道如何在鏈表中添加元素，也就是下面我們所學(xué)習(xí)的單鏈表的插入。
? ? ? ? 通過上文可知，我們的單鏈表分為含頭結(jié)點(diǎn)與不含頭結(jié)點(diǎn)的兩種單鏈表，不同的單鏈表在執(zhí)行有些插入操作的方法也存在一些差異。
? ? ? ? 對(duì)于插入操作我們?cè)谶@里主要介紹：按位序插入、指定結(jié)點(diǎn)的后插、指定結(jié)點(diǎn)的前插。由于指定節(jié)點(diǎn)的前后插操作是已經(jīng)指定過節(jié)點(diǎn)，所以對(duì)此情況我們單鏈表是否帶頭結(jié)點(diǎn)對(duì)其沒什么影響；只有按位序插入時(shí)，單鏈表是否帶頭結(jié)點(diǎn)會(huì)影響其實(shí)現(xiàn)，接下來我們?cè)诜治霭次恍虿迦霑r(shí)也將是否帶頭結(jié)點(diǎn)來分開討論。?
按位序插入
? ? ? ? 按位序插入，顧名思義也就是在我們需要插入的地方，插入一個(gè)值即可，在這里我們創(chuàng)建該函數(shù)表示：
ListInsert(&L,i,e)：插入操作。在表L中的第i個(gè)位置上插入指定元素e。?
? ? ? ? 由于鏈表的特殊性，我們無法跟順序表一樣，可以直接的找到其第i個(gè)位置；我們知道，單鏈表就是由很多結(jié)點(diǎn)相連，所以我們要想找到第i個(gè)位置的結(jié)點(diǎn)，就需要從頭部向后，順著我們結(jié)點(diǎn)中指向下一個(gè)結(jié)點(diǎn)的指針，逐步向后查找，知道找到第i個(gè)即可。由于需要從頭部開始查找，所以帶頭結(jié)點(diǎn)的單鏈表插入與不帶頭結(jié)點(diǎn)的單鏈表插入，在實(shí)現(xiàn)上就存在一定的不同。?
帶頭結(jié)點(diǎn)
? ? ? ? ?由上文我們已經(jīng)了解到了帶頭結(jié)點(diǎn)的單鏈表，那么在這里對(duì)于帶頭結(jié)點(diǎn)的鏈表就不作描述。既然我們需要在第i個(gè)位置上插入一個(gè)元素，那么首先我們要做的就是檢查i是否合法（如果i的值為0，我們的鏈表怎么會(huì)有第0位呢？或者是i的值超出我們鏈表的長度呢？這樣就是不合法）。
?
? ? ? ? 我們核驗(yàn)完i的合法性后，就需要思考如何在第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)；以圖為例：如果我們要在第二個(gè)位置插入一個(gè)結(jié)點(diǎn)e，那么首先我們要做的是使用malloc函數(shù)開辟出一片新的空間（前文有malloc描述）；開辟出一段空間之后，我們就需要去查找出鏈表中第二個(gè)結(jié)點(diǎn)前的位置，這是因?yàn)槲覀冃枰诘诙€(gè)位置插入元素的話，就需要將元素插入到第一個(gè)元素和第二個(gè)元素之間（這樣我們插入的元素就成為了第二個(gè)元素）；又由于在我們的單鏈表中?，前一個(gè)結(jié)點(diǎn)中存在一個(gè)指針指向下一個(gè)結(jié)點(diǎn)的地址，當(dāng)我們找到第一個(gè)元素時(shí)，也相當(dāng)于找到了第二個(gè)元素的位置，這時(shí)，我們讓新插入的結(jié)點(diǎn)中的指針指向原鏈表中的第二個(gè)結(jié)點(diǎn)位置，而原鏈表中第一個(gè)元素的指針則指向新插入結(jié)點(diǎn)的位置；這樣我們是不是就成功的將其連接起來了。
? ? ? ? 又因?yàn)槲覀冞@里在第一個(gè)結(jié)點(diǎn)前是存在一個(gè)頭結(jié)點(diǎn)的，所以當(dāng)我們想要在第一個(gè)位置插入一個(gè)元素時(shí)，這時(shí)待插入的位置是頭結(jié)點(diǎn)和原鏈表中第一個(gè)結(jié)點(diǎn)之間，由于同樣是在兩個(gè)結(jié)點(diǎn)之間，所以其插入方法也同上。
? ? ? ? ?由于我們?cè)谶M(jìn)行按位插入時(shí)需要從頭部循環(huán)向后遍歷到第i-1個(gè)結(jié)點(diǎn)，所以需要遍歷i-1次；那么其平均復(fù)雜度也就是O(n);同理，當(dāng)我們需要插入的位置在第一個(gè)時(shí)，我們就不需要遍歷，那個(gè)我們這是的時(shí)間復(fù)雜度就是最優(yōu)時(shí)間復(fù)雜度：O(1)。
? ? ? ? 需要注意的是，我們?cè)谶M(jìn)行插入操作時(shí)，其順序可不可以更改？也就是如上圖所示：正常來說，我們需要首先讓e的指針指向的地址，之后讓頭結(jié)點(diǎn)指針指向e的地址；那么我們可以不可以顛倒順序呢？
? ? ? ? 答案當(dāng)然是不可以的。其主要原因就是，由于我們頭結(jié)點(diǎn)的指針初始是存放的??的地址（我們只能通過頭結(jié)點(diǎn)的指針尋找到其地址），那么按照我們最初的方法，是需要將存放的這個(gè)?的地址賦值給e結(jié)點(diǎn)中指針，之后我們?cè)俑鼡Q掉頭結(jié)點(diǎn)指針的指向（由于e為malloc開辟的空間，所以我們?cè)陂_辟時(shí)會(huì)創(chuàng)建出一個(gè)指針直接存放其地址，所以我們可以直接通過這個(gè)指針對(duì)其賦值）；而當(dāng)我們首先將頭結(jié)點(diǎn)指針的指向更改為e的存儲(chǔ)地址后，在后面我們e中指針指向??地址時(shí)，我們會(huì)將頭結(jié)點(diǎn)的指針指向位置值賦給e中指針，但此時(shí)頭結(jié)點(diǎn)指針的指向已經(jīng)不是?地址了，這樣就會(huì)造成如上圖所示的錯(cuò)誤。
? ? ? ? ?當(dāng)然由于是從前向后遍歷，那么最差的時(shí)間復(fù)雜度當(dāng)然就是在最末位插入結(jié)點(diǎn)了，其時(shí)間復(fù)雜度為：O(n)。
//插入 : 在第i個(gè)位置插入(含頭節(jié)點(diǎn)）
bool ListInsert(LinkList &L, int i, int e) {
if(i<1) return false ;
LNode *p ; //掃描指針
int j = 0; //帶頭節(jié)點(diǎn) 從0開始
p = L;
while(p != NULL && j < i-1) { //找到 i-1 的位置
p = p->next ;
j++;
}
if(p == NULL) return false;
LNode *s = (LNode *)malloc(sizeof(LNode)) ;
s->data = e;
s->next = p->next;
p->next = s;
return true;
} 需要注意的是：由于我們這里的鏈表是沒有記錄長度的，所以我們?cè)趙hile循環(huán)中 p!=NULL 是為了判斷i是否會(huì)超出鏈表長度。?當(dāng)然也可以寫出一個(gè)計(jì)算長度的函數(shù)，其原理大致就是從頭結(jié)點(diǎn)開始向后遍歷，直到循環(huán)到該結(jié)點(diǎn)指針指向NULL即可，在循環(huán)中，每執(zhí)行一次就讓記錄長度的變量自增即可。
不帶頭結(jié)點(diǎn)
? ? ? ? ?由于這里單鏈表不存在頭結(jié)點(diǎn)，所以這里在i=1時(shí)，我們需要特殊處理以下；當(dāng)i>1且合法時(shí)，我們此時(shí)插入前后都是結(jié)點(diǎn)，這時(shí)方法就同帶頭結(jié)點(diǎn)單鏈表的插入方法。
? ? ? ? ?這里我們只需分析插入第一個(gè)位置的情況，由于我們不存在頭結(jié)點(diǎn)，所以當(dāng)我們想要插入第一個(gè)元素時(shí)，就需要利用頭指針；在插入前，我們的頭指針指向的是當(dāng)時(shí)的第一個(gè)結(jié)點(diǎn)，也是我們插入后的第二個(gè)結(jié)點(diǎn)；那么我們?cè)诓迦霑r(shí)，首先需要使插入結(jié)點(diǎn)e的指針指向（也就是L指向的位置），之后我們更改L頭指針的指向，使其指向e結(jié)點(diǎn)的位置即可。（當(dāng)然這里我們的存儲(chǔ)指向順序也是不可以顛倒的，如果顛倒會(huì)同上面一樣，形成一個(gè)閉環(huán)）
? ? ? ? 除了頭部的插入以外，其余的插入方法就同帶頭結(jié)點(diǎn)單鏈表插入的方法相同，我們?cè)谶@里就不做多描述，其時(shí)間復(fù)雜度也同帶頭結(jié)點(diǎn)的插入相同。
綜上來看：
? ? ? ? 帶頭結(jié)點(diǎn)與不帶頭結(jié)點(diǎn)的單鏈表在按位序插入中，其基本實(shí)現(xiàn)方法是相同的，僅僅只在頭結(jié)點(diǎn)插入時(shí)略有不同；其時(shí)間復(fù)雜度也都是相同的：最優(yōu)為O(1),最差為O(n)。?
指定結(jié)點(diǎn)后插
? ? ? ? 對(duì)于指定結(jié)點(diǎn)后插的操作，其實(shí)現(xiàn)方法其實(shí)是跟前面的按位序插入是類似的。
? ? ? ? 我們回想以下，我們?cè)趯?shí)現(xiàn)按位序插入時(shí)，是要找的插入位置的前一個(gè)結(jié)點(diǎn)的位置進(jìn)行操作的，而這里是直接給出需要插入位置的前一個(gè)結(jié)點(diǎn)位置，那么我們只需按照之前按位序插入的方法執(zhí)行一遍即可（首先讓e結(jié)點(diǎn)的指針指向y，也就是x結(jié)點(diǎn)指針的指向；之后讓x指針的指向e的存儲(chǔ)位置即可）?。
bool InsertNextNode (LNode *p, ElemType e) {
if (p == NULL) return false ;
LNode *s = (LNode *) malloc(sizeof(LNode));
if(s==NULL) return false //內(nèi)存分配失敗
s->data = e;
s->next = p->next;
p->next = s;
return true;
}? ? ? ? ?在實(shí)現(xiàn)時(shí)需要判斷以下其內(nèi)存是否分配成功，也就是 s 是否為 NULL。
指定結(jié)點(diǎn)前插
InsertPriorNode (LNode *p, ElemType e) ：在p結(jié)點(diǎn)之前插入元素e?
? ? ? ? ?在這種情況下，看似跟之前很像，但不太一樣，由于我們的 p 指向的為插入結(jié)點(diǎn)后的元素，而我們單鏈表又無法找到結(jié)點(diǎn)x前驅(qū)結(jié)點(diǎn)，那么我們就很難通過之前的辦法讓x的前驅(qū)結(jié)點(diǎn)指向我們需要插入結(jié)點(diǎn)的存儲(chǔ)位置，那么我們就需要更改方法。
? ? ? ? 首先，提供一種簡單的方法，若函數(shù)可以傳入單鏈表的頭指針，此時(shí)我們只需從頭指針向后遍歷，遍歷到某結(jié)點(diǎn)的指針指向為p即可，這時(shí)我們就成功找到其插入后的前驅(qū)結(jié)點(diǎn)，就可以按我們之前的方法去進(jìn)行插入了。
? ? ? ? 不過這種方法是復(fù)雜的，其需要遍歷，所以其時(shí)間復(fù)雜度為O(n);那么我們用什么辦法可以使得其不從頭遍歷也可以前插呢？
? ? ? ??
? ? ? ? 在這里，我們按照之前的辦法，在結(jié)點(diǎn)e的后面插入一個(gè)結(jié)點(diǎn)x，這就等同于我們之前的方法，并不難實(shí)現(xiàn)。
? ? ? ? ?緊接著呢，我們定義一個(gè)與結(jié)點(diǎn)中數(shù)據(jù)同類型的變量，利用該變量顛倒e與x的存儲(chǔ)數(shù)位置，這樣我們就等同于在p的前面插入一個(gè)結(jié)點(diǎn)了，只不過此時(shí)p指向的是我們所插入的結(jié)點(diǎn)。
bool InsertPriorNode (LNode *p, ElemType e) {
if (p == NULL) return false ;
LNode *s = (LNode *) malloc(sizeof(LNode));
if(s==NULL) return false //內(nèi)存分配失敗
s->next = p->next;
p->next = s; //新結(jié)點(diǎn)相連
s->data = p->data; //p中元素給s
p->data = e; // e的值給p
return true;
}????????由于我們只在單個(gè)的位置中插入，該算法的時(shí)間復(fù)雜度為:O(1)。?
單鏈表的刪除
按位序刪除?
?ListDelete(&L, i, &e) ：刪除操作。刪除表L中第i個(gè)位置的元素，并用e返回刪除元素的值。
? ? ? ? ?由于我們的鏈表是有單個(gè)的結(jié)點(diǎn)不斷相連的，所以我們?cè)趧h除某一節(jié)點(diǎn)時(shí)，只需要更改其相連的方向即可，不需要向順序表一樣，將刪除結(jié)點(diǎn)后的結(jié)點(diǎn)均向前移動(dòng)，這樣就提高了效率。
帶頭結(jié)點(diǎn)
? ? ? ? 由于我們需要?jiǎng)h除第i個(gè)元素，那么我們?cè)趧h除操作中，首先需要找到第i-1個(gè)結(jié)點(diǎn)的位置，然后我們直接更改其i-1結(jié)點(diǎn)的指針指向，使其指向i+1結(jié)點(diǎn)的存儲(chǔ)位置；這樣在后面我們遍歷時(shí)，就可以直接跳過第i個(gè)元素了。
?
? ? ? ? 我們的刪除操作只是需要改一個(gè)刪除結(jié)點(diǎn)前的結(jié)點(diǎn)指針指向即可，其時(shí)間復(fù)雜度為O(1);所以其整體的刪除操作時(shí)間主要耗費(fèi)在尋找第i-1個(gè)結(jié)點(diǎn)的位置上；根據(jù)我們前面的分析，尋找需要從頭循環(huán)遍歷，所以其平均時(shí)間復(fù)雜度則是O(n);那么最好的時(shí)間復(fù)雜度則是在第一個(gè)位置插入，為O(1);最差的時(shí)間復(fù)雜度則是在最末尾插入，時(shí)間復(fù)雜度為O(n)?。
? ? ? ? 對(duì)于含有頭結(jié)點(diǎn)的單鏈表而言，其在第一個(gè)刪除時(shí)前面存在頭結(jié)點(diǎn)，所以插入的方式就跟在后面結(jié)點(diǎn)插入的方式相同。
//刪除 : 刪除第i個(gè)位置的元素 并返回 （含頭節(jié)點(diǎn)）
bool ListDelete(LinkList &L, int i, int &e) {
if(i<1) return false;
LNode *p;
int j=0;
p = L;
while(p != NULL && j < i-1) {
p = p->next;
j++;
}
if(p == NULL) return false;
e = p->next->data;
p->next = p->next->next;
/*
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
*/
return true;
} ?
不帶頭結(jié)點(diǎn)?
? ? ? ? 對(duì)于不含頭結(jié)點(diǎn)的單鏈表，其除在頭部的刪除外，其余的方法均與帶頭結(jié)點(diǎn)的單鏈表相同，所以這里我們只討論起頭部的刪除。
? ? ? ? 由于不帶頭結(jié)點(diǎn)的單鏈表刪除頭部時(shí)?前面無頭結(jié)點(diǎn)，只有一個(gè)頭指針指向其存儲(chǔ)位置，所以我們?cè)趧h除時(shí)，只需要將頭指針指向第二個(gè)結(jié)點(diǎn)的存儲(chǔ)位置即可。
//刪除 : 刪除第i個(gè)位置的元素 并返回 （不含頭節(jié)點(diǎn)）
bool ListDelete(LinkList &L, int i, int &e) {
if(i<1) return false;
LNode *p;
int j=1;
p = L;
if(i==1) {
e = p->data ;
L = p->next;
}
while(p != NULL && j < i-1) {
p = p->next;
j++;
}
if(p == NULL) return false;
e = p->next->data;
p->next = p->next->next;
/*
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
*/
return true;
} ?指定結(jié)點(diǎn)刪除
DeleteNode(LNode *p)? ? ? ? 刪除指定結(jié)點(diǎn) p
? ? ? ? 這里，我們?nèi)粢獎(jiǎng)h除p指向的結(jié)點(diǎn)，就需要更改其前驅(qū)結(jié)點(diǎn)的指向，但是我們并不能通過p去找到其前驅(qū)結(jié)點(diǎn)，那么如果這里我們引入一個(gè)頭指針L，從頭部向后遍歷尋找其前驅(qū)結(jié)點(diǎn)，這樣我們就可以根據(jù)上面的刪除方法對(duì)其進(jìn)行刪除了。
????????該種方法由于要從前遍歷尋找，所以其時(shí)間復(fù)雜度為O(n)。?
????????還有一種辦法，我們只需要將p后續(xù)結(jié)點(diǎn)的數(shù)據(jù)值存入p指向的結(jié)點(diǎn)中，之后讓p指向的結(jié)點(diǎn)的指針直接跳過其后繼結(jié)點(diǎn)，指向指向其后面的那個(gè)即可。也就是我們將y的值存入x的位置，然后讓p指向的結(jié)點(diǎn)直接跳過q指向下一個(gè)即可。
//刪除指定節(jié)點(diǎn) (刪除 p 節(jié)點(diǎn)）
bool DeleteNode(LNode *p, LinkList &L) {
if(p == NULL) return false;
if(p == L) {
L = p->next;
}
p->data = p->next->data;
p->next = p->next->next;
/*
LNode *q;
q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
*/
return true;
}? ? ? ? 這種辦法只需要更改其指向即可，所以其時(shí)間復(fù)雜度為O(1)。?
單鏈表的查找
? ? ? ? 對(duì)于單鏈表的查找，其實(shí)我們實(shí)現(xiàn)的底層邏輯都是相同的，就是從頭指針開始向后遍歷，知道尋找到我們需要查找的結(jié)點(diǎn)為止；由于需要從前向后遍歷查找，所以其時(shí)間復(fù)雜度自然為:O(n)。
按位查找
?GetElem(L,i)：按位查找操作。獲取表L中第i個(gè)位置的元素的值。
? ? ? ? ?對(duì)于按位查找，我們只需要利用一個(gè)for循環(huán)，使其循環(huán)i次，其循環(huán)到的結(jié)果自然就是我們?cè)氐闹盗?；不過需要注意的是，在循環(huán)過程中，需要判斷一個(gè)i的合法性，避免長度超出我們鏈表長度。
//按位查找
LNode *GetElem(LinkList L, int i){
if(i<0) return NULL;
LNode *p;
int j=0;
p = L;
while(p!=NULL && j<i){
p = p->next;
j++;
}
//if(p==NULL) return NULL;
return p;
} 按值查找
?LocateElem(L,e)：按值查找操作。在表L中查找具有給定關(guān)鍵字值的元素。
? ? ? ? ?按值查找的方法與按位查找略有不同，按值查找需要遍歷整個(gè)鏈表，之后在每次遍歷時(shí)都要判斷一下其是否為我們需要尋找的值，如果遍歷到NULL還未找到，則說明該值不在鏈表之中。
//按值查找
LNode *LocateElem(LinkList L, int e) {
LNode *p = L; //初始化
while(p != NULL && p->data != e) {
p = p->next;
}
return p;
}單鏈表建立
? ? ? ? 前面我們學(xué)習(xí)了那么多的單鏈表操作，那么我們對(duì)單鏈表一定有了一個(gè)基本的了解；那么我們?cè)诔跏蓟湵頃r(shí)，一定要將很多個(gè)結(jié)點(diǎn)相連到一起，那么我們?cè)撊绾螌?shí)現(xiàn)該問題呢？?在這里我們提供頭插法和尾插法兩種方法。
頭插法
? ? ? ? 如下圖所示，頭插法顧名思義也就是從頭部開始插入，我們每次插入一個(gè)新的元素，都需要從其頭部插入（如果是不含頭結(jié)點(diǎn)的鏈表，我們需要更改其頭指針）；這樣逐個(gè)的插入。?
?
? ? ? ? 不過這樣每次插入頭部方法，會(huì)使我們先插入鏈表的結(jié)點(diǎn)在后面，而后插入的結(jié)點(diǎn)在鏈表的前面。這個(gè)可以用于鏈表的逆置。
? ? ? ? 由于是需要一個(gè)一個(gè)插入，其總的時(shí)間復(fù)雜度為O(n)。
//頭插法建立
LinkList List_HeadInsert(LinkList &L) {
LNode *s; int x;
L = (LinkList)malloc(sizeof(LNode)) ;
L->next = NULL; //創(chuàng)建頭結(jié)點(diǎn)
cin >> x ;
while(x != 9999){
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = L->next ;
L->next = s ;
cin >> x ;
}
return L ;
}尾插法
?????????至于尾插法，顧名思義就是在鏈表的尾部插入一個(gè)結(jié)點(diǎn)；這種插入方法我們需要時(shí)刻更改尾部結(jié)點(diǎn)的指針指向，所以我們需要一個(gè)指針一直指向尾部結(jié)點(diǎn)，方便我們?nèi)ジ?；尾部插入的方法，其插入順序和在鏈表中的排列順序是相同的?/p>
? ? ? ? 由于是需要一個(gè)一個(gè)插入，其總的時(shí)間復(fù)雜度為O(n)。
//尾插法建立
LinkList List_TailInsert(LinkList &L) {
int x;
cin >> x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s, *r = L;
while(x!=9999) {
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
cin >> x;
}
r->next = NULL;
return L;
}?單鏈表代碼
含頭結(jié)點(diǎn)單鏈表代碼
?
//2.3 鏈表 單鏈表（帶頭節(jié)點(diǎn)）
#include<bits/stdc++.h>
using namespace std ;
//結(jié)點(diǎn)
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
//頭插法建立
LinkList List_HeadInsert(LinkList &L) {
LNode *s; int x;
L = (LinkList)malloc(sizeof(LNode)) ;
L->next = NULL; //創(chuàng)建頭結(jié)點(diǎn)
cin >> x ;
while(x != 9999){
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = L->next ;
L->next = s ;
cin >> x ;
}
return L ;
}
//尾插法建立
LinkList List_TailInsert(LinkList &L) {
int x;
cin >> x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s, *r = L;
while(x!=9999) {
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
cin >> x;
}
r->next = NULL;
return L;
}
//插入 : 在第i個(gè)位置插入(含頭節(jié)點(diǎn)）
bool ListInsert(LinkList &L, int i, int e) {
if(i<1) return false ;
LNode *p ; //掃描指針
int j = 0; //帶頭節(jié)點(diǎn) 從0開始
p = L;
while(p != NULL && j < i-1) { //找到 i-1 的位置
p = p->next ;
j++;
}
if(p == NULL) return false;
LNode *s = (LNode *)malloc(sizeof(LNode)) ;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//刪除 : 刪除第i個(gè)位置的元素 并返回 （含頭節(jié)點(diǎn)）
bool ListDelete(LinkList &L, int i, int &e) {
if(i<1) return false;
LNode *p;
int j=0;
p = L;
while(p != NULL && j < i-1) {
p = p->next;
j++;
}
if(p == NULL) return false;
e = p->next->data;
p->next = p->next->next;
/*
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
*/
return true;
}
//刪除指定節(jié)點(diǎn) (刪除 p 節(jié)點(diǎn)）
bool DeleteNode(LNode *p) {
if(p == NULL) return false;
p->data = p->next->data;
p->next = p->next->next;
/*
LNode *q;
q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
*/
return true;
}
//按位查找
LNode *GetElem(LinkList L, int i){
if(i<0) return NULL;
LNode *p;
int j=0;
p = L;
while(p!=NULL && j<i){
p = p->next;
j++;
}
//if(p==NULL) return NULL;
return p;
}
//按值查找
LNode *LocateElem(LinkList L, int e) {
LNode *p = L; //初始化
while(p != NULL && p->data != e) {
p = p->next;
}
return p;
}
//展示當(dāng)前鏈表
void ShowList(LinkList L) {
LNode *p = L->next;
while(p!=NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//初始化
bool InitList(LinkList &L) {
L = NULL;
return true;
}
int main(){
LinkList L;
InitList(L); //初始化
int x ;
cout << "請(qǐng)選擇頭插（1、尾插（2：";
cin >> x ;
if(x == 1) {
cout << "頭插法：" ;
List_HeadInsert(L); //頭插法創(chuàng)建
ShowList(L);
}
else {
cout << "尾插法： " ;
List_TailInsert(L); //尾插法創(chuàng)建
ShowList(L);
}
ListInsert(L, 2, 3); //插入
ShowList(L);
int e;
ListDelete(L, 2, e); //刪除
ShowList(L);
// GetElem(L, 3); //查找按位
ShowList(L);
cout << GetElem(L, 3)->data << endl;
// LocateElem(L, 3); //按值查
ShowList(L);
cout << LocateElem(L, 3)->data << endl;
DeleteNode(LocateElem(L, 3));
ShowList(L);
return 0;
} 不含頭結(jié)點(diǎn)單鏈表代碼
//2.3 鏈表 單鏈表（不帶頭節(jié)點(diǎn)）
#include<bits/stdc++.h>
using namespace std ;
//結(jié)點(diǎn)
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
//頭插法建立
LinkList List_HeadInsert(LinkList &L) {
LNode *s; int x;
cin >> x;
L = (LinkList)malloc(sizeof(LNode)) ;
L->data = x;
L->next = NULL;
cin >> x;
while(x != 9999){
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = L ;
L = s ;
cin >> x ;
}
return L ;
}
//尾插法建立
LinkList List_TailInsert(LinkList &L) {
int x ;
cin >> x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s, *r = L;
L->data = x;
cin >> x;
while(x!=9999) {
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
cin >> x;
}
r->next = NULL;
return L;
}
//插入 : 在第i個(gè)位置插入(不含頭節(jié)點(diǎn)）
bool ListInsert(LinkList &L, int i, int e) {
if(i<1) return false ;
LNode *p ; //掃描指針
int j = 1; //不帶頭節(jié)點(diǎn) 從1開始
p = L;
if(i==1) {
LNode *s = (LNode *)malloc(sizeof(LNode)) ;
s->data = e;
s->next = p;
p = s;
return true;
}
while(p != NULL && j < i-1) { //找到 i-1 的位置
p = p->next ;
j++;
}
if(p == NULL) return false;
LNode *s = (LNode *)malloc(sizeof(LNode)) ;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//刪除 : 刪除第i個(gè)位置的元素 并返回 （不含頭節(jié)點(diǎn)）
bool ListDelete(LinkList &L, int i, int &e) {
if(i<1) return false;
LNode *p;
int j=1;
p = L;
if(i==1) {
e = p->data ;
L = p->next;
}
while(p != NULL && j < i-1) {
p = p->next;
j++;
}
if(p == NULL) return false;
e = p->next->data;
p->next = p->next->next;
/*
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
*/
return true;
}
//刪除指定節(jié)點(diǎn) (刪除 p 節(jié)點(diǎn)）
bool DeleteNode(LNode *p, LinkList &L) {
if(p == NULL) return false;
if(p == L) {
L = p->next;
}
p->data = p->next->data;
p->next = p->next->next;
/*
LNode *q;
q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
*/
return true;
}
//按位查找
LNode *GetElem(LinkList L, int i){
if(i<=0) return NULL;
LNode *p;
int j=1;
p = L;
while(p!=NULL && j<i){
p = p->next;
j++;
}
//if(p==NULL) return NULL;
return p;
}
//按值查找
LNode *LocateElem(LinkList L, int e) {
LNode *p = L; //初始化
while(p != NULL && p->data != e) {
p = p->next;
}
return p;
}
//展示當(dāng)前鏈表
void ShowList(LinkList L) {
LNode *p = L;
while(p!=NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//初始化
bool InitList(LinkList &L) {
L = NULL;
return true;
}
int main(){
LinkList L;
InitList(L); //初始化
int x ;
cout << "請(qǐng)選擇頭插（1、尾插（2：";
cin >> x ;
if(x == 1) {
cout << "頭插法：" ;
List_HeadInsert(L); //頭插法創(chuàng)建
ShowList(L);
}
else {
cout << "尾插法： " ;
List_TailInsert(L); //尾插法創(chuàng)建
ShowList(L);
}
ListInsert(L, 2, 3); //插入
ShowList(L);
int e;
ListDelete(L, 2, e); //刪除
ShowList(L);
// GetElem(L, 3); //查找按位
ShowList(L);
cout << GetElem(L, 3)->data << endl;
// LocateElem(L, 3); //按值查
ShowList(L);
cout << LocateElem(L, 3)->data << endl;
DeleteNode(LocateElem(L, 3), L);
ShowList(L);
return 0;
}
運(yùn)行結(jié)果如下：?
? ? ? ? ?第一行是我們頭插法后單鏈表的展示，我們可以看出，其頭插法的存儲(chǔ)會(huì)與我們輸入鏈表的順序相反；第二行就是我們的插入操作結(jié)果，第三行就是我們的刪除操作結(jié)果，第4-7行就是查找第三個(gè)位置的元素和3在什么位置并返回；最后一行則是刪除第三個(gè)結(jié)點(diǎn)。
? ? ? ? ?第一行是我們尾插法后單鏈表的展示，我們可以看出，其尾插法的存儲(chǔ)會(huì)與我們輸入鏈表的順序相同（為1-7）；第二行就是我們的插入操作結(jié)果（在第二個(gè)位置插入3），第三行就是我們的刪除操作結(jié)果（刪除第二個(gè)位置的結(jié)點(diǎn)），第4-7行就是查找第三個(gè)位置的元素和3在什么位置并返回（這里我們查找3所在的位置和第三個(gè)元素與頭插法查找的結(jié)果就是不同的）；最后一行則是刪除第三個(gè)結(jié)點(diǎn)。文章來源：http://www.zghlxwxcb.cn/news/detail-833443.html
? ? ? ? ?到這里我們對(duì)于單鏈表的基本學(xué)習(xí)也就結(jié)束了，至于一些其他的操作例如：求長度，這些簡單的循環(huán)我們就不在這里過多敘述；相信各位大佬通過上面的學(xué)習(xí)，可以輕松的實(shí)現(xiàn)這些簡單的功能。文章來源地址http://www.zghlxwxcb.cn/news/detail-833443.html
到了這里，關(guān)于【玩轉(zhuǎn)408數(shù)據(jù)結(jié)構(gòu)】線性表——單鏈表的定義以及增刪改查（線性表的鏈?zhǔn)奖硎?上）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
