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