手?jǐn)]雙鏈表，圖解
跟單鏈表不同，雙鏈表的節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指針指向上一個(gè)元素，一個(gè)指針指向下一個(gè)元素。
▌如下圖
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，要像認(rèn)識(shí)一個(gè)人一樣，要了解這個(gè)人有什么特點(diǎn)，比如喜歡打球，喜歡喝酒之類的。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)也是一樣，要了解數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)。
我們要學(xué)習(xí)雙鏈表，需要搞明白鏈表這幾個(gè)特點(diǎn)
創(chuàng)建鏈表
往鏈表插入數(shù)據(jù)
刪除鏈表中的某個(gè)數(shù)據(jù)
刪除整個(gè)鏈表
查找鏈表
反轉(zhuǎn)鏈表
▌先看看如何創(chuàng)建一個(gè)鏈表
創(chuàng)建一個(gè)鏈表無非就是搞定鏈表頭，沒有頭的鏈表就是死鏈表，有頭就表示這個(gè)鏈表是存在的。當(dāng)然了，可能會(huì)存在循環(huán)鏈表，只有位置，沒有固定的頭指針。
創(chuàng)建一個(gè)pHead，并且以后pHead頭指針保持不動(dòng)，就表示我們創(chuàng)建好了一個(gè)鏈表頭指針。
typedef struct Node{
struct Node *prev;
struct Node *next;
int elements;
}pNode;
pNode * CreateHead(void)
{
pNode *head = NULL;
head = (pNode *)malloc(sizeof(struct Node));
head->next = NULL;
head->prev = NULL;
return head;
}
▌插入元素
插入元素的方式有多種，可以頭插，可以尾插，也可以任意插，我只寫了簡(jiǎn)單的插入方式-尾插。
int InsertElement(pNode *head,int element)
{
if(head == NULL)
{
PRINTK_LINK("Head NULL\n");
return (-1);
}
pNode * pTemp = head;
while(pTemp->next != NULL)
{
pTemp = pTemp->next;
}
pNode * pElement = (pNode *)malloc(sizeof(struct Node));
pElement->elements = element;
pTemp->next = pElement;
pElement->prev = pTemp;
PRINTK_LINK("Element:%d\n",element);
return (0);
}
▌遍歷一個(gè)鏈表
遍歷鏈表是常規(guī)的操作，但是遍歷鏈表的方法有很多種，可以從頭開始遍歷，可以從尾部開始，在涉及二分查找的時(shí)候可以從中間某個(gè)位置開始遍歷。雖然方法很多，但是我只寫了一種方法，就是從頭開始遍歷鏈表，因?yàn)槭亲詈?jiǎn)單的。
int TraverseLink(pNode *head)
{
if(head == NULL)
{
PRINTK_LINK("Head NULL\n");
return (-1);
}
pNode * pTemp = head;
while(pTemp->next != NULL)
{
pTemp = pTemp->next;
PRINTK_LINK("Element:%d\n",pTemp->elements);
}
return (0);
}
▌刪除鏈表
刪除整個(gè)鏈表是把鏈表的每個(gè)元素都刪除，并且把頭也刪除，并且把頭指針指向NULL。如果需要找到鏈表中的某個(gè)元素并刪除，就需要先找到鏈表中的元素，刪除掉，并且把前后的兩個(gè)元素連在一起。
int DeleteLink(pNode *head)
{
if(head == NULL)
{
PRINTK_LINK("Head NULL\n");
return (-1);
}
pNode * pTemp = head;
while(pTemp->next != NULL)
{
pTemp = pTemp->next;
}
while(pTemp != NULL)
{
free(pTemp);pTemp = NULL;
pTemp = pTemp->prev;
}
return (0);
}
▌完整代碼
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define LOG_TAG "[LINK]: %s() line: %d "
#define PRINTK_LINK(fmt, args...) printf(LOG_TAG fmt, __FUNCTION__, __LINE__, ##args)
typedef struct Node{
struct Node *prev;
struct Node *next;
int elements;
}pNode;
pNode * CreateHead(void)
{
pNode *head = NULL;
head = (pNode *)malloc(sizeof(struct Node));
head->next = NULL;
head->prev = NULL;
return head;
}
int InsertElement(pNode *head,int element)
{
if(head == NULL)
{
PRINTK_LINK("Head NULL\n");
return (-1);
}
pNode * pTemp = head;
while(pTemp->next != NULL)
{
pTemp = pTemp->next;
}
pNode * pElement = (pNode *)malloc(sizeof(struct Node));
pElement->elements = element;
pTemp->next = pElement;
pElement->prev = pTemp;
PRINTK_LINK("Element:%d\n",element);
return (0);
}
int TraverseLink(pNode *head)
{
if(head == NULL)
{
PRINTK_LINK("Head NULL\n");
return (-1);
}
pNode * pTemp = head;
while(pTemp->next != NULL)
{
pTemp = pTemp->next;
PRINTK_LINK("Element:%d\n",pTemp->elements);
}
return (0);
}
int DeleteLink(pNode *head)
{
if(head == NULL)
{
PRINTK_LINK("Head NULL\n");
return (-1);
}
pNode * pTemp = head;
while(pTemp->next != NULL)
{
pTemp = pTemp->next;
}
while(pTemp != NULL)
{
free(pTemp);
pTemp = pTemp->prev;
}
return (0);
}
int main()
{
pNode * pHead = CreateHead();
InsertElement(pHead,13);
InsertElement(pHead,8);
InsertElement(pHead,0);
InsertElement(pHead,4);
InsertElement(pHead,485);
InsertElement(pHead,94);
TraverseLink(pHead);
DeleteLink(pHead);
return 0;
}
▌程序輸出
ubuntu1804:~/c$ gcc shuanglianbiao.c && ./a.out
[LINK]: InsertElement() line: 40 Element:13
[LINK]: InsertElement() line: 40 Element:8
[LINK]: InsertElement() line: 40 Element:0
[LINK]: InsertElement() line: 40 Element:4
[LINK]: InsertElement() line: 40 Element:485
[LINK]: InsertElement() line: 40 Element:94
[LINK]: TraverseLink() line: 56 Element:13
[LINK]: TraverseLink() line: 56 Element:8
[LINK]: TraverseLink() line: 56 Element:0
[LINK]: TraverseLink() line: 56 Element:4
[LINK]: TraverseLink() line: 56 Element:485
[LINK]: TraverseLink() line: 56 Element:94
▌總結(jié)
我上面的代碼只設(shè)計(jì)了鏈表頭，如果設(shè)計(jì)鏈表尾部指針，應(yīng)用會(huì)更加靈活。
相比于單鏈表，雙鏈表的操作會(huì)更加靈活，當(dāng)然，每一個(gè)節(jié)點(diǎn)都需要新增一個(gè)指向于上一個(gè)位置的指針。
雙鏈表還可以把頭尾連接起來變成一個(gè)環(huán)形隊(duì)列。
鏈表相對(duì)于數(shù)組來說，插入和刪除數(shù)據(jù)非?？?，因?yàn)椴恍枰苿?dòng)數(shù)據(jù)，只需要改變指針的指向。
雙鏈表內(nèi)存利用率高，如果是內(nèi)存緊張的硬件設(shè)備，使用鏈表操作可以節(jié)省內(nèi)存。相對(duì)于數(shù)組，鏈表可以做到按需分配內(nèi)存。
鏈表是一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，建議做到自己能寫出一個(gè)鏈表，不要求十全十美，我曾經(jīng)面試遇到讓我手?jǐn)]一個(gè)棧。相對(duì)于那些C語言基礎(chǔ)，寫代碼更能彰顯程序員的技術(shù)。
