雙端鏈表

單鏈表要想在表尾插入一個(gè)鏈結(jié)點(diǎn)，需要遍歷整個(gè)鏈表直到表尾，再進(jìn)行插入，效率很低；

雙端鏈表增加了對(duì)表尾鏈結(jié)點(diǎn)的引用，可以直接在表尾插入鏈結(jié)點(diǎn)；

下面是雙端鏈表的實(shí)現(xiàn)

雙端鏈表的使用

之前有介紹用數(shù)組實(shí)現(xiàn)隊(duì)列，下面提供一個(gè)用雙端鏈表實(shí)現(xiàn)的隊(duì)列, 其中Queue是隊(duì)列的基類(lèi)，若有疑惑，可以先看一下前面講隊(duì)列的文章；

雙向鏈表

傳統(tǒng)鏈表存在的問(wèn)題: 沿鏈表反向遍歷比較困難,很難取得前一個(gè)鏈結(jié)點(diǎn)；

關(guān)鍵點(diǎn): 每個(gè)鏈結(jié)點(diǎn)有兩個(gè)指向其他鏈結(jié)點(diǎn)的引用,而不是一個(gè)；

缺點(diǎn): 每次插入或刪除一個(gè)鏈結(jié)點(diǎn)時(shí),要處理四個(gè)鏈結(jié)點(diǎn)的應(yīng)用,而不是兩個(gè)

可以用來(lái)實(shí)現(xiàn)雙端隊(duì)列；

雙向鏈表的實(shí)現(xiàn)：

1. 首先要重新定義一個(gè)鏈結(jié)點(diǎn)類(lèi)，雙向鏈表的鏈結(jié)點(diǎn)需要保存左右兩個(gè)元素的引用；

2. 雙向鏈表的實(shí)現(xiàn)

雙向鏈表的使用，從兩端分別進(jìn)行插入刪除數(shù)據(jù)

?我是今陽(yáng)，如果想要進(jìn)階和了解更多的干貨，歡迎關(guān)注公眾號(hào)”今陽(yáng)說(shuō)“接收我的最新文章