---

前言

?????????在數(shù)據(jù)結(jié)構(gòu)的廣袤天地里，鏈表作為一種重要的線性數(shù)據(jù)結(jié)構(gòu)，以其獨(dú)特的存儲(chǔ)方式和靈活的操作特性，在眾多編程場(chǎng)景中發(fā)揮著關(guān)鍵作用。今天，我們就來(lái)深入探討一下從單鏈表到雙鏈表的發(fā)展歷程，看看雙鏈表是如何在單鏈表的基礎(chǔ)上應(yīng)運(yùn)而生，并解決了單鏈表所面臨的一些問(wèn)題。

---

一、單鏈表回顧

• 首先，我們來(lái)回顧一下單鏈表的基本結(jié)構(gòu)。單鏈表是由一系列節(jié)點(diǎn)組成的數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)包含兩部分：數(shù)據(jù)域和指針域。數(shù)據(jù)域用于存儲(chǔ)具體的數(shù)據(jù)，指針域則存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)的指針，通過(guò)這樣的指針鏈接，各個(gè)節(jié)點(diǎn)依次相連，形成了一條鏈表。
• 單鏈表不帶頭單向不循環(huán)，是鏈表結(jié)構(gòu)中較為基礎(chǔ)的一種形式，與帶頭節(jié)點(diǎn)的單鏈表不同，不帶頭節(jié)點(diǎn)的單鏈表在進(jìn)行操作時(shí)，第一個(gè)節(jié)點(diǎn)就直接存儲(chǔ)了實(shí)際的數(shù)據(jù)，沒(méi)有專門設(shè)置一個(gè)額外的頭節(jié)點(diǎn)來(lái)簡(jiǎn)化某些操作邏輯。

以下是帶頭單鏈表和不帶頭單鏈表的圖片

以上這些圖片均表示單鏈表

• 例如，我們有一個(gè)簡(jiǎn)單的單鏈表存儲(chǔ)整數(shù)數(shù)據(jù)，節(jié)點(diǎn)結(jié)構(gòu)可以定義如下

typedef struct ListNode 
{int data;struct ListNode *next;
} ListNode;

• 單鏈表在很多場(chǎng)景下都非常有用，它能夠方便地進(jìn)行動(dòng)態(tài)內(nèi)存分配，實(shí)現(xiàn)數(shù)據(jù)的靈活存儲(chǔ)和操作，比如插入和刪除節(jié)點(diǎn)等操作相對(duì)數(shù)組來(lái)說(shuō)更加靈活，不需要移動(dòng)大量元素

二、單鏈表的局限性

• 然而，單鏈表也存在一些局限性：
• 單向遍歷：

單鏈表的指針只能指向一個(gè)方向，也就是只能從表頭順著指針依次訪問(wèn)到表尾的節(jié)點(diǎn)

• 刪除操作的不便:

當(dāng)我們想要刪除單鏈表中的某個(gè)節(jié)點(diǎn)時(shí)，如果只知道要?jiǎng)h除節(jié)點(diǎn)的指針（而不是它的前驅(qū)節(jié)點(diǎn)指針），操作起來(lái)會(huì)比較麻煩,，往往需要從頭開(kāi)始遍歷鏈表去找到前驅(qū)節(jié)點(diǎn)，這同樣會(huì)影響操作的效率。

為了克服單鏈表的這些局限性，我們就引入了雙鏈表

三、什么是雙鏈表

• 雙鏈表的每個(gè)節(jié)點(diǎn)除了包含數(shù)據(jù)域和指向下一個(gè)節(jié)點(diǎn)的指針域外，還增加了一個(gè)指向前一個(gè)節(jié)點(diǎn)的指針域。也就是說(shuō)，雙鏈表的節(jié)點(diǎn)結(jié)構(gòu)可以定義如下：

typedef struct DoublyListNode 
{int data;struct DoublyListNode *prev;struct DoublyListNode *next;
} DoublyListNode;

• 在這個(gè)結(jié)構(gòu)中，**prev 指針指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，next 指針指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。**這樣一來(lái)，雙鏈表就具備了雙向遍歷的能力。

雙鏈表可以分為帶頭節(jié)點(diǎn)和不帶頭結(jié)點(diǎn)

• 不帶頭節(jié)點(diǎn)的雙鏈表
  
• 結(jié)構(gòu)特點(diǎn)：

1.鏈表的第一個(gè)節(jié)點(diǎn)就直接存儲(chǔ)實(shí)際的數(shù)據(jù)元素，不存在一個(gè)專門作為 “頭” 的額外節(jié)點(diǎn)。
2.每個(gè)節(jié)點(diǎn)除了數(shù)據(jù)域外，有兩個(gè)指針域，一個(gè)指向前驅(qū)節(jié)點(diǎn)（prev 指針），一個(gè)指向后繼節(jié)點(diǎn)（next 指針）

