單鏈表

文章目錄

• • 單鏈表
  • • 前言
    • 單向鏈表的結(jié)構(gòu)
    • 代碼實(shí)現(xiàn)
    • • 鏈表存儲(chǔ)的節(jié)點(diǎn)
      • 鏈表初始化
      • 鏈表的基本操作
      • • 增加節(jié)點(diǎn)
        • 按照編號(hào)順序添加節(jié)點(diǎn)
        • 更新節(jié)點(diǎn)中數(shù)據(jù)
        • 遍歷鏈表
        • 獲取鏈表長度
        • 獲取倒數(shù)第n個(gè)節(jié)點(diǎn)

前言

在鏈表的學(xué)習(xí)之前，我們已經(jīng)學(xué)過了數(shù)組，在數(shù)組創(chuàng)建時(shí)，其數(shù)組長度已經(jīng)寫死了，因此對于數(shù)據(jù)的拓展，數(shù)組具有一定的局限性。數(shù)組有一個(gè)很重要的結(jié)構(gòu)就是索引，我們在數(shù)組中查詢數(shù)據(jù)也是用索引去查詢，因此當(dāng)需要?jiǎng)h除數(shù)據(jù)時(shí)，必須將所有數(shù)據(jù)進(jìn)行移動(dòng)改變索引，性能開銷相當(dāng)大，而鏈表就可以解決以上問題。

---

單向鏈表的結(jié)構(gòu)

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-Hyce4Vv3-1627915099881)(C:/Users/Supreme%20honor/Desktop/NoteBook/%E9%93%BE%E8%A1%A8.jpg)]

鏈表結(jié)構(gòu)比較簡單，就是一個(gè)個(gè)節(jié)點(diǎn)連接在一起，形成一個(gè)完整鏈?zhǔn)浇Y(jié)構(gòu)。每個(gè)節(jié)點(diǎn)包含兩部分(如圖)，一個(gè)是用于存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)域，一個(gè)是用于指向下一個(gè)節(jié)點(diǎn)的next指針。當(dāng)刪除數(shù)據(jù)時(shí)，只需要要改變前后節(jié)點(diǎn)的next引用關(guān)系即可，不需要像數(shù)組一次性出發(fā)所有數(shù)據(jù)的移動(dòng)，速度比數(shù)組快很多，也節(jié)省了很大的性能開銷。

---

代碼實(shí)現(xiàn)

鏈表存儲(chǔ)的節(jié)點(diǎn)

//存儲(chǔ)人物信息 class HeroNode {//人物序號(hào)：鏈表操作中有根據(jù)序號(hào)進(jìn)行排序的方法,添加此節(jié)點(diǎn)以測試鏈表數(shù)據(jù)的插入public int num;public String name;public String nickname;public HeroNode next;/*** 構(gòu)造器*/public HeroNode(int num, String name, String nickname) {this.num = num;this.name = name;this.nickname = nickname;}@Overridepublic String toString() {return "HeroNode{" +"num=" + num +", name='" + name + '\'' +", nickname='" + nickname+"}";} }

鏈表初始化

class SingleLinkedList {/*** 先初始化一個(gè)頭節(jié)點(diǎn),不放具體的數(shù)據(jù)*/private HeroNode headNode = new HeroNode(0,"",""); }

鏈表的基本操作

增加節(jié)點(diǎn)

