雙鏈表(Double Link List)是一種數(shù)據(jù)結(jié)構(gòu),每個(gè)節(jié)點(diǎn)包含兩個(gè)指針,分別指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)。相比于單鏈表,雙鏈表可以雙向遍歷,刪除和更新操作也更加靈活方便。
下面是在Java中實(shí)現(xiàn)雙鏈表的刪除和更新操作的示例:
刪除操作
雙鏈表的刪除操作需要考慮以下情況:
待刪除節(jié)點(diǎn)是頭節(jié)點(diǎn)
待刪除節(jié)點(diǎn)是尾節(jié)點(diǎn)
待刪除節(jié)點(diǎn)是中間節(jié)點(diǎn)
示例代碼
public class DoublyLinkedList {
// 定義鏈表節(jié)點(diǎn)
class ListNode {
int val;
ListNode prev;
ListNode next;
ListNode(int val) {
this.val = val;
this.prev = null;
this.next = null;
}
}
private ListNode head;
private ListNode tail;
// 刪除節(jié)點(diǎn)
public void deleteNode(ListNode node) {
if (node == head) { // 待刪除節(jié)點(diǎn)是頭節(jié)點(diǎn)
head = head.next;
if (head != null) {
head.prev = null;
} else {
tail = null;
}
} else if (node == tail) { // 待刪除節(jié)點(diǎn)是尾節(jié)點(diǎn)
tail = tail.prev;
tail.next = null;
} else { // 待刪除節(jié)點(diǎn)是中間節(jié)點(diǎn)
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
}
更新操作
雙鏈表的更新操作可以分為兩種情況:
更新節(jié)點(diǎn)的值
將節(jié)點(diǎn)移動(dòng)到另一個(gè)位置
示例代碼如下:
public class DoublyLinkedList {
// 定義鏈表節(jié)點(diǎn)
class ListNode {
int val;
ListNode prev;
ListNode next;
ListNode(int val) {
this.val = val;
this.prev = null;
this.next = null;
}
}
private ListNode head;
private ListNode tail;
// 刪除節(jié)點(diǎn)
public void deleteNode(ListNode node) {
if (node == head) { // 待刪除節(jié)點(diǎn)是頭節(jié)點(diǎn)
head = head.next;
if (head != null) {
head.prev = null;
} else {
tail = null;
}
} else if (node == tail) { // 待刪除節(jié)點(diǎn)是尾節(jié)點(diǎn)
tail = tail.prev;
tail.next = null;
} else { // 待刪除節(jié)點(diǎn)是中間節(jié)點(diǎn)
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
}
以上就是在Java中實(shí)現(xiàn)雙鏈表的刪除和更新操作的示例代碼。