一、簡介
? ? ? ? 雖然單向鏈表能夠100%解決邏輯關(guān)系為“一對一”數(shù)據(jù)的存儲問題，但在解決那些需要大量查找前趨節(jié)點的問題是，單向鏈表無疑是不能用了，因為單向鏈表適合“從前往后”查找，并不適合“從后往前”查找。
? ? ? ? 如果要提高鏈表的查找效率，那雙向鏈表（雙鏈表）無疑是首選。
? ? ? ? 雙向鏈表字面上的意思是“雙向”的鏈表，如圖1所示。
??? ? ? 雙向指各個節(jié)點之間的邏輯關(guān)系是雙向的，該鏈表通常只有一個頭節(jié)點。
? ? ? ? 從圖1還可以看出，雙向鏈表中每個節(jié)點包括一下3個部分，分別是指針域（用于指向當(dāng)前節(jié)點的直接前驅(qū)節(jié)點）、數(shù)據(jù)域（用于存儲數(shù)據(jù)元素）和指針域（用于指向當(dāng)前節(jié)點的后繼節(jié)點）。
二、創(chuàng)建
1、聲明
typedef struct line{
struct line *prior;//指向直接前趨
int data;
struct line *next;//指向直接后繼
}line;2、創(chuàng)建
line* initLine(line *head){
head=(line*)malloc(sizeof(line));//創(chuàng)建鏈表第一個結(jié)點（首元結(jié)點）
head->prior=NULL;
head->next=NULL;
head->data=1;
line *list=head;
for(int i=2; i<=3; i++)
{
//創(chuàng)建并初始化一個新結(jié)點
line *body=(line*)malloc(sizeof(line));
body->prior=NULL;
body->next=NULL;
body->data=i;
list->next=body;//直接前趨結(jié)點的next指針指向新結(jié)點
body->prior=list;//新結(jié)點指向直接前趨結(jié)點
list=list->next;
}
return head;
}三、基本操作
1、添加節(jié)點
? ? ? ? 添加節(jié)點可以分為三種，分別是：添加至表頭、添加至鏈表的中間位置和添加至鏈表尾。
添加至表頭
? ? ? ? 將新元素添加到表頭，只需要將其與表頭元素建立雙層邏輯關(guān)系即可。
? ? ? ? 假設(shè)定義新元素節(jié)點為tmp，表頭節(jié)點為head，則只需要執(zhí)行下面兩個步驟和即可：
- tmp的next變成head，head的prior編程tmp；
- 將head移至tmp，重新指向新的表頭。
????????比如將元素7天添加到雙向鏈表的表頭，則實現(xiàn)過程如圖2所示。
添加至鏈表的中間位置
? ? ? ? 添加至表的中間位置主要分為兩個步驟：
- 新節(jié)點先與其后繼節(jié)點建立雙層邏輯關(guān)系；
- 新節(jié)點的前驅(qū)與之建立雙層邏輯關(guān)系。
? ? ? ? ?此過程如圖3所示。
?添加至表尾
?? ? ? ?與添加至表頭很相似，其過程如下：
- 找到雙向鏈表的最后一個節(jié)點；
- 讓新節(jié)點與其進行雙層邏輯關(guān)系建立。
? ? ? ? 此過程如圖4所示。?
代碼
經(jīng)過上述內(nèi)容，我們可以試著編寫代碼了。
line *insertLine(line *head,int data,int add){
//新建數(shù)據(jù)域為data的結(jié)點
line *temp=(line*)malloc(sizeof(line));
temp->data=data;
temp->prior=NULL;
temp->next=NULL;
//插入到鏈表頭，要特殊考慮
if(add==1)
{
temp->next=head;
head->prior=temp;
head=temp;
}
else
{
line *body=head;
//找到要插入位置的前一個結(jié)點
for(int i=1; i<add-1; i++)
{
body=body->next;
}
//判斷條件為真，說明插入位置為鏈表尾
if(body->next==NULL)
{
body->next=temp;
temp->prior=body;
}
else
{
body->next->prior=temp;
temp->next=body->next;
body->next=temp;
temp->prior=body;
}
}
return head;
}2、刪除節(jié)點
? ? ? ? 雙向鏈表刪除節(jié)點時，只需要遍歷到要刪除的節(jié)點，然后將其刪除即可。
? ? ? ? 例如，從刪除2的過程如圖5所示。
代碼
//刪除結(jié)點的函數(shù)，data為要刪除結(jié)點的數(shù)據(jù)域的值
line *delLine(line *head,int data)
{
line *temp=head;
//遍歷鏈表
while(temp)
{
//判斷當(dāng)前結(jié)點中數(shù)據(jù)域和data是否相等，若相等，摘除該結(jié)點
if (temp->data==data)
{
temp->prior->next=temp->next;
temp->next->prior=temp->prior;
free(temp);
return head;
}
temp=temp->next;
}
printf("鏈表中無該數(shù)據(jù)元素");
return head;
}3、查找節(jié)點
? ? ? ? 依次遍歷表中數(shù)據(jù)，直到找到為止。
代碼
//head為原雙鏈表，elem表示被查找元素
int selectElem(line * head,int elem){
//新建一個指針t，初始化為頭指針 head
line * t=head;
int i=1;
while(t)
{
if(t->data==elem)
{
return i;
}
i++;
t=t->next;
}
//程序執(zhí)行至此處，表示查找失敗
return -1;
}4、更改節(jié)點
? ? ? ? 在查找的基礎(chǔ)上完成。過程是通過遍歷找到的節(jié)點，直接將數(shù)據(jù)域修改即可。
代碼
//更新函數(shù)，其中，add 表示更改結(jié)點在雙鏈表中的位置，newElem 為新數(shù)據(jù)的值
line *amendElem(line *p,int add,int newElem){
line *temp=p;
//遍歷到被刪除結(jié)點
for (int i=1; i<add; i++)
{
temp=temp->next;
}
temp->data=newElem;
return p;
}四、完整代碼
? ? ? ? 給出的所有代碼的整合代碼：
#include <bits/stdc++.h>
typedef struct line{
struct line *prior;
int data;
struct line *next;
}line;
//雙鏈表的創(chuàng)建
line* initLine(line * head);
//雙鏈表插入元素，add表示插入位置
line * insertLine(line * head,int data,int add);
//雙鏈表刪除指定元素
line * delLine(line * head,int data);
//雙鏈表中查找指定元素
int selectElem(line * head,int elem);
//雙鏈表中更改指定位置節(jié)點中存儲的數(shù)據(jù)，add表示更改位置
line *amendElem(line * p,int add,int newElem);
//輸出雙鏈表的實現(xiàn)函數(shù)
void display(line * head);
int main(){
line *head=NULL;
//創(chuàng)建雙鏈表
head=initLine(head);
display(head);
//在表中第 3 的位置插入元素 7
head=insertLine(head,7,3);
display(head);
//表中刪除元素 2
head=delLine(head,2);
display(head);
printf("元素 3 的位置是：%d\n",selectElem(head,3));
//表中第 3 個節(jié)點中的數(shù)據(jù)改為存儲 6
head=amendElem(head,3,6);
display(head);
return 0;
}
line* initLine(line * head){
head=(line*)malloc(sizeof(line));
head->prior=NULL;
head->next=NULL;
head->data=1;
line *list=head;
for(int i=2; i<=5; i++)
{
line*body=(line*)malloc(sizeof(line));
body->prior=NULL;
body->next=NULL;
body->data=i;
list->next=body;
body->prior=list;
list=list->next;
}
return head;
}
line *insertLine(line *head,int data,int add){
//新建數(shù)據(jù)域為data的結(jié)點
line *temp=(line*)malloc(sizeof(line));
temp->data=data;
temp->prior=NULL;
temp->next=NULL;
//插入到鏈表頭，要特殊考慮
if(add==1)
{
temp->next=head;
head->prior=temp;
head=temp;
}
else
{
line * body=head;
//找到要插入位置的前一個結(jié)點
for(int i=1; i<add-1; i++)
{
body=body->next;
}
//判斷條件為真，說明插入位置為鏈表尾
if(body->next==NULL)
{
body->next=temp;
temp->prior=body;
}
else
{
body->next->prior=temp;
temp->next=body->next;
body->next=temp;
temp->prior=body;
}
}
return head;
}
line *delLine(line *head,int data)
{
line *temp=head;
//遍歷鏈表
while(temp)
{
//判斷當(dāng)前結(jié)點中數(shù)據(jù)域和data是否相等，若相等，摘除該結(jié)點
if(temp->data==data)
{
temp->prior->next=temp->next;
temp->next->prior=temp->prior;
free(temp);
return head;
}
temp=temp->next;
}
printf("鏈表中無該數(shù)據(jù)元素");
return head;
}
//head為原雙鏈表，elem表示被查找元素
int selectElem(line *head,int elem){
//新建一個指針t，初始化為頭指針 head
line *t=head;
int i=1;
while(t)
{
if(t->data==elem)
{
return i;
}
i++;
t=t->next;
}
//程序執(zhí)行至此處，表示查找失敗
return -1;
}
//更新函數(shù)，其中，add 表示更改結(jié)點在雙鏈表中的位置，newElem 為新數(shù)據(jù)的值
line *amendElem(line *p,int add,int newElem){
line * temp=p;
//遍歷到被刪除結(jié)點
for(int i=1; i<add; i++)
{
temp=temp->next;
}
temp->data=newElem;
return p;
}
//輸出鏈表的功能函數(shù)
void display(line *head)
{
line *temp=head;
while(temp)
{
if(temp->next==NULL)
{
printf("%d\n",temp->data);
}
else
{
printf("%d->",temp->data);
}
temp=temp->next;
}
}參考文獻：http://c.biancheng.net/view/3343.html文章來源：http://www.zghlxwxcb.cn/news/detail-412430.html
好啦，以上就是本文的全部內(nèi)容啦！創(chuàng)作不易，點個贊再走唄～文章來源地址http://www.zghlxwxcb.cn/news/detail-412430.html
到了這里，關(guān)于雙向鏈表（Double Linked List）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
