生活随笔
收集整理的這篇文章主要介紹了
双向链表及其用法
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
轉(zhuǎn)載自:https://blog.csdn.net/fk5431/article/details/45072935
一、雙向鏈表的定義
雙向鏈表也是鏈表的一種，它每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)結(jié)點(diǎn)，分別指向其直接前驅(qū)和直接后繼。所以我們從雙向鏈表的任意一個(gè)結(jié)點(diǎn)開始都可以很方便的訪問其前驅(qū)元素和后繼元素。
二、雙向鏈表的存儲(chǔ)結(jié)構(gòu)
雙向鏈表也是采用的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它與單鏈表的區(qū)別就是每個(gè)數(shù)據(jù)結(jié)點(diǎn)中多了一個(gè)指向前驅(qū)元素的指針域 ，它的存儲(chǔ)結(jié)構(gòu)如下圖：
當(dāng)雙向鏈表只有一個(gè)結(jié)點(diǎn)的時(shí)候它的存儲(chǔ)結(jié)構(gòu)如下：
?
三、雙向鏈表的實(shí)現(xiàn)與操作
因?yàn)樵陔p向鏈表中，我們可以通過任意一個(gè)結(jié)點(diǎn)訪問到其前驅(qū)元素和后繼元素，時(shí)間復(fù)雜度為O(1)，所以雙向鏈表是十分方便的，我們通常構(gòu)建鏈表也會(huì)選擇去構(gòu)建雙向鏈表。
接下來(lái)看一下雙向鏈表的實(shí)現(xiàn)與操作：
[cpp]?view plaincopy
#include<stdio.h>??#include<stdlib.h>??#include<malloc.h>??typedef?struct?DOUBLE_LIST??{??????int?data;??????struct?DOUBLE_LIST?*prev;??????struct?DOUBLE_LIST?*next;??}double_list;??double_list?*createlist()?????????{??????double_list?*head,?*p,?*q;??????int?n,x;??????head?=?(double_list?*)malloc(sizeof(double_list));??????head->prev?=?head;??????head->next?=?head;??????p?=?head;??????printf("輸入要?jiǎng)?chuàng)建雙向鏈表的元素的個(gè)數(shù)：\n");??????scanf("%d",&n);??????for(int?i=0;i<n;i++)??????{??????????scanf("%d",?&x);??????????q?=?(double_list?*)malloc(sizeof(double_list));??????????q->data?=?x;??????????p->next?=?q;??????????head->prev?=?q;??????????q->prev?=?p;??????????q->next?=?head;??????????p?=?q;??????}??????return?head;??}????void?printlist(double_list?*head)??{??????double_list?*p;??????p?=?head;??????p?=?p->next;??????while(p!=head)??????{??????????printf("%d??",?p->data);??????????p?=?p->next;??????}??????printf("\n");??}????int?lengthlist(double_list?*head)??{??????double_list?*p;??????p?=?head;??????p?=?p->next;??????int?coun?=?0;??????while(p!=head)??????{??????????coun++;??????????p?=?p->next;??????}??????return?coun;??}????void?insertlist_f(double_list?*head,?int?i,?int?data)??{??????double_list?*p?=?head,?*q;??????p?=?p->next;??????i--;??????while(i--)??????????p?=?p->next;??????q?=?(double_list?*)malloc(sizeof(double_list));??????q->data?=?data;??????(p->prev)->next?=?q;??????q->prev?=?p->prev;??????q->next?=?p;??????p->prev?=?q;??}????void?deletelist_i(double_list?*head,?int?i)??{??????double_list?*p?=?head;??????p?=?p->next;??????i--;??????while(i--)??????????p?=?p->next;??????(p->prev)->next?=?p->next;??????(p->next)->prev?=?p->prev;??????free(p);??}????void?deletelist_x(double_list?*head,?int?x)??{??????double_list?*p?=?head,?*q;??????p?=?p->next;??????while(p!=head)??????????if(p->data?==?x)??????????{??????????????q?=?p->next;??????????????(p->prev)->next?=?p->next;??????????????(p->next)->prev?=?p->prev;??????????????free(p);??????????????p?=?q;??????????}??????????else??????????????p?=?p->next;??}????void?sortlist(double_list?*head)????{??????double_list?*p?=?head,?*q,?*t;??????p?=?p->next;??????for(;p!=head;p=p->next)??????????for(t?=?p->next;t!=head;t=t->next)??????????{??????????????if(p->data?>?t->data)??????????????{??????????????????int?a?=?p->data;??????????????????p->data?=?t->data;??????????????????t->data?=?a;??????????????}??????????}??}??int?main()??{??????double_list?*head;??????head?=?createlist();??????deletelist_x(head,?2);????????????printlist(head);??????insertlist_f(head,?2,?2);??????printlist(head);????????return?0;??}??
對(duì)于雙向鏈表的遍歷來(lái)說我只給出了前序遍歷的代碼，沒有寫后序遍歷的代碼，這其實(shí)是差不多的，但是因?yàn)殡p向鏈表可以進(jìn)行兩個(gè)方向的遍歷，這給我們帶來(lái)了很大的方便。
總結(jié)
以上是生活随笔為你收集整理的双向链表及其用法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
