Java鏈表超詳細(xì)講解(通俗易懂,含源碼)
概念
鏈表(linked list):是一種物理存儲結(jié)構(gòu)上非連續(xù)存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序?qū)崿F(xiàn)的.
鏈表由一系列結(jié)點(鏈表中每一個元素稱為結(jié)點)組成,結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分:一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域,另一個是存儲下一個結(jié)點地址的指針域。 相比于線性表順序結(jié)構(gòu),操作復(fù)雜。由于不必須按順序存儲,鏈表在插入的時候可以達(dá)到O(1)的復(fù)雜度,比另一種線性表順序表快得多,但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間,而線性表和順序表相應(yīng)的時間復(fù)雜度分別是O(logn)和O(1)。
鏈表的分類
- 單向鏈表,雙向鏈表
- 帶頭鏈表,不帶頭鏈表
- 循環(huán)的,非循環(huán)的
排列組合后一共有
即一共8種鏈表,其中單向、不帶頭、非循環(huán)以及雙向、不帶頭、非循環(huán)的鏈表最為重要,也是本文主要介紹的鏈表類型。
鏈表的結(jié)構(gòu)
對于鏈表的結(jié)構(gòu),可以用如下這個圖來模擬。
圖中所示的為鏈表的一個節(jié)點,value是這個節(jié)點的所存儲的數(shù)據(jù)值,next為下一節(jié)點的地址。
下面是一個5個節(jié)點的鏈表。
接下來,我們來實現(xiàn)這樣的鏈表的增刪查改:
第一個節(jié)點,地址假設(shè)是0x999,存儲的數(shù)據(jù)是11,next存儲的是下一個節(jié)點的地址(假設(shè)是0x888)
第二個節(jié)點,地址假設(shè)是0x888,存儲的數(shù)據(jù)是22,next存儲的是下一個節(jié)點的地址(假設(shè)是0x777)
第三個節(jié)點,地址假設(shè)是0x777,存儲的數(shù)據(jù)是33,next存儲的是下一個節(jié)點的地址(假設(shè)是0x666)
第四個節(jié)點,地址假設(shè)是0x666,存儲的數(shù)據(jù)是44,next存儲的是下一個節(jié)點的地址(假設(shè)是0x555)
第五個節(jié)點,地址假設(shè)是0x555,存儲的數(shù)據(jù)是55,由于沒有后續(xù)節(jié)點,next存儲的是空指針null
定義一個head,存儲頭節(jié)點(第一個節(jié)點)的地址(假設(shè)為0x999)。
代碼實現(xiàn)鏈表
1.創(chuàng)建節(jié)點類
節(jié)點由val域(數(shù)據(jù)域),以及next域(指針域)組成,對于next域,其是引用類型,存放下一個節(jié)點的地址,故
用public ListNode next來創(chuàng)建next。
同時設(shè)置構(gòu)造函數(shù),方便對val進(jìn)行初始化。
//ListNode代表一個節(jié)點 class ListNode{ public int val; public ListNode next; //構(gòu)造函數(shù) public ListNode(int a){ this.val = a; } }
2.創(chuàng)建鏈表
方法一:枚舉法(略簡單,略low)
public class MyLinkedList { public ListNode head;//鏈表的頭 public void creatList(){ ListNode listNode1 = new ListNode(11); ListNode listNode2 = new ListNode(22); ListNode listNode3 = new ListNode(33); ListNode listNode4 = new ListNode(44); ListNode listNode5 = new ListNode(55); this.head = listNode1; listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5; } }
直接進(jìn)行val的賦值以及對next的初始化。
注意:不用對最后一個節(jié)點的next進(jìn)行賦值,因為next是引用類型,不賦值則默認(rèn)為null。
- 方法二:頭插法public void addFirst(int data)
頭插法是指在鏈表的頭節(jié)點的位置插入一個新節(jié)點,定義一個node表示該節(jié)點,然后就是對node的next進(jìn)行賦值,用node.next = this.head即可完成(注意:head應(yīng)指向新節(jié)點)
代碼實現(xiàn)
public void addFirst(int data){ ListNode node = new ListNode(data); node.next = this.head; this.head = node; }
- 方法三:尾插法public void addLast(int data)
尾插法是指在鏈表的尾節(jié)點的位置插入一個新節(jié)點,定義一個node表示該節(jié)點,然后就是對原來最后一個節(jié)點的next進(jìn)行賦值,先將head移動至原來最后一個節(jié)點,用head.next = node進(jìn)行賦值(注意,如果鏈表不為空,需要定義cur來代替head)
代碼實現(xiàn)
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.打印鏈表:public void display()
認(rèn)識了鏈表的結(jié)構(gòu),我們可以知道,節(jié)點與節(jié)點之間通過next產(chǎn)生聯(lián)系。并且我們已將創(chuàng)建了head,即頭節(jié)點的地址,通過head的移動來實現(xiàn)鏈表的打印。
注意:為了使head一直存在且有意義,我們在display()函數(shù)中定義一個cur:ListNode cur = this.head;來替代head。
對于head的移動,可用head = head.next來實現(xiàn)。
代碼實現(xiàn):
public void display(){ ListNode cur = this.head; while(cur != null){ System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); }
4.查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中:public boolean contains(int key)
查找key,可以利用head移動,實現(xiàn)對于key的查找(注意:同樣要定義一個cur來代替head)
代碼實現(xiàn)
public boolean contains(int key){ ListNode cur = this.head; while(cur != null){ if(cur.val == key){ return true; } cur = cur.next; } return false; }
5.得到單鏈表的長度:public int Size()
定義計數(shù)器count = 0,通過head的移動來判斷鏈表長度(注意:同樣要定義一個cur來代替head)
代碼實現(xiàn)
public int Size(){ int count = 0; ListNode cur = this.head; while(cur != null){ count++; cur = cur.next; } return count; }
6.任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標(biāo):public boolean addIndex(int index,int data)
比如,我們把一個值為1314,地址是0x520(設(shè)為node引用)的節(jié)點,即val域值為1314,next域為null,地址是520,將該節(jié)點插入至3號位置,
經(jīng)過分析,需要將head先移至2號位置(注意:用cur代替head,防止head丟失),然后
node.next = cur.next使該節(jié)點的next域改為下一節(jié)點的地址,再cur.next = node.next使前一節(jié)點
的next域改為該節(jié)點的地址。
public void addIndex(int index,int data){ if(index < 0 ||index > Size()){ //對index位置的合法性進(jìn)行判斷 return; } if(index == 0){ //相當(dāng)于頭插法 addFirst(data); return; } if(index = Size()){ //相當(dāng)于尾插法 addLast(data); return; } ListNode cur = findIndex(index);//找到index位置前一位置的地址 ListNode node = new ListNode(data);//初始化node node.next = cur.next; cur.next = node; }
7.刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點:public void remove(int key)
對于刪除第一次出現(xiàn)的key值的節(jié)點,若不是頭節(jié)點,我們只需將key值對應(yīng)的節(jié)點的前一節(jié)點的next的域改為key值對應(yīng)的節(jié)點的next域即可。
對于頭節(jié)點,直接head = head.next即可。
對于key值對應(yīng)的節(jié)點的前一節(jié)點,我們可以寫一個函數(shù)來找到它,方便后續(xù)的代碼書寫。
//找到key的前驅(qū)(前一節(jié)點) public ListNode searchPrev(int key){ ListNode cur = this.head; while(cur.next != null){ if(cur.next.val == key){ return cur; } cur = cur.next; } return null; } //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點 public void remove(int key){ if(this.head == null){ return; } if(this.head.val == key){ this.head = this.head.next; return; } ListNode cur = searchPrev(key); if(cur == null){ return; //沒有要刪除的節(jié)點 } ListNode del = cur.next;//定義要刪除的節(jié)點 cur.next = del.next; }
8.刪除所有值為key的節(jié)點:public void removeAllKey(int key)
若要刪除所有值為key的節(jié)點,其實我們只需多次調(diào)用上面所寫的remove函數(shù)即可完成,但是,
若要達(dá)到面試難度,那么要求就是遍歷一遍鏈表,刪除所有值為key的節(jié)點。
情況一:key連續(xù),如下(1,2,3節(jié)點)
情況二:key不連續(xù),如下(1,3節(jié)點)
代碼實現(xiàn):
public ListNode removeAllKey(int key){ if(this.head = null){ return null; } 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; } return this.head; }
9.清空鏈表:public void clear()
1.簡單粗暴的方法:將頭節(jié)點置為空head = null;即可
2.細(xì)膩溫柔的做法:將每一個節(jié)點都置為空
public void clear(){ while(this.head != null){ ListNode curNext = this.head.next; this.head.next = null; this.head = curNext; } }
源碼
import java.util.List; //ListNode代表一個節(jié)點 class ListNode{ public int val; public ListNode next; //構(gòu)造函數(shù) public ListNode(int a){ this.val = a; } } public class MyLinkedList { public ListNode head;//鏈表的頭 public void creatList() { ListNode listNode1 = new ListNode(11); ListNode listNode2 = new ListNode(22); ListNode listNode3 = new ListNode(33); ListNode listNode4 = new ListNode(44); ListNode listNode5 = new ListNode(55); this.head = listNode1; listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5; } //頭插法 public void addFirst(int data) { ListNode node = new ListNode(data); node.next = this.head; this.head = node; /*if(this.head == null){ this.head = node; }else{ node.next = this.head; this.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; } } //打印順序表 public void display() { ListNode cur = this.head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } //查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中 public boolean contains(int key) { ListNode cur = this.head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next; } return false; } //得到單鏈表的長度 public int Size() { int count = 0; ListNode cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } //找到index位置的前一位置的地址 public ListNode findIndex(int index) { ListNode cur = head.next; while (index - 1 != 0) { cur = cur.next; index--; } return cur; } //任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標(biāo) public void addIndex(int index, int data) { if (index < 0 || index > Size()) { return; } if (index == 0) { //相當(dāng)于頭插法 addFirst(data); return; } if (index == Size()) { //相當(dāng)于尾插法 addLast(data); return; } ListNode cur = findIndex(index);//找到index位置前一位置的地址 ListNode node = new ListNode(data);//初始化node node.next = cur.next; cur.next = node; } //找到key的前驅(qū)(前一節(jié)點) public ListNode searchPrev(int key) { ListNode cur = this.head; while (cur.next != null) { if (cur.next.val == key) { return cur; } cur = cur.next; } return null; } //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點 public void remove(int key) { if (this.head == null) { return; } if (this.head.val == key) { this.head = this.head.next; return; } ListNode cur = searchPrev(key); if (cur == null) { return; //沒有要刪除的節(jié)點 } ListNode del = cur.next;//定義要刪除的節(jié)點 cur.next = del.next; } //刪除所有值為key的節(jié)點 public ListNode removeAllKey(int key) { if (this.head = null) { return null; } 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; } return this.head; } //清空鏈表 public void clear() { while (this.head != null) { ListNode curNext = this.head.next; this.head.next = null; this.head = curNext; } } }
總結(jié)
到此這篇關(guān)于Java鏈表超詳細(xì)講解的文章就介紹到這了,更多相關(guān)Java鏈表詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Spring中的Schedule動態(tài)添加修改定時任務(wù)詳解
這篇文章主要介紹了Spring中的Schedule動態(tài)添加修改定時任務(wù)詳解,可能有人會問,為啥不用Quartz,Quartz自然是非常方便強(qiáng)大的,但不是本篇要講的內(nèi)容,本篇就偏要使用SpringSchedule來實現(xiàn)動態(tài)的cron表達(dá)式任務(wù),需要的朋友可以參考下2023-11-11MySQL中關(guān)鍵字UNION和UNION ALL的區(qū)別
本文主要介紹了MySQL中關(guān)鍵字UNION和UNION ALL的區(qū)別,深入探討UNION和UNION ALL的定義、用法、主要區(qū)別,具有一定的參考價值,感興趣的可以了解一下2024-06-06java中對象的比較equal、Comparble、Comparator的區(qū)別
本文主要介紹了java中對象的比較equal、Comparble、Comparator的區(qū)別,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-10-10分布式開發(fā)醫(yī)療掛號系統(tǒng)數(shù)據(jù)字典模塊前后端實現(xiàn)
這篇文章主要為大家介紹了分布式開發(fā)醫(yī)療掛號系統(tǒng)數(shù)據(jù)字典模塊前后端實現(xiàn),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-04-04SpringBoot如何打印mybatis的執(zhí)行sql問題
這篇文章主要介紹了SpringBoot如何打印mybatis的執(zhí)行sql問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2023-03-03