更新時(shí)間:2020-10-13 來(lái)源:黑馬程序員 瀏覽量:
雙向鏈表中雙向的意思是說(shuō)前后節(jié)點(diǎn)之間互相有引用,鏈表的節(jié)點(diǎn)我們稱為 Node。Node
有三個(gè)屬性組成:其前一個(gè)節(jié)點(diǎn),本身節(jié)點(diǎn)的值,其下一個(gè)節(jié)點(diǎn),假設(shè) A、B 節(jié)點(diǎn)相鄰,A 節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)就是 B,B 節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)就是
A,兩者互相引用,在鏈表的頭部節(jié)點(diǎn),我們稱為頭節(jié)點(diǎn)。頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)是 null,尾部稱為尾節(jié)點(diǎn),尾節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)是
null,如果鏈表數(shù)據(jù)為空的話,頭尾節(jié)點(diǎn)是同一個(gè)節(jié)點(diǎn),本身是 null,指向前后節(jié)點(diǎn)的值也是 null。
雙向鏈表如何實(shí)現(xiàn)新增和刪除節(jié)點(diǎn)?
新增:我們可以選擇從鏈表頭新增,也可以選擇從鏈表尾新增,如果是從鏈表尾新增的話,直接把當(dāng)前節(jié)點(diǎn)追加到尾節(jié)點(diǎn)之后,本身節(jié)點(diǎn)自動(dòng)變?yōu)槲补?jié)點(diǎn)。
刪除:把刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)的 prev 指向其前一個(gè)節(jié)點(diǎn),把刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的 next 指向其后一個(gè)節(jié)點(diǎn),最后把刪除的節(jié)點(diǎn)置為 null
即可。
猜你喜歡:
LinkedList和ArrayList對(duì)比各有什么優(yōu)勢(shì)?