---

前言

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

---

一、單鏈表回顧

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

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

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

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

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

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

二、單鏈表的局限性

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

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

• 刪除操作的不便:

當我們想要刪除單鏈表中的某個節(jié)點時，如果只知道要刪除節(jié)點的指針（而不是它的前驅(qū)節(jié)點指針），操作起來會比較麻煩,，往往需要從頭開始遍歷鏈表去找到前驅(qū)節(jié)點，這同樣會影響操作的效率。

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

三、什么是雙鏈表

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

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

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

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

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

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

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

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

1.有一個專門的頭節(jié)點，這個頭節(jié)點的數(shù)據(jù)域一般不存儲實際的數(shù)據(jù)（當然也可以根據(jù)具體需求賦予特殊含義，但通常為空數(shù)據(jù)域），主要作用是方便鏈表的各種操作。
2.頭節(jié)點同樣有兩個指針域，prev 指針一般指向 NULL（因為它是表頭，前面沒有節(jié)點了），next 指針指向鏈表中的第一個實際存儲數(shù)據(jù)的節(jié)點。

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

1.雙向遍歷

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

• 刪除操作的便利性

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

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

2.不帶頭雙鏈表的用途

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

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

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

3.帶頭雙鏈表的用途

• 簡化操作邏輯：

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

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

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

五、雙鏈表的操作

雙鏈表的插入操作

（一）雙鏈表的尾插操作

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

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

插入節(jié)點的步驟

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

（二）雙鏈表的頭插操作

// 頭插操作
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é)點newnode的next指針指向當前頭節(jié)點head的下一個節(jié)點（即原來鏈表中的第一個節(jié)點）。
• 第二行代碼將新節(jié)點newnode的prev指針指向頭節(jié)點head
• head->next->prev = newnode;
• 將原來鏈表中第一個節(jié)點（即head->next）的prev指針指向新節(jié)點newnode。這一步是為了讓原來的第一個節(jié)點知道它的前一個節(jié)點變成了新節(jié)點
• head->next = newnode;
• 將頭節(jié)點head的next指針指向新節(jié)點newnode。這一步是為了讓頭節(jié)點指向新插入的節(jié)點，從而使新節(jié)點成為鏈表中的第一個節(jié)點

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

雙鏈表的刪除操作

（一）雙鏈表的尾刪操作

// 尾刪
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;
• 雙鏈表通常有一個頭節(jié)點，尾節(jié)點是頭節(jié)點的前一個節(jié)點，所以這里head->prev就是尾節(jié)點，將其賦值給del
• LTNode* prev = del->prev;，找到尾節(jié)點del的前一個節(jié)點prev
• prev->next = head;，將尾節(jié)點的前一個節(jié)點的next指針指向頭節(jié)點，這樣就把尾節(jié)點從鏈表中移除了。
• head->prev = prev;，同時更新頭節(jié)點的prev指針指向新的尾節(jié)點（原來尾節(jié)點的前一個節(jié)點）

（二）雙鏈表的頭刪操作

// 頭刪操作
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é)點的下一個節(jié)點就是要刪除的第一個數(shù)據(jù)節(jié)點，將其賦值給del
• head->next = del->next;，將頭節(jié)點的next指針指向要刪除節(jié)點del的下一個節(jié)點，這樣就把del從鏈表中移除了。
• if (del->next) { del->next->prev = head; }，如果del有下一個節(jié)點（即del不是尾節(jié)點），那么將del的下一個節(jié)點的prev指針指向頭節(jié)點

（三）雙鏈表刪除指定位置數(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é)點的前一個節(jié)點的next指針指向pos節(jié)點的下一個節(jié)點，這樣就把pos從鏈表中移除了。
• if (pos->next) { pos->next->prev = pos->prev; }，如果pos有下一個節(jié)點，那么將pos的下一個節(jié)點的prev指針指向pos的前一個節(jié)點

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