網(wǎng)站備案信息真實(shí)性核驗(yàn)單個人產(chǎn)品線上推廣方案
目錄
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ū)
- 若?
cur.val == val
prev.next = cur.next
cur = cur.next
- 否則:
prev = cur
cur = cur.next
- 處理頭節(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;}