1. ArrayList的缺陷
順序表只適合靜態(tài)的查找和更新，不適合插入和刪除元素，
因為在ArrayList中插入和刪除元素時，由于需要將后序元素往前后者往后移動，所以時間復雜度會相當高，能達到O(N)。
為了解決這一問題，java 引入了 LinkedList(鏈表)。
2. 鏈表
2.1 鏈表的概念以及結構
鏈表是一種邏輯上連續(xù)，物理上不連續(xù)的存儲結構。
鏈表是由一個個節(jié)點連接構成的，一個節(jié)點包含 val 域和 next?域。
邏輯上連續(xù)是因為鏈表有一個 next 域，這個 next 域會指向下一個節(jié)點。
每個節(jié)點都是一個對象，因此他們都會有屬于自己的地址。
上圖就是一個不帶頭單向非循環(huán)的鏈表。
其實，鏈表的結構有很多種。
1. 帶頭和不帶頭
此處的帶頭和不帶頭指的是，是否有一個虛擬的頭節(jié)點，該頭節(jié)點的 val 是無效值，該頭節(jié)點的下一個節(jié)點才是鏈表的第一個節(jié)點，head 會固定指向該虛擬的頭節(jié)點，不能修改 head 的指向。
2. 單向和雙向
單向和雙向，顧名思義，就是只能指向一個方向的和能夠指向兩個方向的
單向的鏈表只有兩個域(val + next)，而雙向的鏈表則比單向的鏈表多一個域 prev
單向的鏈表只能向后(next)走，而雙向的鏈表既能向后(next)走，也能向前(prev)走
3. 循環(huán)和非循環(huán)
顧名思義，就是循環(huán)的鏈表和不是循環(huán)的鏈表咯
雖然鏈表的種類有這么多，但是我們只用重點掌握兩種：單向不帶頭非循環(huán)和雙向不帶頭非循環(huán)。
單向不帶頭非循環(huán)：結構簡單，面試題考的多。
雙向不帶頭非循環(huán)：LinkedList 的底層實現(xiàn)結構就是雙向不帶頭非循環(huán)鏈表。
2.2 鏈表的實現(xiàn)
此處鏈表的實現(xiàn)，實現(xiàn)的是單向不帶頭非循環(huán)鏈表。
要實現(xiàn)一個鏈表，我們就得先創(chuàng)建一個 MySingleList 類，我們要實現(xiàn)的就是?MySingleList 類。
由剛剛學過的知識可以知道，鏈表是由一個個節(jié)點組成的，節(jié)點是鏈表的一部分
所以我們還需要定義一個靜態(tài)內部類 ListNode 作為節(jié)點。
一個節(jié)點 = val + next ,所以 ListNode 有兩個成員變量，
我們順便再把 ListNode 的構造方法寫出來。
而鏈表本身自帶一個 head 節(jié)點指向頭節(jié)點，所以我們還需要定義一個成員變量 head
?因為沒有一個完整的鏈表，所以我們可以寫一個方法，手動創(chuàng)建一個鏈表，這樣方便我們測試這個鏈表方法寫對沒。
要實現(xiàn)鏈表，則需要實現(xiàn)以下方法
//頭插法
public void addFirst(int data) {
}
//尾插法
public void addLast(int data) {
}
//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
public void addIndex(int index, int data) {
}
//查找是否包含關鍵字key是否在單鏈表當中
public boolean contains(int key) {
return false;
}
//刪除第一次出現(xiàn)關鍵字為key的節(jié)點
public void remove(int key) {
}
//刪除所有值為key的節(jié)點
public void removeAllKey(int key) {
}
//得到單鏈表的長度
public int size() {
return -1;
}
//清空鏈表
public void clear() {
}
//打印鏈表
public void display() {
}我們可以先挑選簡單的實現(xiàn)，可以選擇先實現(xiàn) size，display，contains 和 clear
那我們就先來實現(xiàn) size 方法，求鏈表的長度。
思路就是遍歷鏈表，遇到一個節(jié)點，count就++。
那我們就可以定義一個 cur ，cur 指向 head，然后遍歷即可
不能直接用 head 來遍歷鏈表，因為如果 head 走了，鏈表就不知道從哪里開始了。
然后我們再來實現(xiàn) display ，打印鏈表
?同理，我們要把鏈表的每一個數(shù)字都打印出來，就需要遍歷鏈表，
遍歷到一個節(jié)點，就打印一個節(jié)點。
再來實現(xiàn) contains 方法，查找 key 是否在鏈表中存在，
這個也一樣，遍歷鏈表，找到了就返回 true ， 遍歷完鏈表了還找不到，那就返回 false
再來實現(xiàn) clear，這不簡單，只要將頭節(jié)點置 null 了，鏈表也就清空了?
再來實現(xiàn) addFirst ，頭插法
頭插法的意思就是，新增一個節(jié)點，將該節(jié)點插入到鏈表的第一個，也就是頭節(jié)點的位置。
分兩種情況，第一種，鏈表為空，第二種，鏈表不為空。
如果鏈表為空，說明鏈表里面沒有節(jié)點，那新增的這個 node 節(jié)點就是鏈表的第一個節(jié)點，也就是頭節(jié)點。
如果鏈表不為空，那我們需要牢記這一點：插入節(jié)點的時候，先綁定后面的數(shù)據(jù)，再來插入節(jié)點
?如上圖解
再來實現(xiàn) addLast，尾插法，與頭插法類似
尾插法，就是把新增的節(jié)點插入到鏈表的尾巴，也就是鏈表最后一個節(jié)點的位置 。
同理，尾插法也分為兩種情況，
第一種，鏈表為空，說明鏈表里面一個節(jié)點都沒有，所以新增的節(jié)點，就相當于鏈表的第一個節(jié)點，也就是頭節(jié)點。
第二種，鏈表不為空，新增的節(jié)點要插入到鏈表的尾巴，則需要先找到鏈表的尾巴節(jié)點，再來插入。
由上圖，我們不難發(fā)現(xiàn)，鏈表尾巴節(jié)點和其他節(jié)點的區(qū)別：那就是尾巴節(jié)點的 next 域 為 null
所以，我們就能借助這點，找到鏈表的尾巴節(jié)點。
?
再來寫 addIndex，指定位置插入?
因為 addIndex 方法含有參數(shù) index，所以根據(jù) index ，分為四種情況
第一種，非法情況，如果下標小于0或者大于鏈表的長度，則不合法，不合法就不用插了。
第二種，下標剛好是0，說明是頭插法，直接調用我們剛剛寫好的 addFirst 即可。
第三種，下標剛好是鏈表長度，說明是插在最后一個位置，尾插法，直接調用 addLast 即可。
第四種，index 不是以上三種情況，說明 index?位置是在鏈表中間位置。
則需要我們先找到下標位置的前一個節(jié)點，然后綁定數(shù)據(jù)，再來插入
?
然后我們再來實現(xiàn) remove 方法，刪除第一個關鍵字為 key 的節(jié)點
那很簡單，首先要找到關鍵字為 key 的節(jié)點，再來刪除。
如果鏈表為 null ，說明沒有節(jié)點給你刪除
如果 head.val == key,說明刪除頭節(jié)點
因為要刪除 key 的節(jié)點，所以得先找到 關鍵字為 key 的節(jié)點的前一個節(jié)點，才能進行刪除
所以我們可以單獨寫一個方法，來找，關鍵字為 key 的節(jié)點的前一個節(jié)點。
遍歷鏈表，找 key 的節(jié)點 的前一個，找到了就返回該節(jié)點，找不到就返回 null?
找到了 prev(key節(jié)點的前一個節(jié)點)之后，就直接刪除 prev.next 即可
?再來實現(xiàn) removeAllKey 方法，刪除所有值為 key 的節(jié)點
public class MySingleList {
static class ListNode {
//一個節(jié)點包含 val 和 next
public int val;//節(jié)點的值域
public ListNode next;//下一個節(jié)點的地址
//提供構造方法
public ListNode(int val) {
this.val = val;
}
}
//對于鏈表本身來說，必須得有一個頭結點
public ListNode head;//指向當前鏈表的頭節(jié)點
public void createList() {
//創(chuàng)建鏈表，讓每個節(jié)點連起來即可
ListNode n1 = new ListNode(12);
ListNode n2 = new ListNode(23);
ListNode n3 = new ListNode(34);
ListNode n4 = new ListNode(45);
ListNode n5 = new ListNode(56);
//通過 next 建立節(jié)點之間的聯(lián)系
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
this.head = n1;
}
//得到單鏈表的長度
public int size() {
int count = 0;
//用 cur 來遍歷鏈表
ListNode cur = head;
//cur == null說明鏈表遍歷完了
while (cur != null) {
count++;
cur = cur.next;//讓 cur 指向下一個節(jié)點
}
return count;
}
//打印鏈表
public void display() {
ListNode cur = head;
//遍歷鏈表
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//查找是否包含關鍵字key是否在單鏈表當中
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
//遍歷鏈表，找到了就返回 true
if (cur.val == key) {
return true;
}
cur = cur.next;
}
//找不到就返回 false
return false;
}
//清空鏈表
public void clear() {
this.head = null;//頭節(jié)點為null，就找不到其他結點了
}
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
return;
}
//綁定后面的數(shù)據(jù)
node.next = head;
//更新頭
head = node;
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
//如果 head 為 null ，說明鏈表沒有結點
if (head == null) {
head = node;
return;
}
ListNode cur = head;
//找到鏈表的尾巴節(jié)點
while (cur.next != null) {
cur = cur.next;
}
//到了這里說明 cur 指向了尾巴節(jié)點
//插入
cur.next = node;
}
//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
public void addIndex(int index, int data) {
// index 不合法，則不能插入
if (index < 0 || index > size()) {
return;
}
if (index == 0) {
//頭插法
addFirst(data);
return;
}
if (index == size()) {
//尾插法
addLast(data);
return;
}
//中間位置
ListNode cur = head;
//走 index - 1 步,找到要刪除結點位置的前一個結點
int step = index - 1;
while (step != 0) {
cur = cur.next;
step--;
}
//先綁定后面的數(shù)據(jù)
ListNode node = new ListNode(data);
node.next = cur.next;
//再來插入
cur.next = node;
}
//刪除第一次出現(xiàn)關鍵字為key的節(jié)點
public void remove(int key) {
//空表刪不了
if (head == null) {
return;
}
//如果是頭節(jié)點
if (head.val == key) {
head = head.next;
return;
}
//找到 key 節(jié)點的前一個節(jié)點
ListNode prev = findKeySubOne(key);
if (prev == null) {
//說明不存在 key 節(jié)點的前一個節(jié)點
return;
} else {
ListNode target = prev.next;// target 為要刪除的節(jié)點
//刪除
prev.next = target.next;
}
}
private ListNode findKeySubOne(int key) {
//空表
if (head == null) {
return null;
}
ListNode cur = head;
//找到要刪除的前一個結點
//必須得判斷 cur.next 是否為空，不然有可能會空指針異常
//如果 cur.next == null,那么 cur 已經(jīng)是尾巴結點，就沒有繼續(xù)判斷的必要了
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//刪除所有值為key的節(jié)點
public void removeAllKey(int key) {
//空表
if (head == null) {
return;
}
ListNode prev = head;// prev 為 del 的前一個
ListNode del = head.next;// del 表示要刪除的元素
// del 不為空，說明還有，有可能要刪除的節(jié)點
while (del != null) {
if (del.val == key) {
//刪除
prev.next = del.next;
//del往后走
del = del.next;
} else {
//兩個都往后走
prev = del;
del = del.next;
}
}
//最后再來判斷頭節(jié)點
if (head.val == key) {
head = head.next;
}
}
}?3. 鏈表練習題
203.?移除鏈表元素
?
剛剛寫過刪除所有值為 key 的節(jié)點，直接復制代碼到 LeetCode 上，改下方法名字即可。
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
ListNode prev = head;
ListNode del = head.next;
while (del != null) {
if (del.val == val) {
prev.next = del.next;
del = del.next;
} else {
prev = del;
del = del.next;
}
}
if (head.val == val) {
head = head.next;
}
return head;
}
}206.?反轉鏈表
這道題，思路就是頭插法，從第二個節(jié)點開始遍歷鏈表，對鏈表的每個元素進行頭插法即可。
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode cur = head.next;//從第二個節(jié)點開始反轉
ListNode prev = head;// prev 相當于新頭
head.next = null;//置空，防止循環(huán)
while (cur != null) {
ListNode curNext = cur.next;
//頭插法
cur.next = prev;//頭插
prev = cur;//更新
cur = curNext;//cur繼續(xù)往后走
}
return prev;
}
}??
876.?鏈表的中間結點
思路：快慢指針，相同時間，速度兩倍，路程兩倍
class Solution {
//找中間結點
public ListNode middleNode(ListNode head) {
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
//遍歷鏈表，防止空指針異常
while (fast != null && fast.next != null) {
fast = fast.next.next;//一次走兩步
slow = slow.next;//一次走一步
}
return slow;
}
}鏈表中倒數(shù)第k個結點
?思路：還是利用快慢指針，先讓 fast 走 k-1步，再讓 fast 和 slow 一起走，等 fast 走到尾巴節(jié)點， slow 就是倒數(shù)第 k 個節(jié)點
public class Solution {
public ListNode FindKthToTail(ListNode head, int k) {
// k 不合法或者鏈表為空
if (head == null || k <= 0) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (k - 1 != 0) {
fast = fast.next;
if (fast == null) {
//說明k比鏈表長度還大
return null;
}
k--;
}
//你先走，然后我們同時同速走，距離不變，就是k-1步，差k個節(jié)點
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
??????21.?合并兩個有序鏈表
思路：與合并2個有序數(shù)組類似，定義一個dummy虛擬頭節(jié)點，如果鏈表1的節(jié)點比鏈表2的節(jié)點小，那就鏈表1的節(jié)點加進來，如果不是，那就鏈表2的節(jié)點加進來，然后對應的鏈表往后走，遍歷完之后，看看哪個鏈表不為空，不為空的鏈表就連接在后面，最后返回 dummy.next 即可。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null && list2 == null) {
return null;
}
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
if (list1 != null) {
cur.next = list1;
}
if (list2 != null) {
cur.next = list2;
}
return dummy.next;
}
}CM11 鏈表分割
思路：與合并有序鏈表類似，但又不完全類似，定義bs，be，as，ae，兩個部分
小于x放到 b 中，大于的放到 a 中，最后讓 be 和 as 連接即可
public class Partition {
public ListNode partition(ListNode pHead, int x) {
//定義 bs,be,as,ae
// 小于 x 放到 b ，大于 x 放到 a 中
//最后連接 be 和 as
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
//遍歷鏈表
while (cur != null) {
//說明是第一次放元素
if (cur.val < x) {
if (bs == null) {
bs = cur;
be = cur;
} else {
be.next = cur;
be = cur;
}
} else {
//第一次
if (as == null) {
as = cur;
ae = cur;
} else {
ae.next = cur;
ae = cur;
}
}
cur = cur.next;
}
//如果第一段為空
if (bs == null) {
return as;
}
//如果a段存在，ae.next需要置空，防止形成循環(huán)
if (as != null) {
ae.next = null;
}
//連接a段和b段
be.next = as;
return bs;
}
}OR36 鏈表的回文結構
思路：1. 找到鏈表的中間節(jié)點 。 2. 反轉中間節(jié)點之后的節(jié)點。 3. 比較
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode fast = head;
ListNode slow = head;
//1. 找到中間節(jié)點
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//2. 反轉中間節(jié)點之后的節(jié)點
ListNode cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;//記錄cur的下一個節(jié)點
cur.next = slow;//反轉
slow = cur;//更新頭
cur = curNext;//cur往后走
}
//3. 比較
while (head != slow) {
//值不相同
if (head.val != slow.val) {
return false;
}
節(jié)點個數(shù)為偶數(shù)個時，相遇的前奏就是這個
if (head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
}160.?相交鏈表
思路：
1.相交主要是Y字型
2.兩個鏈表的長度不一樣 主要體現(xiàn)在相交之前
3.可以讓最長的鏈表先走它們的差值步，然后兩個鏈表再一起走
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null && headB == null) {
return null;
}
//1.分別求出兩個鏈表的長度，然后做差
ListNode pL = headA;//假設A是較長的
ListNode pS = headB;
int lenA = 0;
int lenB = 0;
while (pL != null) {
lenA++;
pL = pL.next;
}
while (pS != null) {
lenB++;
pS = pS.next;
}
int len = lenA - lenB;//記錄差值
pL = headA;//重新回到頭結點
pS = headB;
//進行修正
if (len < 0) {
pL = headB;
pS = headA;
len = lenB - lenA;
}
//2.讓較長的鏈表先走差值步
while (len != 0) {
pL = pL.next;
len--;
}
//3.然后兩個鏈表再一起走
while (pL != null && pS != null) {
if (pL == pS) {
return pL;
}
pL = pL.next;
pS = pS.next;
}
return null;
}
}141.?環(huán)形鏈表
思路：利用快慢指針，fast 一次走2步，slow 一次走一步，如果有環(huán)，那么能追上，沒環(huán)就肯定追不上
public class Solution {
//是否有環(huán)
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;//一次走兩步
slow = slow.next;//一次走一步
//相當于追及問題，slow在追fast，有環(huán)就能追上，沒環(huán)就追不上
if (fast == slow) {
return true;
}
}
return false;
}
}142.?環(huán)形鏈表 II
思路：快慢指針，當 fast 與 slow 相遇時，讓 fast 從 head 開始，和 slow 同速一起走，當 slow
?和 fast 再次相遇時，該相遇點就是環(huán)的入口點
public class Solution {
//返回環(huán)的入口點
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
//相遇后，
//相遇點到入口點的距離與起始點到入口點的距離相等
fast = head;
while (fast != null && slow != null) {
if (fast == slow) {
return fast;//如果fast與slow再次相遇，則該點為入口點
}
fast = fast.next;
slow = slow.next;
}
}
}
return null;
}
}?4. LinkedList的模擬實現(xiàn)
和單鏈表同理，只是雙向無頭非循環(huán)鏈表多了一個 prev 域
與單鏈表相同，雙向鏈表也由一個個節(jié)點組成，所以同理，我們要定義一個靜態(tài)內部類，相比于單鏈表，雙鏈表還多了一個尾巴節(jié)點，尾巴節(jié)點 last 會指向雙鏈表的最后一個節(jié)點
雙向鏈表與單鏈表相同，也要實現(xiàn)以下方法
//頭插法
public void addFirst(int data) {
}
//尾插法
public void addLast(int data) {
}
//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
public void addIndex(int index, int data) {
}
//查找是否包含關鍵字key是否在鏈表當中
public boolean contains(int key) {
}
//刪除第一次出現(xiàn)關鍵字為key的節(jié)點
public void remove(int key) {
}
//刪除所有值為key的節(jié)點
public void removeAllKey(int key) {
}
//得到鏈表的長度
public int size() {
}
public void display() {
}
public void clear() {
}同樣的，我們先選擇實現(xiàn) size，display，contains?方法
這些方法的實現(xiàn)與單鏈表沒什么區(qū)別，直接按照你寫單鏈表的方式來寫上述三個方法即可。
再來實現(xiàn) clear 方法，需要注意，每一個節(jié)點的 prev 和 next 都要手動置空，last 和 head 也要置空
再來實現(xiàn)頭插法，與單鏈表類似，分兩種情況
第一種，鏈表為空，說明新增的節(jié)點既是頭節(jié)點又是尾巴節(jié)點
第二種，鏈表不為空，則先需要綁定后面的數(shù)據(jù)，再來插入
再來實現(xiàn)尾插法，同樣與單鏈表類似，分兩種情況
第一種，鏈表為空，相當于頭插
第二種，鏈表不為空，先綁定數(shù)據(jù)，再來插入
再來實現(xiàn) addIndex，與單鏈表類似，分四種情況
第一種，index 不合法，不能插入
第二種，index = 0，相當于頭插法
第三種，index = size() ,相當于尾插法
第四種，不是以上三種情況，首先先找到 index 下標的節(jié)點，先綁定數(shù)據(jù)，再進行插入
第四種情況與單鏈表類似，先讓 cur 走 index 步，然后綁定數(shù)據(jù)，進行插入。
然后我們再來實現(xiàn) remove 方法，
思路：遍歷鏈表，如果要刪除的是頭節(jié)點，就需要考慮該鏈表是否只有一個節(jié)點，
如果要刪除的不是頭節(jié)點，那就得判斷要刪除的節(jié)點是尾巴節(jié)點，還是中間節(jié)點
再來實現(xiàn) removeAllKey 方法，思路與 remove 方法類似，只不過 remove 方法是刪一次就走人了，而?removeAllKey 方法，是要刪除多次
// 無頭雙向鏈表實現(xiàn)
public class MyLinkedList {
static class ListNode {
public int val;//節(jié)點的值域
public ListNode prev;//指向上一個節(jié)點
public ListNode next;//指向下一個節(jié)點
//提供構造方法
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//頭節(jié)點
public ListNode last;//尾巴節(jié)點
//得到鏈表的長度
public int size() {
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
}
//查找是否包含關鍵字key是否在鏈表當中
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
public void clear() {
ListNode cur = head;
//要將鏈表的每一個元素手動置空
while (cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
this.head = null;
this.last = null;
}
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
} else {
//先綁定數(shù)據(jù)
node.next = head;
head.prev = node;
//再來插入
head = node;///更新頭
}
}
//尾插法
public void addLast(int data) {
if (head == null) {
addFirst(data);
} else {
ListNode node = new ListNode(data);
//先綁定數(shù)據(jù)
node.prev = last;
last.next = node;
//再進行插入
last = node;
}
}
//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
return;
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
ListNode node = new ListNode(data);
ListNode prev = cur.prev;
//先綁定數(shù)據(jù)
node.prev = prev;
node.next = cur;
//再來插入
prev.next = node;
cur.prev = node;
}
//刪除第一次出現(xiàn)關鍵字為key的節(jié)點
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
//刪除頭節(jié)點
if (cur == head) {
head = head.next;
//考慮只有一個節(jié)點的情況
if (head == null) {
last = null;
} else {
head.prev = null;
}
} else {
//是否是尾巴節(jié)點
if (cur.next == null) {
//刪除尾巴節(jié)點
last = last.prev;
last.next = null;
} else {
//刪除中間節(jié)點
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
//刪完之后就走人
return;
}
cur = cur.next;
}
}
//刪除所有值為key的節(jié)點
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
//刪除頭節(jié)點
if (cur == head) {
head = head.next;
//考慮只有一個節(jié)點的情況
if (head == null) {
last = null;
} else {
head.prev = null;
}
} else {
//是否是尾巴節(jié)點
if (cur.next == null) {
//刪除尾巴節(jié)點
last = last.prev;
last.next = null;
} else {
//刪除中間節(jié)點
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
cur = cur.next;//繼續(xù)刪
} else {
cur = cur.next;
}
}
}
}?5. LinkedList的使用
5.1?LinkedList的構造
5.2?LinkedList的其他常用方法介紹
刷題的時候直接用就行
5.3?LinkedList的遍歷
可以使用 foreach 循環(huán)遍歷，或者使用迭代器遍歷文章來源：http://www.zghlxwxcb.cn/news/detail-696437.html
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
list.add(1);
// 1.使用 foreach 遍歷
for (int x : list) {
System.out.print(x + " ");
}
// 2.使用迭代器遍歷
Iterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}6. ArrayList和LinkedList的區(qū)別
文章來源地址http://www.zghlxwxcb.cn/news/detail-696437.html
到了這里，關于數(shù)據(jù)結構之鏈表 - 超詳細的教程，手把手教你認識并運用鏈表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
