您好,登錄后才能下訂單哦!
本篇文章為大家展示了使用Java怎么對(duì)鏈表進(jìn)行增刪查改操作,內(nèi)容簡(jiǎn)明扼要并且容易理解,絕對(duì)能使你眼前一亮,通過這篇文章的詳細(xì)介紹希望你能有所收獲。
簡(jiǎn)單來說鏈表是物理上不一定連續(xù),但是邏輯上一定連續(xù)的一種數(shù)據(jù)結(jié)構(gòu)
實(shí)際中鏈表的結(jié)構(gòu)非常多樣,以下情況組合起來就有8種鏈表結(jié)構(gòu). 單向和雙向,帶頭和不帶頭,循環(huán)和非循環(huán)。排列組合和會(huì)有8種。
但我這只是實(shí)現(xiàn)兩種比較難的鏈表,理解之后其它6種就比較簡(jiǎn)單了
1.單向不帶頭非循環(huán)鏈表
2.雙向不帶頭非循環(huán)鏈表
我們創(chuàng)建了一個(gè) ListNode 類為節(jié)點(diǎn)類型,里面有兩個(gè)成員變量,val用來存儲(chǔ)數(shù)值,next來存儲(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變量來標(biāo)識(shí)鏈表的頭部,接著就是實(shí)現(xiàn)單鏈表的增刪查改了
這個(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; }
尾插法首先要考慮是不是第一次插入,如果是的話直接把head指向node就好了,如果不是第一次插入,則需要定義一個(gè)cur來找尾巴節(jié)點(diǎn),把尾巴節(jié)點(diǎn)的next值改成node就好了。因?yàn)槿绻挥梦舶凸?jié)點(diǎn)的話,head就無法標(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; } }
定義一個(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; }
我們假設(shè)鏈表的頭是從0位置開始的,任意位置插入需要考慮幾點(diǎn)
1.位置的合法性,如果位置小于0,或者大于鏈表長(zhǎng)度則位置不合法
2.如果要插入的是0位置直接使用頭插法
3.如果插入的位置等于鏈表長(zhǎng)度則使用尾插法,因?yàn)槲覀冞@鏈表是從0開始的
最關(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; }
當(dāng)我們要查找鏈表中是否有某一個(gè)關(guān)鍵字時(shí),只需要定義一個(gè)cur從頭開始遍歷即可
//查找是否包含關(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; }
這個(gè)思路其實(shí)也很簡(jiǎn)單,考慮到兩種情況即可
1.如果要?jiǎng)h除的是頭節(jié)點(diǎn)只需要把頭節(jié)點(diǎn)指向它的向一個(gè)節(jié)點(diǎn)即可
2.還有一種則是不存在key的情況,所以這里寫了一個(gè)方法來判讀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("沒有key這個(gè)關(guān)鍵字"); return; } //刪除 ListNode delete = prev.next; prev.next = delete.next; }
假設(shè)要?jiǎng)h除的是3,思路:
定義兩個(gè)節(jié)點(diǎn)點(diǎn)類型的變量,prev指向head,cur指向head的下一個(gè)節(jié)點(diǎn)。
如果判斷cur的val值是要?jiǎng)h除的值,如果是則直接跳過這個(gè)節(jié)點(diǎn) 如果不是則讓prev和cur往后走,直到整個(gè)鏈表遍歷完。
到最后會(huì)發(fā)現(xiàn)頭節(jié)點(diǎn)并沒有遍歷到,循環(huán)結(jié)束后則需要判讀頭節(jié)點(diǎn)是不是要?jiǎng)h除的節(jié)點(diǎn)
記住一定要邊畫圖邊寫代碼!
//刪除所有值為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; } }
定義一個(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; }
雙向鏈表和單向鏈表的最大的區(qū)別就是多了一個(gè)前驅(qū)節(jié)點(diǎn)prev,同樣來實(shí)現(xiàn)雙向鏈表的增刪查改
public class TestLinkedList { public ListNode head; public ListNode last; }
同樣先定義節(jié)點(diǎn)類型,比單向鏈表多了一個(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來標(biāo)識(shí)尾巴節(jié)點(diǎn),而單鏈表只是標(biāo)識(shí)了頭節(jié)點(diǎn)。
因?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; } }
雙向鏈表有一個(gè)last來標(biāo)識(shí)尾巴節(jié)點(diǎn),所以在尾插的時(shí)候不用再找尾巴節(jié)點(diǎn)了。和頭插法類似
//尾插法 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; } }
這個(gè)和單鏈表一樣,直接定義個(gè)cur遍歷
//得到鏈表的長(zhǎng)度 public int size() { ListNode cur = this.head; int count = 0; while (cur != null) { count++; cur = cur.next; } return count; }
任意位置插入也和單鏈表類似有三種情況。判斷合法性和頭插尾插就不多了主要還是在中間的隨機(jī)插入,一定要注意修改的順序!
要修改的地方一共有四個(gè),一定要畫圖理解!
//找要插入的節(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; }
這里和單鏈表一樣,直接定義個(gè)cur遍歷看看鏈表里有沒有這個(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; }
思路:遍歷鏈表找第一次出現(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; } } }
思路和刪除一個(gè)key類似,但需要注意兩個(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; } } }
//打印鏈表 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; }
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).
1.SpringMVC,Spring Web MVC是一種基于Java的實(shí)現(xiàn)了Web MVC設(shè)計(jì)模式的請(qǐng)求驅(qū)動(dòng)類型的輕量級(jí)Web框架。2.Shiro,Apache Shiro是Java的一個(gè)安全框架。3.Mybatis,MyBatis 是支持普通 SQL查詢,存儲(chǔ)過程和高級(jí)映射的優(yōu)秀持久層框架。4.Dubbo,Dubbo是一個(gè)分布式服務(wù)框架。5.Maven,Maven是個(gè)項(xiàng)目管理和構(gòu)建自動(dòng)化工具。6.RabbitMQ,RabbitMQ是用Erlang實(shí)現(xiàn)的一個(gè)高并發(fā)高可靠AMQP消息隊(duì)列服務(wù)器。7.Ehcache,EhCache 是一個(gè)純Java的進(jìn)程內(nèi)緩存框架。
上述內(nèi)容就是使用Java怎么對(duì)鏈表進(jìn)行增刪查改操作,你們學(xué)到知識(shí)或技能了嗎?如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。