單鏈表詳解
- 一、前言
- 二、什么是鏈表？
- 2.1、鏈表的概念：
- 2.2、兩種重要的單鏈表
- 2.3、關于單鏈表的一些基礎知識
- 三、單鏈表的實作
- 3.1、窮舉法創建一個簡單的鏈表
- 3.2、遍歷鏈表
- 3.3、得到鏈表的長度
- 3.4、頭插法
- 3.5、尾插法
- 3.6、 任意位置插入節點
- 3.7、查找是否包含關鍵字key是否在單鏈表當中
- 3.8、洗掉所有節點
- 3.9、洗掉第一次出現關鍵字為key的節點
- 3.10、洗掉所有值為key的節點
- 四、LeetCode和劍指Offer上的單鏈表面試題
- 五、其他練習題
一、前言
在上篇文章中，我們詳細的講解了順序表，這里鏈接給大家放在下面，沒看過的同學可以看一看，因為單鏈表就是在順序表之上，做出優化的線性表，
新學期預習嗎？保姆級講解資料結構之順序表的9個方法+手撕代碼
大家還記得順序表中的add方法嗎？那寫起來簡直是一個麻煩，又要考慮pos下標是否合法，還得一個一個的把后面的元素移到前面，這樣一來，不僅代碼寫起來麻煩，代碼執行的時間復雜度也高，但也不是沒有優點，
順序表：由陣列構成，那么它也就包含了陣列的特性，
優點：
1、查詢元素時非常方便快捷，可以通過一個下標，能夠快速的找到當前的資料，O(1).
缺點：
1、每次都會浪費大小不等的記憶體，假設當前陣列大小為20；如果你要放第21個元素的時候，就需要擴容，假設擴容2倍后，大小是40，只放一個元素，那么剩下19個就浪費掉了，
2、每次擴容的時候，都需要拷貝陣列的內容，拷貝的程序中也是需要時間的，造成一定程度資源的浪費，
3、洗掉和插入資料的時候，都需要移動資料，
那么問題來了，有沒有一種表，又不浪費記憶體，洗掉、插入資料的時候還方便快捷呢？
這時候能夠解決上面三個問題的鏈表來了！
二、什么是鏈表？
2.1、鏈表的概念：
鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考鏈接次序實作的 ，
2.2、鏈表的分類：鏈表的結構非常多樣化，根據帶頭和不帶頭，雙向和單向，回圈和不回圈可以組成很多種鏈表，
隨便鏈表的種類有很多，但是只需要重點掌握兩種即可，
2.2、兩種重要的單鏈表
1、無頭單向非回圈鏈表：結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結構，如哈希桶、圖的鄰接表等等，另外這種結構在筆試面試中出現很多，
1、無頭雙向回圈鏈表：在Java集合框架當中，LinkedList的底層就是由這種鏈表實作的，
注意：每個鏈表的400、200、300均為節點的參考地址，實際上是以16進制的方式存盤的，這里我為了畫圖方便，進行了簡寫，
2.3、關于單鏈表的一些基礎知識
1、鏈表在邏輯上是連續的，但是物理上不一定是連續的，這里的物理上，指的是記憶體地址上，
2、單鏈表的值域：
對于單鏈表來說，每一個節點都3個屬性，在下圖中最上面的123，指的是當前節點的地址(本來應該是16進制，這里為了方便說明用10進制)，val域：val是value的縮寫，就是值的意思，這里存放的是當前節點需要存盤的資訊，
next域：它的型別是一個節點型別，由于單鏈表在邏輯上是連續的，故對于一個節點來說，它不僅需要存放自己的val值，它還需要存放自己的下一個節點的地址->next，以此來實作邏輯上的連續，
3、單鏈表的結構
頭節點+資料節點
三、單鏈表的實作
光說不練假把式，我們了解了鏈表的結構、用處，現在我們來親手實作一個自己的單鏈表，
3.1、窮舉法創建一個簡單的鏈表
這里我先用窮舉的方式一一創建節點，這樣方便理解，下文再講述用其他方法創建鏈表
public class MylinkedList {
public ListNode head;//標識這個鏈表的頭
/**
* 窮舉法，最簡單的方式把鏈表一個一個列舉出來，
*/
public void createList(){
ListNode listNode1=new ListNode(12);
ListNode listNode2=new ListNode(13);
ListNode listNode3=new ListNode(23);
ListNode listNode4=new ListNode(33);
ListNode listNode5=new ListNode(44);
listNode1.next=listNode2;
listNode2.next=listNode3;
listNode3.next=listNode4;
listNode4.next=listNode5;
//head參考 參考的是listNode1參考 參考的物件
this.head=listNode1;
}
}
class ListNode{
public int val;//值
public ListNode next;//儲存下一個節點的地址，它是一個參考
/**
* 不帶引數的構造方法
*/
public ListNode(){
}
/**
* 帶一個引數的構造方法
*/
public ListNode(int val){
this.val=val;
}
}
現在鏈表有了，那么問題來了，陣列可以通過for回圈的方式遍歷鏈表，或者直接通過陣列下標找到某個節點，那如何遍歷鏈表當中的每個元素呢？
先看這樣一行代碼：
head=head.next;
大家都知道head代表的是頭結點的一個參考，這行代實際上是在修改參考，那把head修改到哪里呢？next指的是當前節點的下一個節點的地址，那么head.next意思就是head的下一個節點，這行代碼就是讓head走到它下一個節點的位置，現在它走到了listNode2的位置，
接下來再看這樣一行代碼
head=head.next.next
聰明如你，假如當前head是listNode2，那么head.next就是listNode3的地址就指的是234，它后面再加一個next，就再指向在一個地址就是了，所以它的意思是讓從listNode2走到listNode4的位置，
慢慢的我們發現，我們可以通過head=head.next的方式讓head這個參考不停的指向下一個節點，這難道不就是在遍歷鏈表嗎？我們讓head走頭開始，每走過一個節點，列印一個節點對應的val值，直到走到最后一個節點，
接下來我們來實作這個方法，
3.2、遍歷鏈表
上面我們已經知道了遍歷鏈表的方式是讓head一直等于head.next，我們如果需要遍歷整個鏈表，就需要給他加一個限制條件，考慮到head具有特殊的含義，我們這里用一個cur節點來遍歷鏈表，this.head=!null
/**
*遍歷鏈表
*
*/
public void disPlay(){
ListNode cur=this.head;
while (cur!=null){
/**
* 注意不能while回圈的判斷條件不能寫成
* this.head.next!=null，
* 這樣的話，最后一個節點是不能被列印的
*
*/
System.out.println(this.head.val);
cur=cur.next;
}
System.out.println();
}
總結：如果想遍歷完鏈表，一定得是cur！==null，這樣才算是遍歷完了，
有了上面的基礎，接下來我們在實作一些更復雜的方法，
3.3、得到鏈表的長度
思路是遍歷一遍鏈表，定義一個計數器count，每遍歷一個節點就讓count+1,遍歷完成后，回傳count的值就是鏈表的長度了，
上代碼！
//得到單鏈表的長度
public int size(){
int count=0;
ListNode cur=this.head;
while (cur!=null){
count++;
cur=cur.next;
}
return count;
}
size方法和display方法差別在多了一個計數器，在同樣遍歷遍歷的基礎下，display方法是列印鏈表的val值，而size方法是讓計數器count+1.
3.4、頭插法
1、剛剛我們以窮舉法這樣的方式創建了一個鏈表，現在我們用頭插法創建鏈表，
對于兩種鏈表，兩種不同的頭插法方式，
（1）：對于無頭單向鏈表，
用藍色字體的Node節點是需要頭插的節點，它當前的val值是110，地址是777，next域是null，對于沒有頭結點的鏈表，頭插法就是直接把需要插入的節點放到當前鏈表的第一個位置即可，
如圖：
對于單向有頭鏈表頭插法就需要把插入的元素放到head節點和head下一個節點直接，因為有頭的鏈表，head不能變，
如圖：
上代碼！
//頭插法 無頭單向鏈表
public void addFirst(int data){
ListNode Node=new ListNode(data);
Node.next=this.head;
this.head=Node;
}
3.5、尾插法
尾插法顧名思義，和頭插法相似，尾插法把需要插入的節點插入到鏈表的尾部即可，但是問題來了，頭插法可以直接插是因為鏈表本來就有head節點，但是鏈表并沒有特別指出尾巴在哪里，所為尾插法第一個要做的是就是找到鏈表的尾巴，然后在插入到最后，修改next，
1、找尾巴：找尾巴還是和size方法類似，定義一個cur節點，讓他一直遍歷，直到cur.next==null，就找到尾巴了，這時停止回圈，不然就指向下一個節點，
2、修改next：找到尾巴之后，讓cur.next=Node就好，讓鏈表原本的尾巴，指向現在的Node節點，
3、還有一件事：萬一鏈表是空的呢？那就是第一次插入了，這時直接讓head=node就好，
上代碼！
//尾插法
public void addLast(int data){
ListNode node=new ListNode(data);
//第一次和不是第一次
if(this.head==null){
this.head=node;
}
else {
ListNode cur=this.head;
while (cur.next!=null){
cur=cur.next;
}
cur.next=node;
}
}
3.6、 任意位置插入節點
這個方法的意思就是在某一個位置，插入一個節點，第一個資料節點為0號下標，以此類推，
這時，需要修改的域有，上一個節點的next域，因為插入后它的next域就應當是當前插入節點的地址了，還有就是當前節點的next域，把它的next域修改成原本3號下標節點的地址，以下是插入的步驟和特殊情況處理，
我們先相處一個基礎版的代碼：
node.next=cur.next;
cur.next=node;
0、index位置小于0或者比鏈表長度還大怎么辦？
1、需要找到插入位置的前一個節點的地址，在上圖是需要先找到1號下標節點的地址，
2、0位置可沒有前一個節點，
3、要插入到最后一個節點怎么做？
這些問題，都會在代碼中解決，
4、找到index下標前一個節點的方法 findInddexSubOne
讓一個參考從頭開始，走index-1步，這是這個參考指向的就是前一個節點，
/**
* 讓一個參考從頭開始，走index-1步
* @param index
* @return
*/
public ListNode findInddexSubOne(int index){
int count=0;
ListNode cur=this.head;
while (count!=index-1){
cur=cur.next;
count++;
}
return cur;
}
整個方法代碼如下：
它有點長，你忍一下，
//任意位置插入,第一個資料節點為0號下標
public void addIndex(int index,int data){
//1、判斷index是否合法
if(index<0 ||index >size()){
System.out.println("index位置不合法");
return;
}
//2、index為0，直接頭插法
if(index==0){
addFirst(data);
return;
}
//3、index==size()，直接尾插法
if(index==size()){
addLast(data);
return;
}
/**
* 4、正常的情況
* cur指向的是一個index-1位置的節點
*/
ListNode cur=findInddexSubOne(index);
ListNode node=new ListNode(data);
node.next=cur.next;
cur.next=node;
}
/**
* 讓一個參考從頭開始，走index-1步
* @param index
* @return
*/
public ListNode findInddexSubOne(int index){
int count=0;
ListNode cur=this.head;
while (count!=index-1){
cur=cur.next;
count++;
}
return cur;
}
3.7、查找是否包含關鍵字key是否在單鏈表當中
遍歷鏈表，定義一個cur參考，從鏈表的頭開始，如果cur的val值和key相等了，就回傳true，如果遍歷完了，還沒有找到，那就是沒有，回傳false，
方法代碼如下：
//查找是否包含關鍵字key是否在單鏈表當中
public boolean contains(int key){
ListNode cur=this.head;
while (cur!=null){
if(cur.val==key){
return true;
}
}
return false;
}
3.8、洗掉所有節點
由于鏈表是都 next域一個個連接起來的，那么洗掉所以節點的一個粗暴的方法就是把所有的next置空，讓每個節點都找不到下一個節點，這樣鏈表就連接不起來，就算是洗掉了，
第一次嘗試：我們試試是否可以像之前遍歷鏈表一樣，將每次經過的cur節點置空它的next域，這樣就把整個鏈表刪完了，
但是當我們實際操作的時候發現，當你將cur節點的next域洗掉的時候，那它要怎么找到下一個節點呢？
我們在定義一個節點curNext保存cur下一個節點就是了，這樣每次洗掉的時候，curNext還可以指向下一個節點，洗掉完之后再讓cur指向curNext，
還有一件事！
節點還有頭結點沒有洗掉，所以當回圈走完，我們還需要讓head節點置空，這樣就是真正的把所有節點洗掉了，
上代碼！
//洗掉所有節點
public void clear(){
ListNode cur=this.head;
while (cur!=null){
ListNode curNext=cur.next;
cur.next=null;
cur=curNext;
}
this.head=null;
}
3.9、洗掉第一次出現關鍵字為key的節點
假設要洗掉的節點是6，下標為del，我們只需要找到它的前驅節點prev，直接讓這個前驅節點和del的下一個節點相連，就變向的忽略的del節點，這就算是洗掉這個這點了，
總結：
1、找到待洗掉節點的前驅節點和下一個節點
2、將前驅節點的next域指向待洗掉節點的next域，
3、有一種特殊情況是頭結點是需要洗掉的節點，那么直接置空就好，
具體細節都在代碼中，找到前驅節點我寫成了一個方法search在下面的代碼中
//找到前序節點 服務于 洗掉第一次出現關鍵字為key的節點
public ListNode searchPrev(int key){
ListNode prev=this.head;
while (prev!=null){
if(prev.next.val==key){
return prev;
}
prev=prev.next;
}
return null; //找完了都沒回傳，說明沒有找到這個節點，
}
洗掉方法
//洗掉第一次出現關鍵字為key的節點
public void remove(int key){
//0、頭結點是要洗掉的節點
if(this.head.val==key){
this.head=this.head.next;
return;
}
//1、找到要洗掉節點的前驅節點
ListNode prev=searchPrev(key);
if(prev==null){
System.out.println("沒有你要洗掉的節點");
return;
}
//2、開始洗掉節點
ListNode del=prev.next;
prev.next=del.next;
}
3.10、洗掉所有值為key的節點
1、上面我們已經寫了9個方法了，相信大家單鏈表已經掌握的不錯了，這是最后一個方法，我們這次將難度上升到面試的高度！ 在只遍歷鏈表一遍的情況下，洗掉所有值為key的節點，
如下圖，有兩個val值為45的節點，我們這個方法需要只遍歷鏈表一遍，就洗掉這兩個val值為45的節點，
思路：
1.定義cur為當前要洗掉的節點，prev為洗掉節點的前驅節點，每次判斷cur.val是否等于key，如果等于key就把prev.next指向cur.next，如果不相等，就讓cur和prev一起向后走，
上代碼
//洗掉所有值為key的節點
public void removeAllKey(int key){
ListNode prev=this.head;
ListNode cur=this.head.next;
while (cur!=null){
if(cur.val==key){
prev.next=cur.next;
cur=cur.next;
}
else {
prev=cur;
cur=cur.next;
}
}
//別忘了頭結點
if(this.head.val==key){
this.head=this.head.next;
}
}
只遍歷一遍就完成了洗掉所以val值等于key的節點，你真棒!
四、LeetCode和劍指Offer上的單鏈表面試題
上面學習完了，怎么創建一個自己單鏈表，并且完成了單鏈表的10個方法，現在來試試挑戰面試題把，題解在下方，加油哦！
劍指 Offer II 021. 洗掉鏈表的倒數第 n 個結點
LeetCode 24：兩兩交換鏈表中的節點、1662. 檢查兩個字串陣列是否相等
leetcode 21. 合并兩個有序鏈表
五、其他練習題
我還總結了一些LeetCode和劍指offer的題解，一起來看看吧！，
劍指 Offer 67. 把字串轉換成整數
怎么把i am a student逆置成student a am i？面試題逆置字串講解
三種方法任君挑選 LeetCode_136只出現一次的數字
什么？動態規劃10行求出連續子陣列的最大和 劍指offer-42講解
劍指 Offer 39. 陣列中出現次數超過一半的數字 簡單易懂14行搞定 ，人人皆可會
二叉樹的層序遍歷原理+LeetCode真題練習
劍指 Offer 58 - II. 左旋轉字串的三種解法一起看看吧！！
字串“aabcccccaaa”壓縮成“a2b1c5a3“還要回傳更小的？力扣面試題 01.06. 字串壓縮講解
字串bit666keji123“中數字的個數？
找到不重復的數字進階版 空間復雜度O(1),時間O(n)平方，不能修改陣列內容，不能對陣列進行排序
LeetCode_231. 判斷一個數是否為2 的冪，與運算一行代碼解決
驗證尼科徹斯定理，即：任何一個整數m的立方都可以寫成m個連續奇數之和
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298115.html
標籤：其他
上一篇：linux作業實戰中的常用命令
下一篇：一道面試題--設計炸船互動游戲