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