目錄

1.鏈表的基本概念

2.鏈表的實(shí)現(xiàn) -- 節(jié)點(diǎn)的構(gòu)造和鏈接

? ? ? ? 節(jié)點(diǎn)如何構(gòu)造?

? ? ? ? 如何將鏈表關(guān)聯(lián)起來?

3.鏈表的方法(功能)

1).display() -- 鏈表的遍歷

2).size() -- 求鏈表的長度

3).addFirst(int val) -- 頭插法

4).addLast(int val) -- 尾插法

5).addIndex -- 在任意位置插入

6).contains(int val) -- 鏈表中是否包含某個元素

7). remove(int key) -- 刪除第一次出現(xiàn)的關(guān)鍵字的節(jié)點(diǎn)

8).removeAll(int val) -- 刪除所有出現(xiàn)的關(guān)鍵字的節(jié)點(diǎn)

9).clear() -- 清空

? ? ? ? 回收對象,防止浪費(fèi) : head == null;

---

---

1.鏈表的基本概念

• 鏈表（Linked List）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)（Node）組成，每個節(jié)點(diǎn)包含兩部分：一部分存放數(shù)據(jù)元素，另一部分存放指向下一個節(jié)點(diǎn)的指針.

2.鏈表的實(shí)現(xiàn) -- 節(jié)點(diǎn)的構(gòu)造和鏈接

? ? ? ? 節(jié)點(diǎn)如何構(gòu)造?

在 Java 中，通常通過定義一個類來表示鏈表中的節(jié)點(diǎn)。每個節(jié)點(diǎn)通常包含兩個部分：數(shù)據(jù)域和指針域。對于單向鏈表，每個節(jié)點(diǎn)的指針域指向下一個節(jié)點(diǎn).

public class LinkedList {// 定義鏈表節(jié)點(diǎn)static class ListNode {int val; // 數(shù)據(jù)域ListNode next; // 指針域ListNode(int x) {this.val = x;this.next = null;}}public ListNode head;
}

? ? ? ? 如何將鏈表關(guān)聯(lián)起來?

通過訪問node1的指針域next,將其賦值為下一個節(jié)點(diǎn)的地址,以此類推,最后讓頭節(jié)點(diǎn)head指向第一個節(jié)點(diǎn)node1.

        node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;

3.鏈表的方法(功能)

1).display() -- 鏈表的遍歷

首先，我們創(chuàng)建一個名為 cur 的局部變量，它是一個指向 ListNode 類型的引用。將鏈表的頭節(jié)點(diǎn)（head）賦值給 cur，這樣我們就有了一個可以用來遍歷整個鏈表的起始點(diǎn).使用 while 循環(huán)來遍歷鏈表。只要 cur不是 null（即還沒有到達(dá)鏈表的末尾），就繼續(xù)執(zhí)行循環(huán)體內(nèi)的代碼。如果 cur?是 null，則說明已經(jīng)到了鏈表的末尾，循環(huán)結(jié)束。在循環(huán)體內(nèi)，我們使用 System.out.print 來打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)。這里用 + " -> " 格式化輸出，以箭頭分隔各個數(shù)據(jù)項，直觀地表示出它們之間的鏈接關(guān)系。更新 cur指針，使其指向下一個節(jié)點(diǎn)（通過 cur.next 獲取）。這一步非常重要，因?yàn)樗_保了我們在下一次迭代時能夠訪問鏈表中的下一個節(jié)點(diǎn)。當(dāng)循環(huán)結(jié)束后，我們額外打印一個 null，表示鏈表的終止。這是為了更清晰地展示鏈表結(jié)構(gòu)，表明沒有更多的節(jié)點(diǎn)了。

public void display() {ListNode cur = head;while(cur != null) {System.out.print(cur.val + "->");cur = cur.next;}System.out.println("null");}

2).size() -- 求鏈表的長度

? ? ? ? 定義count變量,記錄cur向后走的次數(shù),每走一步,count++

public int size() {ListNode cur = head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}

3).addFirst(int val) -- 頭插法

? ? ? ? 1. 將head頭節(jié)點(diǎn)的地址傳給node.next? 2. 然后讓head指向node