• 帶頭結(jié)點(diǎn)的雙鏈表
  

• 結(jié)構(gòu)特點(diǎn)：

1.有一個(gè)專門的頭節(jié)點(diǎn)，這個(gè)頭節(jié)點(diǎn)的數(shù)據(jù)域一般不存儲(chǔ)實(shí)際的數(shù)據(jù)（當(dāng)然也可以根據(jù)具體需求賦予特殊含義，但通常為空數(shù)據(jù)域），主要作用是方便鏈表的各種操作。
2.頭節(jié)點(diǎn)同樣有兩個(gè)指針域，prev 指針一般指向 NULL（因?yàn)樗潜眍^，前面沒(méi)有節(jié)點(diǎn)了），next 指針指向鏈表中的第一個(gè)實(shí)際存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)。

四、雙鏈表的優(yōu)勢(shì)

1.雙向遍歷

從表頭到表尾遍歷：和單鏈表類似，我們可以通過(guò)每個(gè)節(jié)點(diǎn)的 next 指針依次訪問(wèn)后續(xù)節(jié)點(diǎn)，從而實(shí)現(xiàn)從表頭到表尾的遍歷。

• 刪除操作的便利性

在雙鏈表中刪除一個(gè)節(jié)點(diǎn)就變得更加容易了。假設(shè)我們要?jiǎng)h除節(jié)點(diǎn) p，我們可以直接通過(guò) p 的 prev 和 next 指針來(lái)完成刪除操作，而不需要像單鏈表那樣去專門尋找它的前驅(qū)節(jié)點(diǎn)

總結(jié)一下帶頭和不帶頭有什么用

2.不帶頭雙鏈表的用途

• 節(jié)省內(nèi)存空間：

每一個(gè)節(jié)點(diǎn)都實(shí)實(shí)在在地用于存儲(chǔ)數(shù)據(jù)及相關(guān)指針，不存在一個(gè)僅為了方便操作而占據(jù)空間但通常不存儲(chǔ)實(shí)際有效數(shù)據(jù)的頭節(jié)點(diǎn)。

• 體現(xiàn)數(shù)據(jù)原始性

3.帶頭雙鏈表的用途

• 簡(jiǎn)化操作邏輯：

• 插入 無(wú)論是頭插、尾插還是指定位置插入，由于有頭節(jié)點(diǎn)的存在，不需要針對(duì)鏈表為空的情況單獨(dú)設(shè)計(jì)特殊的處理邏輯。

• 刪除 進(jìn)行頭刪、尾刪或指定位置刪除時(shí)，操作邏輯相對(duì)統(tǒng)一，不用特別考慮鏈表為空時(shí)刪除操作的特殊變化。

• 遍歷 遍歷鏈表時(shí)，從頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開(kāi)始順著 next 指針向后遍歷（正向遍歷）以及從鏈表末尾順著 prev 指針向前遍歷（反向遍歷）的邏輯較為清晰、簡(jiǎn)單，不用像不帶頭雙鏈表那樣，正向遍歷要從第一個(gè)實(shí)際存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)開(kāi)始，反向遍歷要先找到末尾節(jié)點(diǎn)。

五、雙鏈表的操作

雙鏈表的插入操作

（一）雙鏈表的尾插操作

void LTTPushFront(LTNode* head, int x)
{assert(head);LTNode* newnode = new LTNode;newnode->data = x;newnode->next = head;head = newnode;// 打印鏈表printList(head);
}

• head 為雙鏈表的頭結(jié)點(diǎn)
• x為要插入的數(shù)值

插入節(jié)點(diǎn)的步驟

• LTNode* newnode = new LTNode創(chuàng)建新節(jié)點(diǎn)
• newnode->data = x初始化新節(jié)點(diǎn)的數(shù)據(jù)
• newnode->next = head
• 這行代碼將新節(jié)點(diǎn)的next指針指向當(dāng)前的頭節(jié)點(diǎn)head。這樣，新節(jié)點(diǎn)就指向了原來(lái)的第一個(gè)節(jié)點(diǎn)
• head = newnode
• 這行代碼將頭節(jié)點(diǎn)head更新為新節(jié)點(diǎn)newnode。這樣，新節(jié)點(diǎn)就成為了鏈表的新頭節(jié)點(diǎn)。

（二）雙鏈表的頭插操作

// 頭插操作
void LTPushFront(LTNode* head, int x) 
{assert(head);LTNode* newnode = buyNode(x);newnode->next = head->next;newnode->prev = head;head->next->prev = newnode;head->next = newnode;
}

