上篇內(nèi)容給大家?guī)砹藛捂湵淼臉?gòu)建，那么本期內(nèi)容繼續(xù)給大家?guī)礞湵淼南嚓P(guān)內(nèi)容----雙向鏈表。
什么是雙向鏈表？雙向鏈表與單鏈表有什么區(qū)別？
在單鏈表中，咱們每個(gè)結(jié)點(diǎn)的指針域存放了后繼指針，以便于鏈接每個(gè)結(jié)點(diǎn)，隨后講到按位查找，從頭結(jié)點(diǎn)開始，設(shè)置工作指針來不斷延續(xù)搜索，然后找到該結(jié)點(diǎn)并返回其位置，But如果我們想要找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)怎么辦呢？因?yàn)槲覀兠總€(gè)結(jié)點(diǎn)的指針域存放的是后繼結(jié)點(diǎn)的地址，所以我們還需要重新查找該鏈表，那么這個(gè)時(shí)候的時(shí)間復(fù)雜度會(huì)有所提升，這個(gè)時(shí)候我們就要使用雙向鏈表了。
雙向鏈表與單鏈表的區(qū)別無非是其指針域內(nèi)存放的是前驅(qū)結(jié)點(diǎn)的地址和后繼節(jié)點(diǎn)的位置。那么我們采用結(jié)構(gòu)體的形式來定義雙向鏈表：
typedef struct Node
{
int data;//數(shù)據(jù)域
struct Node* prior;//前驅(qū)
struct Node* next;//后繼
}node,*linklist;我們了解到了雙向鏈表的定義，接下倆我們就要探討插入操作了。
我們?cè)诓迦胍粋€(gè)結(jié)點(diǎn)的時(shí)候要保證其與前后結(jié)點(diǎn)能夠鏈接，而雙向鏈表每兩個(gè)結(jié)點(diǎn)之間擁有兩條線，所以這個(gè)時(shí)候就需要鏈接四條線（兩前驅(qū)+兩后繼），舉個(gè)例子：當(dāng)前要把結(jié)點(diǎn)p插入到結(jié)點(diǎn)s的后面：p的前驅(qū)指向s，p的后繼指向s的后繼，s的后繼指向p，s的后繼的前驅(qū)指向p。
p->prior = s;
p->next = s->next;
s->next = p;
s->next->prior = p;完整的插入代碼與單鏈表的代碼差不多，這里就不給大家展示了，大家可以看我上期博客講述的單鏈表的插入。
接下來咱們?cè)撜f一下如何刪除結(jié)點(diǎn)p？
首先我們要斷開四條線，讓p的前驅(qū)與p的后繼鏈接起來，所以就只需要鏈接兩條線就可以了。
p的前驅(qū)的后繼指向p的后繼，p的后繼的前驅(qū)指向p的前驅(qū)。
p-prior->next = p->next;
p->next->prior = p->prior;?其實(shí)理解也就是表述p的前后地址，然后讓p的前驅(qū)與p的后繼相連的過程。
想刪除建立的雙向鏈表，直接構(gòu)造一個(gè)析構(gòu)函數(shù)，設(shè)置一個(gè)工作指針（負(fù)責(zé)記錄刪除的結(jié)點(diǎn)的指針域指向的位置），用delete釋放就over了。文章來源：http://www.zghlxwxcb.cn/news/detail-795017.html
好了本期內(nèi)容就到這里了，感謝收看，希望給個(gè)三連支持。文章來源地址http://www.zghlxwxcb.cn/news/detail-795017.html
到了這里，關(guān)于雙向鏈表的構(gòu)建的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
