您好,登錄后才能下訂單哦!
這篇“java實(shí)現(xiàn)單鏈表linked list的方法”除了程序員外大部分人都不太理解,今天小編為了讓大家更加理解“java實(shí)現(xiàn)單鏈表linked list的方法”,給大家總結(jié)了以下內(nèi)容,具有一定借鑒價值,內(nèi)容詳細(xì)步驟清晰,細(xì)節(jié)處理妥當(dāng),希望大家通過這篇文章有所收獲,下面讓我們一起來看看具體內(nèi)容吧。
Java的特點(diǎn)有哪些 1.Java語言作為靜態(tài)面向?qū)ο缶幊陶Z言的代表,實(shí)現(xiàn)了面向?qū)ο罄碚?,允許程序員以優(yōu)雅的思維方式進(jìn)行復(fù)雜的編程。 2.Java具有簡單性、面向?qū)ο蟆⒎植际?、安全性、平臺獨(dú)立與可移植性、動態(tài)性等特點(diǎn)。 3.使用Java可以編寫桌面應(yīng)用程序、Web應(yīng)用程序、分布式系統(tǒng)和嵌入式系統(tǒng)應(yīng)用程序等。
一、單鏈表介紹
單鏈表是一個有序列表
,以節(jié)點(diǎn)
的方式鏈?zhǔn)酱鎯π畔?/code>,但節(jié)點(diǎn)
不一定連續(xù)
,每一個節(jié)點(diǎn)包括data域和next域。
data域
:用來存放數(shù)據(jù)。
next域
:指向下一個節(jié)點(diǎn)。
鏈表分為帶頭節(jié)點(diǎn)的鏈表
和不帶頭節(jié)點(diǎn)的鏈表
。
單鏈表(帶頭節(jié)點(diǎn))
單鏈表(不帶頭節(jié)點(diǎn))
二、單鏈表的實(shí)現(xiàn)
需求:使用帶head頭的
單向鏈表
實(shí)現(xiàn)–水滸英雄排行榜管理。
1)完成對英雄的增刪改查
2)第一種方法在添加英雄時,直接添加到鏈表的尾部
。
3)第二種方式在添加英雄時,根據(jù)排名將英雄插入到指定位置
(如果已有這個排名,則添加失敗,并給出提示)
1.單鏈表的創(chuàng)建(添加)
1.1尾添加
尾添加的思路
①先創(chuàng)建一個head頭節(jié)點(diǎn),作用就是表示單鏈表的頭。
②然后每添加一個節(jié)點(diǎn),就直接加入到鏈表的最后。
尾添加即:不考慮編號順序,找到當(dāng)前鏈表的最后節(jié)點(diǎn),將最后這個節(jié)點(diǎn)的next指向新的節(jié)點(diǎn)。
代碼實(shí)現(xiàn)
// 添加方式1:尾添加 public void add(HeroNode heroNode) { // 因?yàn)閔ead頭不能動,因此需要一個輔助變量(指針)temp HeroNode temp = head; while (true) { // 如果遍歷到鏈表的最后 if (temp.next == null) { break; } // temp指針后移 temp = temp.next; } // 當(dāng)退出循環(huán)時,temp指向鏈表的最后 temp.next = heroNode; }
1.2按排名添加
按排名添加的思路
①先通過輔助變量(temp指針)找到新添加的節(jié)點(diǎn)的位置。
②新節(jié)點(diǎn).next=temp.next;
③temp.next=新的節(jié)點(diǎn);
代碼實(shí)現(xiàn)
// 添加方式2:根據(jù)排名添加 public void addByOrder(HeroNode heroNode) { HeroNode temp = head;// 借助輔助指針 boolean flag = false;// 添加的編號是否存在 while (true) { if (temp.next == null) {// 遍歷到結(jié)尾 break; } if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) {// 該編號已存在 flag = true; break; } temp = temp.next;// 后移,遍歷當(dāng)前鏈表 } if (flag) { // 不能添加 System.out.printf("準(zhǔn)備插入的英雄的編號%d已經(jīng)存在,不能加入\n", heroNode.no); } else { // 插入到temp的后面 heroNode.next = temp.next; temp.next = heroNode; } }
2.單鏈表節(jié)點(diǎn)的修改
修改的思路
①通過遍歷先找到該節(jié)點(diǎn)。
②temp.name =newHeroNode.name;
,temp.nickname=newHeroNode.nickname;
代碼實(shí)現(xiàn)
// 修改節(jié)點(diǎn)信息,根據(jù)節(jié)點(diǎn)的no屬性修改其他信息 public void update(HeroNode newHeroNode) { // 空鏈表無法修改節(jié)點(diǎn)信息 if (head.next == null) { System.out.println("鏈表為空~"); return; } // 根據(jù)no排名找到需要修改的節(jié)點(diǎn) HeroNode temp = head.next; boolean flag = false;// flag表示是否找到需要修改的節(jié)點(diǎn) while (true) { if (temp == null) { // 遍歷到結(jié)尾 break; } if (temp.no == newHeroNode.no) { // 找到 flag = true; break; } temp = temp.next;// 后移 } if (flag) { temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; } else { System.out.printf("沒有找到編號為%d的節(jié)點(diǎn),不能修改\n", newHeroNode.no); } }
3.單鏈表節(jié)點(diǎn)的刪除
刪除的思路
①找到需要刪除的節(jié)點(diǎn)的前一個節(jié)點(diǎn)。
②temp.next=temp.next.next
③被刪除的節(jié)點(diǎn),將不會有其它引用指向,會被垃圾回收機(jī)制回收。
代碼實(shí)現(xiàn)
public void delete(int no) { HeroNode temp = head; boolean flag = false;// 是否找到待刪除節(jié)點(diǎn) while (true) { if (temp.next == null) { // 遍歷到結(jié)尾 break; } if (temp.next.no == no) { // 找到了待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn) flag = true; break; } temp = temp.next;// 后移 } if (flag) { // 可以刪除 temp.next = temp.next.next; } else { System.out.printf("要刪除的%d節(jié)點(diǎn)不存在\n", no); } }
4.單鏈表的完整實(shí)現(xiàn)
package com.gql.linkedlist;/** * 單鏈表 * * @guoqianliang * */public class SingleLinkedListDemo { public static void main(String[] args) { // 創(chuàng)建節(jié)點(diǎn) HeroNode hero1 = new HeroNode(1, "宋江", "及時雨"); HeroNode hero2 = new HeroNode(2, "盧俊義", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吳用", "智多星"); HeroNode hero4 = new HeroNode(4, "林沖", "豹子頭"); // 創(chuàng)建單向鏈表 SingleLinkedList singleLinkedList = new SingleLinkedList(); // 加入 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero2); singleLinkedList.list(); // 測試修改節(jié)點(diǎn) HeroNode newHeroNode = new HeroNode(2, "小盧", "玉麒麟~"); singleLinkedList.update(newHeroNode); System.out.println("修改后的鏈表情況:"); singleLinkedList.list(); // 刪除一個節(jié)點(diǎn) singleLinkedList.delete(1); singleLinkedList.delete(2); singleLinkedList.delete(3); singleLinkedList.delete(4); System.out.println("刪除后的鏈表情況:"); singleLinkedList.list(); }}//定義SingleLinkedList,管理英雄class SingleLinkedList { // 初始化頭結(jié)點(diǎn),不存放具體數(shù)據(jù) private HeroNode head = new HeroNode(0, "", ""); // 添加方式1:尾添加 // 思路: // 1.找到當(dāng)前鏈表的最后節(jié)點(diǎn) // 2.將這個最后的節(jié)點(diǎn)的next指向新的節(jié)點(diǎn) public void add(HeroNode heroNode) { // 因?yàn)閔ead頭不能動,因此需要一個輔助變量(指針)temp HeroNode temp = head; while (true) { // 如果遍歷到鏈表的最后 if (temp.next == null) { break; } // temp指針后移 temp = temp.next; } // 當(dāng)退出循環(huán)時,temp指向鏈表的最后 temp.next = heroNode; } // 添加方式2:根據(jù)排名添加 public void addByOrder(HeroNode heroNode) { HeroNode temp = head;// 借助輔助指針 boolean flag = false;// 添加的編號是否存在 while (true) { if (temp.next == null) {// 遍歷到結(jié)尾 break; } if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) {// 該編號已存在 flag = true; break; } temp = temp.next;// 后移,遍歷當(dāng)前鏈表 } if (flag) { // 不能添加 System.out.printf("準(zhǔn)備插入的英雄的編號%d已經(jīng)存在,不能加入\n", heroNode.no); } else { // 插入到temp的后面 heroNode.next = temp.next; temp.next = heroNode; } } // 修改節(jié)點(diǎn)信息,根據(jù)節(jié)點(diǎn)的no屬性修改其他信息 public void update(HeroNode newHeroNode) { // 空鏈表無法修改節(jié)點(diǎn)信息 if (head.next == null) { System.out.println("鏈表為空~"); return; } // 根據(jù)no排名找到需要修改的節(jié)點(diǎn) HeroNode temp = head.next; boolean flag = false;// flag表示是否找到需要修改的節(jié)點(diǎn) while (true) { if (temp == null) { // 遍歷到結(jié)尾 break; } if (temp.no == newHeroNode.no) { // 找到 flag = true; break; } temp = temp.next;// 后移 } if (flag) { temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; } else { System.out.printf("沒有找到編號為%d的節(jié)點(diǎn),不能修改\n", newHeroNode.no); } } // 刪除節(jié)點(diǎn) // 思路: // 1.找到需要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn) // 2.temp.next=temp.next.next // 3.被刪除的節(jié)點(diǎn)將會被垃圾回收機(jī)制回收 public void delete(int no) { HeroNode temp = head; boolean flag = false;// 是否找到待刪除節(jié)點(diǎn) while (true) { if (temp.next == null) { // 遍歷到結(jié)尾 break; } if (temp.next.no == no) { // 找到了待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn) flag = true; break; } temp = temp.next;// 后移 } if (flag) { // 可以刪除 temp.next = temp.next.next; } else { System.out.printf("要刪除的%d節(jié)點(diǎn)不存在\n", no); } } // 顯示鏈表[遍歷] public void list() { // 空鏈表直接返回 if (head.next == null) { System.out.println("鏈表為空"); return; } // 仍然使用輔助變量(指針),進(jìn)行循環(huán) HeroNode temp = head.next; while (true) { if (temp == null) { break; } System.out.println(temp); // 將temp后移 temp = temp.next; } }}//定義HeroNode,每一個HeroNode就是一個節(jié)點(diǎn)class HeroNode { public int no;// 排名 public String name; public String nickname;// 昵稱 public HeroNode next;// 指向下一個節(jié)點(diǎn) // 構(gòu)造器 public HeroNode() { super(); } public HeroNode(int no, String name, String nickname) { super(); this.no = no; this.name = name; this.nickname = nickname; } // 重寫toString @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; }}
運(yùn)行結(jié)果
三、單鏈表面試題
上面四個面試題,答案都放在下面的代碼中
package com.gql.LinkedList;import java.util.Stack;/** * 模擬單鏈表 * * @author Hudie * @Email:guoqianliang@foxmail.com * @date 2020年7月16日下午6:47:42 */public class SingleLinkedListDemo { public static void main(String[] args) { // 創(chuàng)建節(jié)點(diǎn) HeroNode hero1 = new HeroNode(1, "宋江", "及時雨"); HeroNode hero2 = new HeroNode(2, "盧俊義", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吳用", "智多星"); HeroNode hero4 = new HeroNode(4, "林沖", "豹子頭"); // 創(chuàng)建單向鏈表 SingleLinkedList singleLinkedList = new SingleLinkedList(); // 加入 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero2); singleLinkedList.list(); // 測試修改節(jié)點(diǎn) HeroNode newHeroNode = new HeroNode(2, "小盧", "玉麒麟~"); singleLinkedList.update(newHeroNode); System.out.println("修改后的鏈表情況:"); singleLinkedList.list(); // 刪除一個節(jié)點(diǎn) singleLinkedList.delete(4); System.out.println("刪除后的鏈表情況:"); singleLinkedList.list(); //練習(xí)4:反向打印單鏈表 System.out.println("反向打印單鏈表:"); reversePrint(singleLinkedList.getHead()); //練習(xí)3:反轉(zhuǎn)單鏈表 reversalList(singleLinkedList.getHead()); System.out.println("反轉(zhuǎn)過后的單鏈表為:"); singleLinkedList.list(); // 練習(xí)1:獲取單鏈表節(jié)點(diǎn)個數(shù) System.out.println("單鏈表的有效個數(shù)為:"); System.out.println(getLength(singleLinkedList.getHead())); int index = 2; //練習(xí)2:獲取單鏈表倒數(shù)第index給節(jié)點(diǎn) System.out.println("倒數(shù)第"+ index +"個節(jié)點(diǎn)為:"); System.out.println(getLastKNode(singleLinkedList.getHead(),index)); } /** * @Description: 獲取單鏈表節(jié)點(diǎn)個數(shù) 思路: while循環(huán) + 遍歷指針 */ public static int getLength(HeroNode head) { if (head.next == null) { return 0; } int length = 0; // 輔助指針 HeroNode p = head.next; while (p != null) { length++; p = p.next; } return length; } /** * @Description: * 查找單鏈表中倒數(shù)第index個節(jié)點(diǎn) index:表示倒數(shù)第index給節(jié)點(diǎn) * 思路: * 1.首先獲取鏈表的長度length,可直接調(diào)用getLength * 2.然后從鏈表第一個開始遍歷,遍歷(length-index)個 * 3.找不到返回null */ public static HeroNode getLastKNode(HeroNode head, int index) { if (head.next == null) { return null; } int length = getLength(head); if (index <= 0 || index > length) { return null; } HeroNode p = head.next; for(int i = 0;i < length-index;i++){ p = p.next; } return p; } /** * @Description: * 反轉(zhuǎn)單鏈表[帶頭節(jié)點(diǎn)] * 思路: * 1.先定義一個節(jié)點(diǎn)reversalHead = new HeroNode(0,"",""); * 2.遍歷原來的鏈表,每遍歷一個節(jié)點(diǎn),就將其取出,并放在新的鏈表reversalHead的最前端 * 3.原來的鏈表的head.next = reversalHead; */ public static void reversalList(HeroNode head){ //鏈表為空或只有一個節(jié)點(diǎn),無需反轉(zhuǎn),直接返回 if(head.next == null || head.next.next == null){ return; } //輔助指針p HeroNode p = head.next; HeroNode next = null;//指向輔助指針p的下一個位置 HeroNode reversalHead = new HeroNode(0,"",""); //遍歷原來的鏈表,每遍歷一個節(jié)點(diǎn),就將其取出,并放在新的鏈表reversalHead的最前端 while(p != null){ next = p.next; p.next = reversalHead.next; reversalHead.next = p; p = next; } head.next = reversalHead.next; } /** * @Description: * 反向打印單鏈表[帶頭節(jié)點(diǎn)] * 思路1:單鏈表反轉(zhuǎn)后打印(不建議,因?yàn)槠茐牧藛捂湵淼慕Y(jié)構(gòu)) * 思路2:使用棧結(jié)構(gòu),利用棧先進(jìn)后出的特點(diǎn) */ public static void reversePrint(HeroNode head){ if(head.next == null){ return; } Stack<HeroNode> stack = new Stack<HeroNode>(); HeroNode p = head.next; while(p != null){ stack.push(p); p = p.next; } //將棧中的節(jié)點(diǎn)進(jìn)行打印 while(stack.size() > 0){ System.out.println(stack.pop()); } }}// 定義SingleLinkedList,管理英雄,即鏈表的增刪改查class SingleLinkedList { // 初始化頭結(jié)點(diǎn),不存放具體數(shù)據(jù) private HeroNode head = new HeroNode(0, "", ""); // 添加方式1:尾添加 // 思路: // 1.找到當(dāng)前鏈表的最后節(jié)點(diǎn) // 2.將這個最后的節(jié)點(diǎn)的next指向新的節(jié)點(diǎn) public void add(HeroNode heroNode) { // 因?yàn)閔ead頭不能動,因此需要一個輔助變量(指針)temp HeroNode temp = head; while (true) { // 如果遍歷到鏈表的最后 if (temp.next == null) { break; } // temp指針后移 temp = temp.next; } // 當(dāng)退出循環(huán)時,temp指向鏈表的最后 temp.next = heroNode; } public HeroNode getHead() { return head; } // 添加方式2:根據(jù)排名添加 public void addByOrder(HeroNode heroNode) { HeroNode temp = head;// 借助輔助指針 boolean flag = false;// 添加的編號是否存在 while (true) { if (temp.next == null) {// 遍歷到結(jié)尾 break; } if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) {// 該編號已存在 flag = true; break; } temp = temp.next;// 后移,遍歷當(dāng)前鏈表 } if (flag) { // 不能添加 System.out.printf("準(zhǔn)備插入的英雄的編號%d已經(jīng)存在,不能加入\n", heroNode.no); } else { // 插入到temp的后面 heroNode.next = temp.next; temp.next = heroNode; } } // 修改節(jié)點(diǎn)信息,根據(jù)節(jié)點(diǎn)的no屬性修改其他信息 public void update(HeroNode newHeroNode) { // 空鏈表無法修改節(jié)點(diǎn)信息 if (head.next == null) { System.out.println("鏈表為空~"); return; } // 根據(jù)no排名找到需要修改的節(jié)點(diǎn) HeroNode temp = head.next; boolean flag = false;// flag表示是否找到需要修改的節(jié)點(diǎn) while (true) { if (temp == null) { // 遍歷到結(jié)尾 break; } if (temp.no == newHeroNode.no) { // 找到 flag = true; break; } temp = temp.next;// 后移 } if (flag) { temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; } else { System.out.printf("沒有找到編號為%d的節(jié)點(diǎn),不能修改\n", newHeroNode.no); } } // 刪除節(jié)點(diǎn) // 思路: // 1.找到需要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn) // 2.temp.next=temp.next.next // 3.被刪除的節(jié)點(diǎn)將會被垃圾回收機(jī)制回收 public void delete(int no) { HeroNode temp = head; boolean flag = false;// 是否找到待刪除節(jié)點(diǎn) while (true) { if (temp.next == null) { // 遍歷到結(jié)尾 break; } if (temp.next.no == no) { // 找到了待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn) flag = true; break; } temp = temp.next;// 后移 } if (flag) { // 可以刪除 temp.next = temp.next.next; } else { System.out.printf("要刪除的%d節(jié)點(diǎn)不存在\n", no); } } // 顯示鏈表[遍歷] public void list() { // 空鏈表直接返回 if (head.next == null) { System.out.println("鏈表為空"); return; } // 仍然使用輔助變量(指針),進(jìn)行循環(huán) HeroNode temp = head.next; while (true) { if (temp == null) { break; } System.out.println(temp); // 將temp后移 temp = temp.next; } }}// 定義HeroNode,每一個HeroNode就是一個節(jié)點(diǎn)class HeroNode { public int no;// 排名 public String name; public String nickname;// 昵稱 public HeroNode next;// 指向下一個節(jié)點(diǎn) // 構(gòu)造器 public HeroNode() { super(); } public HeroNode(int no, String name, String nickname) { super(); this.no = no; this.name = name; this.nickname = nickname; } // 重寫toString @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; }}
感謝你的閱讀,希望你對“java實(shí)現(xiàn)單鏈表linked list的方法”這一關(guān)鍵問題有了一定的理解,具體使用情況還需要大家自己動手實(shí)驗(yàn)使用過才能領(lǐng)會,快去試試吧,如果想閱讀更多相關(guān)知識點(diǎn)的文章,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。