Java數(shù)據(jù)結(jié)構(gòu)之鏈表的增刪查改詳解
一、鏈表的概念和結(jié)構(gòu)
1.1 鏈表的概念
簡(jiǎn)單來(lái)說(shuō)鏈表是物理上不一定連續(xù)，但是邏輯上一定連續(xù)的一種數(shù)據(jù)結(jié)構(gòu)
1.2 鏈表的分類(lèi)
實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu). 單向和雙向，帶頭和不帶頭，循環(huán)和非循環(huán)。排列組合和會(huì)有8種。
但我這只是實(shí)現(xiàn)兩種比較難的鏈表，理解之后其它6種就比較簡(jiǎn)單了
1.單向不帶頭非循環(huán)鏈表
2.雙向不帶頭非循環(huán)鏈表
二、單向不帶頭非循環(huán)鏈表
2.1 創(chuàng)建節(jié)點(diǎn)類(lèi)型
我們創(chuàng)建了一個(gè) ListNode 類(lèi)為節(jié)點(diǎn)類(lèi)型，里面有兩個(gè)成員變量，val用來(lái)存儲(chǔ)數(shù)值，next來(lái)存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址。
還有一個(gè)帶一個(gè)參數(shù)的構(gòu)造方法在實(shí)例化對(duì)象的同時(shí)給val賦值，因?yàn)槲覀儾恢老乱粋€(gè)節(jié)點(diǎn)的地址所以next是默認(rèn)值一個(gè)null
class ListNode {
public int val;//數(shù)值
public ListNode next;//下一個(gè)節(jié)點(diǎn)的地址
public ListNode(int val) {
this.val = val;
}
}
我們?cè)?MyLinkedList 里創(chuàng)建一個(gè)head變量來(lái)標(biāo)識(shí)鏈表的頭部，接著就是實(shí)現(xiàn)單鏈表的增刪查改了
2.2 頭插法
這個(gè)頭插法并不要考慮第一次插入，每次插入只需要把插入的節(jié)點(diǎn)node 的next值改成頭節(jié)點(diǎn)，再把頭節(jié)點(diǎn)指向node
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
}
2.3 尾插法
尾插法首先要考慮是不是第一次插入，如果是的話(huà)直接把head指向node就好了，如果不是第一次插入，則需要定義一個(gè)cur來(lái)找尾巴節(jié)點(diǎn)，把尾巴節(jié)點(diǎn)的next值改成node就好了。因?yàn)槿绻挥梦舶凸?jié)點(diǎn)的話(huà)，head就無(wú)法標(biāo)識(shí)到頭部了
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
ListNode cur = this.head;
//第一次插入
if(this.head == null) {
this.head = node;
}else{
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
2.4 獲取鏈表長(zhǎng)度
定義一個(gè)計(jì)數(shù)器count，當(dāng)cur遍歷完鏈表的時(shí)候直接返回count就好
//得到單鏈表的長(zhǎng)度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
cur = cur.next;
count++;
}
return count;
}
2.5 任意位置插入
我們假設(shè)鏈表的頭是從0位置開(kāi)始的，任意位置插入需要考慮幾點(diǎn)
1.位置的合法性，如果位置小于0，或者大于鏈表長(zhǎng)度則位置不合法
2.如果要插入的是0位置直接使用頭插法
3.如果插入的位置等于鏈表長(zhǎng)度則使用尾插法，因?yàn)槲覀冞@鏈表是從0開(kāi)始的
最關(guān)鍵的就是從中間任意位置插入 要從中間位置插入，就需要找到要插入位置的前一個(gè)節(jié)點(diǎn)的位置。再插入到它們中間。
/**
* 讓 cur 向后走 index - 1 步
* @param index
* @return
*/
public ListNode findIndexSubOne(int index) {
int count = 0;
ListNode cur = this.head;
while (count != index-1) {
cur = cur.next;
count++;
}
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()) {
System.out.println("index位置不合法");
return;
}
//頭插法
if(index == 0) {
this.addFirst(data);
return;
}
//尾插法
if(index == size()) {
this.addLast(data);
return;
}
//找前驅(qū),cur指向的是 index 的前一個(gè)節(jié)點(diǎn)
ListNode cur = findIndexSubOne(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
2.6 查找關(guān)鍵字
當(dāng)我們要查找鏈表中是否有某一個(gè)關(guān)鍵字時(shí)，只需要定義一個(gè)cur從頭開(kāi)始遍歷即可
//查找是否包含關(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;
}
2.7 刪除第一次出現(xiàn)值為key的節(jié)點(diǎn)
這個(gè)思路其實(shí)也很簡(jiǎn)單，考慮到兩種情況即可
1.如果要?jiǎng)h除的是頭節(jié)點(diǎn)只需要把頭節(jié)點(diǎn)指向它的向一個(gè)節(jié)點(diǎn)即可
2.還有一種則是不存在key的情況，所以這里寫(xiě)了一個(gè)方法來(lái)判讀key是否存在，如果存在則返回key的前一個(gè)節(jié)點(diǎn)的位置
3.存在則把要?jiǎng)h除的節(jié)點(diǎn)的前驅(qū)的next改成它的next即可
/**
* 找要?jiǎng)h除 key 的前一個(gè)節(jié)點(diǎn)
* @return
*/
public ListNode searchPrev(int key) {
ListNode prev = this.head;
while (prev.next != null) {
if (prev.next.val == key) {
return prev;
}
prev = prev.next;
}
return null;
}
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
public void remove(int key) {
if(this.head.val == key) {
this.head = this.head.next;
return;
}
//找 key 的前驅(qū)節(jié)點(diǎn)
ListNode prev = searchPrev(key);
if(prev == null) {
System.out.println("沒(méi)有key這個(gè)關(guān)鍵字");
return;
}
//刪除
ListNode delete = prev.next;
prev.next = delete.next;
}
2.8 刪除所有值為key的節(jié)點(diǎn)
假設(shè)要?jiǎng)h除的是3，思路：
定義兩個(gè)節(jié)點(diǎn)點(diǎn)類(lèi)型的變量，prev指向head，cur指向head的下一個(gè)節(jié)點(diǎn)。
如果判斷cur的val值是要?jiǎng)h除的值，如果是則直接跳過(guò)這個(gè)節(jié)點(diǎn) 如果不是則讓prev和cur往后走，直到整個(gè)鏈表遍歷完。
到最后會(huì)發(fā)現(xiàn)頭節(jié)點(diǎn)并沒(méi)有遍歷到，循環(huán)結(jié)束后則需要判讀頭節(jié)點(diǎn)是不是要?jiǎng)h除的節(jié)點(diǎn)
記住一定要邊畫(huà)圖邊寫(xiě)代碼！
//刪除所有值為key的節(jié)點(diǎn)
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;
}
}
//判斷第一個(gè)節(jié)點(diǎn)是否是要?jiǎng)h除的節(jié)點(diǎn)
if(this.head.val == key) {
this.head = this.head.next;
}
}
2.9 遍歷打印鏈表
定義一個(gè)cur直接遍歷打印就好
//打印鏈表
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
置空鏈表
置空鏈表只需要一個(gè)個(gè)置空即可，并不建議直接把頭節(jié)點(diǎn)置空這種暴力做法
//置空鏈表
public void clear() {
ListNode cur = this.head;
//一個(gè)個(gè)制空
while (cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur = curNext;
}
this.head = null;
}
三、雙向不帶頭非循環(huán)鏈表
雙向鏈表和單向鏈表的最大的區(qū)別就是多了一個(gè)前驅(qū)節(jié)點(diǎn)prev，同樣來(lái)實(shí)現(xiàn)雙向鏈表的增刪查改
public class TestLinkedList {
public ListNode head;
public ListNode last;
}
3.1 創(chuàng)建節(jié)點(diǎn)類(lèi)型
同樣先定義節(jié)點(diǎn)類(lèi)型，比單向鏈表多了一個(gè)前驅(qū)節(jié)點(diǎn)而已。
class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode (int val) {
this.val = val;
}
}
雙向鏈表還定義了一個(gè)last來(lái)標(biāo)識(shí)尾巴節(jié)點(diǎn)，而單鏈表只是標(biāo)識(shí)了頭節(jié)點(diǎn)。
3.2 頭插法
因?yàn)檫@是雙向鏈表，第一次插入要讓head和last同時(shí)指向第一個(gè)節(jié)點(diǎn)。
如果不是第一次插入，則需要
1.把head的前驅(qū)節(jié)點(diǎn)改成node,
2.再把node的next改成head，
3.然后把頭節(jié)點(diǎn)head再指向新的頭節(jié)點(diǎn)node。
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
//第一次插入
if(this.head == null) {
this.head = node;
this.last = node;
}else {
head.prev = node;
node.next = this.head;
this.head = node;
}
}
3.3 尾插法
雙向鏈表有一個(gè)last來(lái)標(biāo)識(shí)尾巴節(jié)點(diǎn)，所以在尾插的時(shí)候不用再找尾巴節(jié)點(diǎn)了。和頭插法類(lèi)似
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
//第一次插入
if(this.head == null) {
this.head = node;
this.last = node;
}else {
this.last.next = node;
node.prev = this.last;
this.last = node;
}
}
3.4 獲取鏈表長(zhǎng)度
這個(gè)和單鏈表一樣，直接定義個(gè)cur遍歷
//得到鏈表的長(zhǎng)度
public int size() {
ListNode cur = this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
3.5 任意位置插入
任意位置插入也和單鏈表類(lèi)似有三種情況。判斷合法性和頭插尾插就不多了主要還是在中間的隨機(jī)插入，一定要注意修改的順序！
要修改的地方一共有四個(gè)，一定要畫(huà)圖理解！
//找要插入的節(jié)點(diǎn)的位置
public ListNode searchIndex(int index) {
ListNode cur = this.head;
while (index != 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) {
//判斷index位置的合法性
if(index < 0 || index > this.size()) {
System.out.println("index的位置不合法");
return;
}
//頭插法
if(index == 0) {
this.addFirst(data);
return;
}
//尾插法
if(index == this.size()) {
this.addLast(data);
return;
}
//中間插入
ListNode node = new ListNode(data);
ListNode cur = searchIndex(index);
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
3.6 查找關(guān)鍵字
這里和單鏈表一樣，直接定義個(gè)cur遍歷看看鏈表里有沒(méi)有這個(gè)值即可
//查找是否包含關(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;
}
3.7 刪除第一次出現(xiàn)的關(guān)鍵字key的節(jié)點(diǎn)
思路：遍歷鏈表找第一次出現(xiàn)的節(jié)點(diǎn)，刪完return。一共分三種情況
1.頭節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)
2.尾巴節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)
3.中間的節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
public void remove(int key) {
ListNode cur = this.head;
while (cur != null) {
if(cur.val == key) {
//要?jiǎng)h除的是頭節(jié)點(diǎn)
if(this.head == cur) {
this.head = this.head.next;
this.head.prev = null;
}else {
//尾巴節(jié)點(diǎn)和中間的節(jié)點(diǎn)兩種情況
cur.prev.next = cur.next;
if(this.last == cur) {
//刪除尾巴節(jié)點(diǎn)
cur = cur.prev;
}else {
cur.next.prev = cur.prev;
}
}
//已經(jīng)刪完了
return;
}else {
cur = cur.next;
}
}
}
3.8 刪除所有值為key的節(jié)點(diǎn)
思路和刪除一個(gè)key類(lèi)似，但需要注意兩個(gè)點(diǎn)。
1.刪完就不用return了，而是繼續(xù)往后走，因?yàn)檫@里是刪除所有為key需要把列表遍歷完
2.還有就是要考慮當(dāng)整個(gè)鏈表都是要?jiǎng)h除的情況，if判斷一下不然會(huì)發(fā)生空指針異常
//刪除所有值為key的節(jié)點(diǎn)
public void removeAllKey(int key) {
ListNode cur = this.head;
while (cur != null) {
if(cur.val == key) {
//要?jiǎng)h除的是頭節(jié)點(diǎn)
if(this.head == cur) {
this.head = this.head.next;
//假設(shè)全部是要?jiǎng)h除的節(jié)點(diǎn)
if(this.head != null) {
this.head.prev = null;
}else {
//防止最后一個(gè)節(jié)點(diǎn)不能被回收
this.last = null;
}
}else {
//尾巴節(jié)點(diǎn)和中間的節(jié)點(diǎn)兩種情況
cur.prev.next = cur.next;
if(this.last == cur) {
//刪除尾巴節(jié)點(diǎn)
cur = cur.prev;
}else {
cur.next.prev = cur.prev;
}
}
//走一步
cur = cur.next;
}else {
cur = cur.next;
}
}
}
3.9 遍歷打印鏈表
//打印鏈表
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
置空鏈表
遍歷鏈表一個(gè)一個(gè)置為null，再把頭節(jié)點(diǎn)和尾巴節(jié)點(diǎn)值為null。防止內(nèi)存泄漏
//置空鏈表
public void clear() {
ListNode cur = this.head;
//一個(gè)一個(gè)置空
while (cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
this.head = null;
this.last = null;
}
四、總結(jié)
1.這里實(shí)現(xiàn)了兩種較難的鏈表：?jiǎn)蜗虿粠ь^非循環(huán)和雙向不帶頭非循環(huán)
2.鏈表物理上不一定連續(xù)，但邏輯上一定連續(xù)。
3.增：鏈表插入一個(gè)元素只需要修改指向，所以時(shí)間復(fù)雜度為O(1)
4:刪：鏈表刪除元素，同樣只需修改指向，時(shí)間復(fù)雜度為O(1)
5.查：鏈表如果需要查找一個(gè)元素需要遍歷鏈表，所以時(shí)間復(fù)雜度為O(n)
6.改：鏈表要去找到要修改的元素，所以時(shí)間復(fù)雜度為O(n).
什么時(shí)候用鏈表？
如果是插入和刪除比較頻繁的時(shí)候，使用鏈表。注意：是不涉及到移動(dòng)數(shù)據(jù)的情況！
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之鏈表的增刪查改詳解的文章就介紹到這了,更多相關(guān)Java鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java和Ceylon對(duì)象的構(gòu)造和驗(yàn)證
這篇文章主要為大家詳細(xì)介紹了Java和Ceylon對(duì)象的構(gòu)造和驗(yàn)證,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-11-11
這篇文章主要介紹了SpringBoot整合Shiro一些方式，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-07-07
這篇文章主要介紹了Java中的ArrayList底層源碼分析,通過(guò)下標(biāo)讀取元素的速度很快,這是因?yàn)锳rrayList底層基于數(shù)組實(shí)現(xiàn),可以根據(jù)下標(biāo)快速的找到內(nèi)存地址,接著讀取內(nèi)存地址中存放的數(shù)據(jù),需要的朋友可以參考下2023-12-12
這篇文章主要為大家詳細(xì)介紹了java的依賴(lài)倒置原則，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02
基于JavaMail的Java實(shí)現(xiàn)復(fù)雜郵件發(fā)送功能
這篇文章主要為大家詳細(xì)介紹了基于JavaMail的Java實(shí)現(xiàn)復(fù)雜郵件發(fā)送功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-09-09
SpringMVC?RESTFul實(shí)體類(lèi)創(chuàng)建及環(huán)境搭建
這篇文章主要為大家介紹了SpringMVC?RESTFul實(shí)體類(lèi)創(chuàng)建及環(huán)境搭建詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
SpringBoot項(xiàng)目里集成Hibernate的示例
在Spring Boot項(xiàng)目中，集成Hibernate可以幫助我們更輕松地進(jìn)行數(shù)據(jù)庫(kù)操作，本文將介紹如何在Spring Boot項(xiàng)目中集成Hibernate，并提供相應(yīng)的示例，感興趣的朋友跟隨小編一起看看吧2023-04-04
Java實(shí)現(xiàn)的Base64加密算法示例
這篇文章主要介紹了Java實(shí)現(xiàn)的Base64加密算法,結(jié)合實(shí)例形式分析了Java實(shí)現(xiàn)的base64編碼轉(zhuǎn)換相關(guān)使用方法及操作注意事項(xiàng),需要的朋友可以參考下2018-04-04
Java對(duì)象不使用時(shí)賦值null的意義詳解
這篇文章主要介紹了java對(duì)象不再使用時(shí)賦值null的意義,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03
詳解mybatis.generator配上最新的mysql 8.0.11的一些坑
這篇文章主要介紹了詳解mybatis.generator配上最新的mysql 8.0.11的一些坑，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-10-10