一漠嵌、雙向鏈表
1盖呼、定義：從下圖中的定義結(jié)點(diǎn)的代碼我們能發(fā)現(xiàn)，雙向與單向最明顯的區(qū)別就是是否可以反向查找上一結(jié)點(diǎn)约炎。
2蟹瘾、創(chuàng)建：大致和單向的創(chuàng)建差不多，區(qū)別在于多了prior的處理
步驟：
1憾朴、*L 指向頭結(jié)點(diǎn)
2、新增數(shù)據(jù)：
2.1.創(chuàng)建1個(gè)臨時(shí)的結(jié)點(diǎn)
2.2.為新增的結(jié)點(diǎn)建立雙向鏈表關(guān)系
① temp 是p的后繼
② temp 的前驅(qū)是p
③ p 要記錄最后的結(jié)點(diǎn)的位置,方便下一次插入
3灸拍、插入：
步驟：
1. 插入的位置不合法 為0或者為負(fù)數(shù)
2. 新建結(jié)點(diǎn)
3.將p指向頭結(jié)點(diǎn)!
4. 找到插入位置i直接的結(jié)點(diǎn)
5. 如果插入的位置超過(guò)鏈表本身的長(zhǎng)度
6. 判斷插入位置是否為鏈表尾部
1?? 將p->next 結(jié)點(diǎn)的前驅(qū)prior = temp
2?? 將temp->next 指向原來(lái)的p->next
3?? p->next 更新成新創(chuàng)建的temp
4?? 新創(chuàng)建的temp前驅(qū) = p
4鸡岗、刪除
1.判斷雙向鏈表是否為空,如果為空則返回0
2. 將指針p移動(dòng)到刪除元素位置前一個(gè)
3.如果k>i 或者 p == NULL 則返回0
4.創(chuàng)建臨時(shí)指針delTemp 指向要?jiǎng)h除的結(jié)點(diǎn),并將要?jiǎng)h除的結(jié)點(diǎn)的data 賦值給*e,帶回到main函數(shù)
5. p->next 等于要?jiǎng)h除的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
6. 如果刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)不為空,則將將要?jiǎng)h除的下一個(gè)結(jié)點(diǎn)的前驅(qū)指針賦值p
7. 刪除delTemp結(jié)點(diǎn)
二、雙向循環(huán)鏈表
1声登、創(chuàng)建
步驟：
1、*L 指向頭結(jié)點(diǎn)
2揣苏、新增數(shù)據(jù)：
2.1.創(chuàng)建1個(gè)臨時(shí)的結(jié)點(diǎn)
2.2.為新增的結(jié)點(diǎn)建立雙向鏈表關(guān)系
①?temp 是p的后繼
② temp 的前驅(qū)是p
③ temp的后繼是*L
④ p 的前驅(qū)是新建的temp
⑤ p 要記錄最后的結(jié)點(diǎn)的位置,方便下一次插入
2、插入
步驟：
1. 創(chuàng)建指針p,指向雙向鏈表頭
2.雙向循環(huán)鏈表為空,則返回0
3.找到插入前一個(gè)位置上的結(jié)點(diǎn)p
4.如果i>index 則返回0
5.創(chuàng)建新結(jié)點(diǎn)temp
6.temp 結(jié)點(diǎn)為空,則返回error
7.將生成的新結(jié)點(diǎn)temp數(shù)據(jù)域賦值e.
8.將結(jié)點(diǎn)temp 的前驅(qū)結(jié)點(diǎn)為p;
9.temp的后繼結(jié)點(diǎn)指向p->next;
10.p的后繼結(jié)點(diǎn)為新結(jié)點(diǎn)temp;
11.如果temp 結(jié)點(diǎn)不是最后一個(gè)結(jié)點(diǎn)绅作，temp節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的前驅(qū)為temp 結(jié)點(diǎn)
3蛾派、刪除
步驟：
1.如果刪除到只剩下首元結(jié)點(diǎn)了,則直接將*L置空;
2.找到要?jiǎng)h除的結(jié)點(diǎn)
3.給e賦值要?jiǎng)h除結(jié)點(diǎn)的數(shù)據(jù)域
4.修改被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的后繼指針?
5.修改被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)的前驅(qū)指針?
6. 刪除結(jié)點(diǎn)temp