? ? ? ? 注意: 這里兩步的順序不可以交換 , 否則 就是自己指向自己了

public void addFirst(int val) {ListNode node = new ListNode(val);node.next = head;head = node;}

4).addLast(int val) -- 尾插法

? ? ? ? 1.為了避免head == null 報錯, 先進(jìn)行判斷,若head == null , 則 head =?node,然后return掉.

? ? ? ? 2.若head != null , 則 這通過循環(huán)找到 cur.next == null ,最后讓cur.next = node.

public void addLast(int val) {ListNode node = new ListNode(val);if(head == null) {head = node;return;}ListNode cur = head;while(cur.next != null) {cur = cur.next;}cur.next = node;}

5).addIndex -- 在任意位置插入

1.判斷index的合法性: (1).?定義一個 checkIndex(int index) 方法用來檢查 index 的合法性

2.index == 0 || index == size();前者相當(dāng)于是頭插，直接調(diào)用 addFirst(),后者相當(dāng)于是尾插，直接調(diào)用 addLast()

3.找到 index 的前一個位置,創(chuàng)建一個 findIndexSubOne(int index) 方法,創(chuàng)建一個節(jié)點(diǎn) cur 來接收調(diào)用方法的返回值, 最后 cur 就是 index 位置的前一個節(jié)點(diǎn)了

4.進(jìn)行連接,實(shí)例化一個所帶數(shù)據(jù)為 val 的節(jié)點(diǎn) node,

node.next = cur.next;

cur.next = node;

public void addIndex(int index,int val) {// 1.判斷index的合法性try {checkIndex(index);} catch(IndexNotLegalException e) {e.printStackTrace();}// index == 0 || index == size()if(index == 0) {addFirst(val);return;} else if(index == size()) {addLast(val);return;}// 3.找到index前一個位置ListNode cur = findIndexSubOne(index);// 4.進(jìn)行連接ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}public ListNode findIndexSubOne(int index) {ListNode cur = head;for (int i = 0; i < index - 1; i++) {cur = cur.next;}return cur;}public void checkIndex(int index) {if(index < 0 || index >size()) {throw new IndexNotLegalException("index位置不合法");}}public class IndexNotLegalException extends RuntimeException {public IndexNotLegalException() {}public IndexNotLegalException(String message) {super(message);}}

6).contains(int val) -- 鏈表中是否包含某個元素

遍歷鏈表,如果能在鏈表中找到val,則返回true,否則,返回false

public boolean contains(int val) {ListNode cur = head;while(cur != null) {if(cur.val == val) {return true;}cur = cur.next;}return false;}

7). remove(int key) -- 刪除第一次出現(xiàn)的關(guān)鍵字的節(jié)點(diǎn)

? ? ? ? 1.首先判斷鏈表是否為空

? ? ? ? 2.循環(huán)遍歷 : cur.next != null

? ? ? ? 3.找到val值的前一個節(jié)點(diǎn)cur : 當(dāng)cur.next.val = val 時,找到目標(biāo)

? ? ? ? 4.進(jìn)行刪除

????????

public void remove(int key) {// 如果鏈表為空if(head == null) {return;}// 如果第一個元素就為val時if(head.val == key) {head = head.next;return;}ListNode cur = head;while(cur.next != null) {if(cur.next.val == key) {cur.next = cur.next.next;return;}cur = cur.next;}}

8).removeAll(int val) -- 刪除所有出現(xiàn)的關(guān)鍵字的節(jié)點(diǎn)

• 定義兩個引用變量
  • cur 代表當(dāng)前需要刪除的節(jié)點(diǎn)
  • prev 代表當(dāng)前需要刪除節(jié)點(diǎn)的前驅(qū)

1. 若?cur.val == val
   1. prev.next = cur.next
   2. cur = cur.next
2. 否則：
   1. prev = cur
   2. cur = cur.next
3. 處理頭節(jié)點(diǎn)

public void removeAll(int key) {if(head == null) {return;}ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;} else {prev = cur;cur = cur.next;}}// 除了頭節(jié)點(diǎn)都刪除完成if(head.val == key) {head = head.next;}}

9).clear() -- 清空

? ? ? ? 回收對象,防止浪費(fèi) : head == null;

public void clear() {this.head = null;}