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)或者訪問特定編號的節(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)
對于鏈表的結(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域(指針域)組成，對于next域，其是引用類型，存放下一個(gè)節(jié)點(diǎn)的地址，故
用public ListNode next來創(chuàng)建next。
同時(shí)設(shè)置構(gòu)造函數(shù)，方便對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)建鏈表
方法一：枚舉法（略簡單，略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的初始化。
注意：不用對最后一個(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)，然后就是對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)，然后就是對原來最后一個(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)識了鏈表的結(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一直存在且有意義，我們在display()函數(shù)中定義一個(gè)cur：ListNode cur = this.head;來替代head。
對于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)對于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.得到單鏈表的長度：public int Size()
定義計(jì)數(shù)器count = 0，通過head的移動(dò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號下標(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號位置，
經(jīng)過分析，需要將head先移至2號位置（注意：用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()){ //對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)
對于刪除第一次出現(xiàn)的key值的節(jié)點(diǎn)，若不是頭節(jié)點(diǎn)，我們只需將key值對應(yīng)的節(jié)點(diǎn)的前一節(jié)點(diǎn)的next的域改為key值對應(yīng)的節(jié)點(diǎn)的next域即可。
對于頭節(jié)點(diǎn)，直接head = head.next即可。
對于key值對應(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é)點(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;
}
//得到單鏈表的長度
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號下標(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Lombok集成springboot遇到的坑，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12
Java Files和Paths是Java 7中引入的新API，用于處理文件和目錄，F(xiàn)iles類提供了許多有用的靜態(tài)方法來操作文件和目錄，而Path類則表示文件系統(tǒng)中的路徑，這篇文章主要介紹了Java Files和Paths的使用詳解,需要的朋友可以參考下2023-03-03
RocketMQ源碼分析之Broker過期消息清理機(jī)制
這篇文章主要為大家介紹了RocketMQ源碼分析之Broker過期消息清理機(jī)制示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
Java中BigDecimal,DateFormatter?和迭代器的"陷阱"
這篇文章主要介紹了Java中BigDecimal，DateFormatter?和迭代器的"陷阱"，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，感興趣的小伙伴可以參考一下2022-06-06
使用maven一步一步構(gòu)建spring mvc項(xiàng)目（圖文詳解）
這篇文章主要介紹了詳解使用maven一步一步構(gòu)建spring mvc項(xiàng)目，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-09-09
這篇文章主要給大家介紹了關(guān)于JVM指令使用的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-01-01
SpringBoot通過RedisTemplate執(zhí)行Lua腳本的方法步驟
這篇文章主要介紹了SpringBoot通過RedisTemplate執(zhí)行Lua腳本的方法步驟,本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-02-02
Java實(shí)現(xiàn)異步執(zhí)行的8種方式總結(jié)
這篇文章主要給大家介紹了關(guān)于Java實(shí)現(xiàn)異步執(zhí)行的8種方式,異步編程不會(huì)阻塞程序的執(zhí)行,它將耗時(shí)的操作提交給后臺(tái)線程或其他執(zhí)行環(huán)境,并立即返回,使得程序可以繼續(xù)執(zhí)行其他任務(wù),需要的朋友可以參考下2023-09-09
本篇文章給大家分享了關(guān)于Java中unsafe操作的相關(guān)知識點(diǎn)以及相關(guān)的實(shí)例代碼，有需要的朋友可以學(xué)習(xí)參考下。2018-03-03
springboot自動(dòng)裝配TypeNotPresentExceptionProxy異常排查解決
這篇文章主要為大家介紹了springboot自動(dòng)裝配TypeNotPresentExceptionProxy異常排查解決,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-09-09