一文帶你搞懂雙鏈表

鏈表是常用的數(shù)據(jù)結(jié)構(gòu)，為方便學(xué)習(xí)，對鏈表進(jìn)行細(xì)分，分為五種：

1、不帶頭節(jié)點的單鏈表
2、帶頭節(jié)點的單鏈表
3、不帶頭結(jié)點的雙鏈表
4、帶頭結(jié)點的雙鏈表
5、帶頭結(jié)點的雙向循環(huán)鏈表

鏈表基本概念

頭指針：

1. 頭指針是指鏈表指向第一個結(jié)點的指針，若鏈表有頭結(jié)點，則是指向頭結(jié)點的指針頭指針具有標(biāo)識作用，所以常用頭指針冠以鏈表的名字無論鏈表是否為空，頭指針均不為空，頭指針是鏈表的必要元素

頭節(jié)點：

1. 頭結(jié)點是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一元素的結(jié)點之前，其數(shù)據(jù)域一般無意義(也可存放鏈表的長度)有了頭結(jié)點，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與其它結(jié)點的操作就統(tǒng)一了頭結(jié)點不一定是鏈表必須要素

單鏈表和雙鏈表的區(qū)別

1. 單鏈表的每一個節(jié)點中只有指向下一個結(jié)點的指針，不能進(jìn)行回溯。雙鏈表的每一個節(jié)點給中既有指向下一個結(jié)點的指針，也有指向上一個結(jié)點的指針，可以快速的找到當(dāng)前節(jié)點的前一個節(jié)點。

上面的三幅圖對于理解鏈表的插入、刪除很重要，看代碼的時候要對著看。

實際中經(jīng)常使用的一般為帶頭雙向循環(huán)鏈表，下面是一個雙向循環(huán)鏈表的 demo，是最簡單的情況。

雙向循環(huán)鏈表demo

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
 int data; //"數(shù)據(jù)域" 保存數(shù)據(jù)元素
 struct node * next; //保存下一個數(shù)據(jù)元素的地址
 struct node * prev; //保存上一個數(shù)據(jù)元素的地址
}Node;

//創(chuàng)建表頭表示鏈表 
Node* creatList()
{
 Node * HeadNode = (Node *)malloc(sizeof(Node));
 //初始化，自己指向自己 
 HeadNode->next = HeadNode->prev = HeadNode;
 return HeadNode;
}
//創(chuàng)建節(jié)點 
Node* creatNode(int data)
{
 //C語言：malloc + free 
 //C++：new + delete 
 Node* newNode = (Node *)malloc(sizeof(Node));
 //初始化
 newNode->data = data;
 newNode->next = NULL;
 newNode->prev = NULL;
 return newNode;
}
//遍歷鏈表
void printList(Node *headNode)
{
 //雙向鏈表不光可以用 next 打印，也可以用 prev 進(jìn)行打印
 //next指針打?。合冗M(jìn)后出   
 //prev指針打印：先進(jìn)先出 
    Node *p = headNode -> next;
    while(p != headNode){
        printf("%dt",p->data);
        p = p -> next;
    }
    printf("n");
}

//插入節(jié)點：頭插法
void insertNodebyHead(Node *headNode,int data)
{
 //創(chuàng)建插入的節(jié)點 
    Node *newNode = creatNode(data);
 //注意順序，賦值會改變指針指向，因此要先連后斷 
 /*
 headNode -> next =  newnode;
 newnode -> prev = headNode;
 newnode -> next = headNode -> next;
 headNode ->next->prev = newNode;
 */
 // 從上面調(diào)整順序，得到下面 
 newNode -> prev = headNode;
 newNode -> next = headNode -> next;
 headNode ->next->prev = newNode;
 headNode -> next =  newNode;
}

//插入節(jié)點：尾插法 
void insertNodebyTail(Node *headNode,int data)
{
 //創(chuàng)建插入的節(jié)點 
 Node *newNode = creatNode(data);
    
 //找到最后一個節(jié)點
 Node *lastNode = headNode;
 while(lastNode->next != headNode)
 {
  lastNode = lastNode->next;//往下走 
 }
 
 //注意順序
 headNode->prev =  newNode;
 newNode->next = headNode;
 lastNode->next = newNode;
 newNode->prev = lastNode;

}

//刪除節(jié)點
void deleteNodebyAppoin(Node *headNode,int posData)
{
 // posNode 想要刪除的節(jié)點，從第一個節(jié)點開始遍歷 
 // posNodeFront 想要刪除節(jié)點的前一個節(jié)點 
    Node *posNode = headNode -> next;
    Node *posNodeFront = headNode;
    
 if(posNode == NULL)
  printf("鏈表為空，無法刪除");
 else{
  while(posNode->data != posData)
  {
   //兩個都往后移，跟著 posNodeFront 走 
   posNodeFront = posNode;  
   posNode = posNodeFront->next;
   if (posNode->next == headNode)
   {
    printf("沒有找到，無法刪除");
    return; 
   }
  }
  //找到后開始刪除 
  posNodeFront->next = posNode->next;
  posNode->next->prev = posNodeFront;
  free(posNode);
 } 
}

int main()
{
 Node* List = creatList();
 
 insertNodebyHead(List,1); 
 insertNodebyHead(List,2); 
 insertNodebyHead(List,3);  
 printList(List);
 
 insertNodebyTail(List,0); 
 printList(List);
 
 deleteNodebyAppoin(List,2);
 printList(List);
 
 return 0;
}

結(jié)果：

雙鏈表的創(chuàng)建、遍歷和單鏈表差不多，只是頭插法、尾插法、刪除操作多了幾個步驟。

對于容易有疑問的地方，博主都寫了注釋，請仔細(xì)看。不理解的地方對著圖更好理解。