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