/*** 添加節(jié)點(diǎn)到單向鏈表* 思路:當(dāng)不考慮編號(hào)順序時(shí)* 1.找到當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)* 2.將最后節(jié)點(diǎn)的next指向新的節(jié)點(diǎn)* @param node*/public void add(HeroNode node){//因?yàn)閔ead節(jié)點(diǎn)不能動(dòng),因此我們需要一個(gè)輔助遍歷指針tempHeroNode temp = headNode;//遍歷鏈表while (true){if (temp.next == null){break;}//后移指針temp = temp.next;}//退出while循環(huán)時(shí),temp就指向了鏈表的最后//將最后的節(jié)點(diǎn)指向新的節(jié)點(diǎn)//注意:不是headNode.next = node;temp.next = node;}

按照編號(hào)順序添加節(jié)點(diǎn)

/*** 需要按照編號(hào)的順序添加* 1.首先要找到新添加的節(jié)點(diǎn)的位置,是通過輔助指針遍歷* 2.新的節(jié)點(diǎn).next = temp.next* 3.將temp.next = 新的節(jié)點(diǎn)* @param node*/ public boolean addByOrder(HeroNode node) {//頭節(jié)點(diǎn)不能動(dòng),因此需要使用輔助指針找到應(yīng)插入的位置//單鏈表:temp要找到添加位置的前一個(gè)節(jié)點(diǎn)(讓這前一個(gè)節(jié)點(diǎn)的next域指向新的節(jié)點(diǎn))HeroNode temp = headNode;//編號(hào)是否以及存在,如果存在則添加失敗boolean hasExit = false;//遍歷鏈表while (true){//鏈表遍歷完畢if (temp.next == null){break;}//要讓temp指向要添加位置的前一個(gè)節(jié)點(diǎn)if (temp.next.num > node.num){break;}else if (temp.next.num == node.num){hasExit = true;break;}//向后移動(dòng)指針temp = temp.next;}//編號(hào)已經(jīng)存在if (hasExit){System.out.println("編號(hào)已存在,添加失敗....");return false;}else{//切記順序不可調(diào)換node.next = temp.next;temp.next = node;}return true; }

更新節(jié)點(diǎn)中數(shù)據(jù)

/*** 修改節(jié)點(diǎn)的信息,根據(jù)No編號(hào)來修改,No編號(hào)不能改* @param node*/ public void update(HeroNode node) {//判斷鏈表是否為空if (headNode.next == null){System.out.println("鏈表為空....");return;}//根據(jù)編號(hào)找到需要修改的節(jié)點(diǎn)HeroNode temp = headNode.next;boolean hasFound = false;while (true){//鏈表已經(jīng)遍歷完畢if (temp == null){break;}//找到待修改節(jié)點(diǎn)if (temp.num == node.num){hasFound = true;break;}temp = temp.next;}//找到節(jié)點(diǎn)if (hasFound){temp.name = node.name;temp.nickname = node.nickname;}else{System.out.println("沒有找到該編號(hào)的節(jié)點(diǎn)....");} }

遍歷鏈表

/*** 遍歷鏈表*/public void list(){System.out.println("-------------------------------List-------------------------------");//判斷鏈表是否為空if (headNode.next == null){System.out.println("鏈表為空");return;}//頭節(jié)點(diǎn)不能動(dòng)HeroNode temp = headNode.next;while (true){if (temp == null){break;}//輸出節(jié)點(diǎn)信息System.out.println(temp);//將temp后移temp = temp.next;}}

獲取鏈表長度

/*** 獲取單鏈表的節(jié)點(diǎn)個(gè)數(shù)(帶頭結(jié)點(diǎn)的鏈表不需要統(tǒng)計(jì)頭節(jié)點(diǎn))* @return 有效節(jié)點(diǎn)個(gè)數(shù)*/ public int getLength() {//空鏈表if (headNode.next == null){return 0;}int length = 0;HeroNode temp = headNode;while (temp.next != null){length++;temp = temp.next;}return length; }

獲取倒數(shù)第n個(gè)節(jié)點(diǎn)

/*** 查找單鏈表中的倒數(shù)第n個(gè)節(jié)點(diǎn)* 1.接受index->倒數(shù)第index個(gè)節(jié)點(diǎn)* 2.獲取鏈表長度length* 3.遍歷length-index個(gè)節(jié)點(diǎn)*/ public HeroNode getLastIndexNode(int index) throws Exception {if (headNode.next == null){return null;}int length = getLength();//對index進(jìn)行校驗(yàn)if (index <= 0 || index > length){throw new Exception("輸入索引錯(cuò)誤!");}HeroNode temp = headNode.next;for (int i = 0; i < length - index; i++){temp = temp.next;}return temp; } 《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的数据结构：单向链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。