• newnode->next = head->next;
• newnode->prev = head;
• 第一行代碼將新節(jié)點(diǎn)newnode的next指針指向當(dāng)前頭節(jié)點(diǎn)head的下一個(gè)節(jié)點(diǎn)（即原來(lái)鏈表中的第一個(gè)節(jié)點(diǎn)）。
• 第二行代碼將新節(jié)點(diǎn)newnode的prev指針指向頭節(jié)點(diǎn)head
• head->next->prev = newnode;
• 將原來(lái)鏈表中第一個(gè)節(jié)點(diǎn)（即head->next）的prev指針指向新節(jié)點(diǎn)newnode。這一步是為了讓原來(lái)的第一個(gè)節(jié)點(diǎn)知道它的前一個(gè)節(jié)點(diǎn)變成了新節(jié)點(diǎn)
• head->next = newnode;
• 將頭節(jié)點(diǎn)head的next指針指向新節(jié)點(diǎn)newnode。這一步是為了讓頭節(jié)點(diǎn)指向新插入的節(jié)點(diǎn)，從而使新節(jié)點(diǎn)成為鏈表中的第一個(gè)節(jié)點(diǎn)

（三）雙鏈表在指定位置之后插入數(shù)據(jù)

// 在pos位置之后插入數(shù)據(jù)
void LTInsert(LTNode* pos, int x) {assert(pos);LTNode* newnode = buyNode(x);newnode->next = pos->next;newnode->prev = pos;if (pos->next) {pos->next->prev = newnode;}pos->next = newnode;
}

• newnode->next = pos->next;：
• 將新節(jié)點(diǎn)newnode的next指針指向pos節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。
• newnode->prev = pos;
• 將新節(jié)點(diǎn)newnode的prev指針指向pos節(jié)點(diǎn)
• if (pos->next) { pos->next->prev = newnode; }：
• 如果pos節(jié)點(diǎn)有下一個(gè)節(jié)點(diǎn)（即pos->next不為NULL），那么將pos的下一個(gè)節(jié)點(diǎn)的prev指針指向新節(jié)點(diǎn)newnode。
• 這一步是為了保持雙鏈表的雙向連接關(guān)系
• 最后將pos節(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)newnode，完成新節(jié)點(diǎn)在pos節(jié)點(diǎn)之后的插入操作

雙鏈表的刪除操作

（一）雙鏈表的尾刪操作

// 尾刪
void LTPopBack(LTNode* head) 
{assert(!LTEmpty(head));LTNode* del = head->prev;LTNode* prev = del->prev;prev->next = head;head->prev = prev;delete del;
}

• LTNode* del = head->prev;
• 雙鏈表通常有一個(gè)頭節(jié)點(diǎn)，尾節(jié)點(diǎn)是頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，所以這里head->prev就是尾節(jié)點(diǎn)，將其賦值給del
• LTNode* prev = del->prev;，找到尾節(jié)點(diǎn)del的前一個(gè)節(jié)點(diǎn)prev
• prev->next = head;，將尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next指針指向頭節(jié)點(diǎn)，這樣就把尾節(jié)點(diǎn)從鏈表中移除了。
• head->prev = prev;，同時(shí)更新頭節(jié)點(diǎn)的prev指針指向新的尾節(jié)點(diǎn)（原來(lái)尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)）

（二）雙鏈表的頭刪操作

// 頭刪操作
void LTpopFront(LTNode* head) {assert(!LTEmpty(head));LTNode* del = head->next;head->next = del->next;if (del->next) {del->next->prev = head;}delete del;
}

• LTNode* del = head->next;頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)就是要?jiǎng)h除的第一個(gè)數(shù)據(jù)節(jié)點(diǎn)，將其賦值給del
• head->next = del->next;，將頭節(jié)點(diǎn)的next指針指向要?jiǎng)h除節(jié)點(diǎn)del的下一個(gè)節(jié)點(diǎn)，這樣就把del從鏈表中移除了。
• if (del->next) { del->next->prev = head; }，如果del有下一個(gè)節(jié)點(diǎn)（即del不是尾節(jié)點(diǎn)），那么將del的下一個(gè)節(jié)點(diǎn)的prev指針指向頭節(jié)點(diǎn)

（三）雙鏈表刪除指定位置數(shù)據(jù)

// 刪除指定位置數(shù)據(jù)
void LTEarse(LTNode* pos) {assert(pos);pos->prev->next = pos->next;if (pos->next) {pos->next->prev = pos->prev;}delete pos;
}

• pos->prev->next = pos->next;，將pos節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next指針指向pos節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，這樣就把pos從鏈表中移除了。
• if (pos->next) { pos->next->prev = pos->prev; }，如果pos有下一個(gè)節(jié)點(diǎn)，那么將pos的下一個(gè)節(jié)點(diǎn)的prev指針指向pos的前一個(gè)節(jié)點(diǎn)

文章到這里就結(jié)束了，感謝你的閱讀，喜歡的話記得三連