Java鏈表ListNode詳解

一、鏈表概述

鏈表是一種常用的數據結構，它存儲一系列元素，這些元素由指向下一個元素的指針引用連接而成。鏈表是由節點組成的，每個節點包含一個數據元素和一個指向下一節點的指針。

二、Java中的鏈表

Java語言中的鏈表是通過節點(Node)的方式實現的，每個節點包含三個部分，即指向下一個節點的指針next、節點值value、以及一個前驅指針prev（如果是雙向鏈表）。

三、ListNode類

Java中的鏈表通常是通過ListNode類來實現的。ListNode類是一個簡單的類，包含一個值val和一個指向下一個節點的指針next。

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

四、鏈表的創建

在Java中，可以通過常規的方式來創建一個鏈表，首先聲明一個頭節點(head)，然後在頭節點後面逐個添加新節點。這裡的新節點就是ListNode類的實例。

ListNode head = new ListNode(0);
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
head.next = node1;
node1.next = node2;

五、鏈表的遍歷

鏈表的遍歷是指按順序依次訪問鏈表中的所有節點。Java鏈表的遍歷通常使用while循環，先訪問頭節點(head)，然後循環訪問後續節點，直到訪問到null節點。

ListNode head = new ListNode(0);
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
head.next = node1;
node1.next = node2;
 
ListNode cur = head;
while(cur != null) {
    System.out.println(cur.val);
    cur = cur.next;
}

六、鏈表的插入

鏈表的插入指在鏈表的某個位置上插入新的節點。Java中鏈表的插入一般有三種情況，包括在鏈表的頭部插入節點、在鏈表的尾部插入節點、在鏈表的指定位置插入節點。

（1）在鏈表頭插入節點

首先需要創建一個新的節點，然後將新節點的next指向原來的頭節點，最後將新節點賦值給頭節點。

ListNode newNode = new ListNode(val);
newNode.next = head;
head = newNode;

（2）在鏈表尾部插入節點

遍歷到鏈表尾部，然後在尾部添加新節點。

ListNode newNode = new ListNode(val);
ListNode cur = head;
while (cur.next != null) {
    cur = cur.next;
}
cur.next = newNode;

（3）在鏈表指定位置插入節點

在Java中，鏈表的插入是通過改變節點的指針來完成的。使用pre節點記錄待插入位置的前一節點，然後先將待插入節點的next指向pre.next，再將pre.next指向待插入節點。

ListNode newNode = new ListNode(val);
ListNode pre = head;
for(int i=1; i<pos; i++){
    pre = pre.next;
}
newNode.next = pre.next;
pre.next = newNode;

七、鏈表的刪除

鏈表的刪除是指在鏈表中刪除指定節點。Java中鏈表的刪除分為刪除頭節點、刪除尾節點和刪除中間節點。刪除鏈表節點時需要分別進行內存釋放處理，以避免造成內存泄漏。

（1）刪除頭節點

將頭節點指針移向下一節點。

head = head.next;

（2）刪除尾節點

找到尾節點的前一節點pre，將pre.next置為null，然後釋放掉尾節點。

ListNode cur = head;
while (cur.next.next != null) {
    cur = cur.next;
}
ListNode delNode = cur.next;
cur.next = null;
delNode = null;

（3）刪除中間節點

找到待刪除節點的前一節點pre，先將pre.next指向待刪除節點的下一節點，再釋放掉待刪除節點。

ListNode pre = head;
for(int i=1; i<pos; i++){
    pre = pre.next;
}
ListNode delNode = pre.next;
pre.next = delNode.next;
delNode = null;