這篇文章將為大家詳細講解有關(guān)Java編程內(nèi)功之怎么使用單鏈表，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。
淮陽網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)公司！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)等網(wǎng)站項目制作，到程序開發(fā)，運營維護。成都創(chuàng)新互聯(lián)公司于2013年創(chuàng)立到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設(shè)就選成都創(chuàng)新互聯(lián)公司。
基本介紹
鏈表是有序的列表,但是它在內(nèi)存中存儲如下
鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)
鏈表是以節(jié)點的方式來存儲.
每個節(jié)點包含data域,next域:指向下一個節(jié)點.
如圖:發(fā)現(xiàn)每個鏈表的各個節(jié)點不一定是連續(xù)存儲
鏈表分帶頭節(jié)點的鏈表和沒有頭節(jié)點的鏈表,根據(jù)實際的需求來確定.
單鏈表介紹
單鏈表(帶頭節(jié)點)邏輯結(jié)構(gòu)示意圖如下
單鏈表的應(yīng)用實例
使用帶head頭的單向鏈表實現(xiàn)-水滸英雄排行榜管理
重慶分公司
重慶分公司
package com.structures.linkedlist; public class SingleLinkedListDemo { public static void main(String[] args) { HeroNode heroNode1 = new HeroNode(1, "宋江", "及時雨"); HeroNode heroNode2 = new HeroNode(2, "盧俊義", "玉麒麟"); HeroNode heroNode3 = new HeroNode(3, "吳用", "智多星"); HeroNode heroNode4 = new HeroNode(4, "林沖", "豹子頭"); SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.add(heroNode3); singleLinkedList.add(heroNode2); singleLinkedList.add(heroNode4); singleLinkedList.add(heroNode1); singleLinkedList.list(); } } //定義SingleLinkedList管理我們的英雄 class SingleLinkedList { //先初始化一個頭節(jié)點,頭節(jié)點不能動,將來遍歷用 private HeroNode head = new HeroNode(0, "", ""); //添加節(jié)點到單向鏈表 //思路:當不考慮編號的順序時 //1. 找到當前鏈表的最后節(jié)點 //2. 將最后這個節(jié)點的next域指向新的節(jié)點 public void add(HeroNode node) { //因為head節(jié)點不能動,因此我們需要一個輔助遍歷temp HeroNode temp = head; //遍歷鏈表,找到最后 while (temp.next != null) { //找到鏈表的最后 //如果沒有找到temp就后移 temp = temp.next; } temp.next = node; } //顯示鏈表[遍歷] public void list() { //判斷鏈表是否為空 if (head.next == null) { System.out.println("鏈表為空"); } //因為頭節(jié)點不能動,因此我們需要一個輔助變量來遍歷 HeroNode temp = head.next; while (temp != null) { //判斷是否到最后 //輸出節(jié)點的信息 System.out.println(temp); //將temp后移 temp = temp.next; } } } //定義一個HeroNode,每個HeroNode對象就是一個節(jié)點 class HeroNode { public int no; public String name; public String nickName; public HeroNode next;//指向下一個節(jié)點 //構(gòu)造器 public HeroNode(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } public HeroNode getNext() { return next; } public void setNext(HeroNode next) { this.next = next; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } } /* HeroNode{no=3, name='吳用', nickName='智多星'} HeroNode{no=2, name='盧俊義', nickName='玉麒麟'} HeroNode{no=4, name='林沖', nickName='豹子頭'} HeroNode{no=1, name='宋江', nickName='及時雨'} */可以看到以上鏈表的實現(xiàn)方式,在添加英雄時,并未按照英雄的編號進行排序. 下面重新寫一個添加方法,實現(xiàn)插入英雄時按編號排序
package com.structures.linkedlist; public class SingleLinkedListDemo { public static void main(String[] args) { HeroNode heroNode1 = new HeroNode(1, "宋江", "及時雨"); HeroNode heroNode2 = new HeroNode(2, "盧俊義", "玉麒麟"); HeroNode heroNode3 = new HeroNode(3, "吳用", "智多星"); HeroNode heroNode4 = new HeroNode(4, "林沖", "豹子頭"); SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.addByNo(heroNode3); singleLinkedList.addByNo(heroNode2); singleLinkedList.addByNo(heroNode4); singleLinkedList.addByNo(heroNode1); singleLinkedList.list(); } } //定義SingleLinkedList管理我們的英雄 class SingleLinkedList { //先初始化一個頭節(jié)點,頭節(jié)點不能動,將來遍歷用 private HeroNode head = new HeroNode(0, "", ""); //添加節(jié)點到單向鏈表 //思路:當不考慮編號的順序時 //1. 找到當前鏈表的最后節(jié)點 //2. 將最后這個節(jié)點的next域指向新的節(jié)點 public void add(HeroNode node) { //因為head節(jié)點不能動,因此我們需要一個輔助遍歷temp HeroNode temp = head; //遍歷鏈表,找到最后 while (temp.next != null) { //找到鏈表的最后 //如果沒有找到temp就后移 temp = temp.next; } temp.next = node; } //第二種添加英雄的方式,在添加英雄時,根據(jù)排名將英雄插入到指定位置 //如果有這個排名,則添加失敗,并給出提示 public void addByNo(HeroNode heroNode) { //因為head節(jié)點不能動,因此我們需要一個輔助遍歷temp //因為單鏈表,因此找的temp是位于添加位置的前一個節(jié)點,否則加入不了 HeroNode temp = head; boolean flag = false;//標識添加的編號是否存在,默認false while (true) { if (temp.next == null) { break; } if (temp.next.no > heroNode.no) {//位置找到,就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) { //編號已存在 flag = true; break; } temp = temp.next; } if (flag) { System.out.printf("準備插入的英雄的編號 %d 已存在,不能加入\n", heroNode.no); } else { //插入鏈表temp的后面 heroNode.next = temp.next; temp.next = heroNode; } } //顯示鏈表[遍歷] public void list() { //判斷鏈表是否為空 if (head.next == null) { System.out.println("鏈表為空"); } //因為頭節(jié)點不能動,因此我們需要一個輔助變量來遍歷 HeroNode temp = head.next; while (temp != null) { //判斷是否到最后 //輸出節(jié)點的信息 System.out.println(temp); //將temp后移 temp = temp.next; } } } //定義一個HeroNode,每個HeroNode對象就是一個節(jié)點 class HeroNode { public int no; public String name; public String nickName; public HeroNode next;//指向下一個節(jié)點 //構(gòu)造器 public HeroNode(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } public HeroNode getNext() { return next; } public void setNext(HeroNode next) { this.next = next; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } } /* HeroNode{no=1, name='宋江', nickName='及時雨'} HeroNode{no=2, name='盧俊義', nickName='玉麒麟'} HeroNode{no=3, name='吳用', nickName='智多星'} HeroNode{no=4, name='林沖', nickName='豹子頭'} */再次進行完善功能,添加修改節(jié)點功能
//修改節(jié)點的信息,根據(jù)no編號來修改,即編號no不能修改. public void update(HeroNode heroNode) { //判斷是否為空 if (head.next == null) { System.out.println("鏈表為空"); } //找到需要修改的節(jié)點,根據(jù)no編號 HeroNode temp = head.next; boolean flag = false;//表示節(jié)點是否找到 while (true) { if (temp == null) { break; } if (temp.no == heroNode.no) { flag = true; break; } temp = temp.next; } if (flag) { temp.name = heroNode.name; temp.nickName = heroNode.nickName; } else { System.out.printf("沒有找到 編號%d 的節(jié)點,不能修改\n", heroNode.no); } }再次進行完善功能,添加刪除節(jié)點功能
//刪除節(jié)點 public void remove(HeroNode heroNode) { //判斷是否為空 if (head.next == null) { System.out.println("鏈表為空"); } HeroNode temp = head.next; boolean flag = false;//標識是否找到待刪除的點 while (true) { if (temp == null) { break; } if (temp.next.no == heroNode.no) { flag = true; break; } temp = temp.next; } if (flag) { temp.next = temp.next.next; } else { System.out.printf("無法刪除 編號%d 的節(jié)點,\n", heroNode.no); } }再次進行完善功能,添加統(tǒng)計單鏈表的有效節(jié)點數(shù)功能
/** * 獲取單鏈表的有效節(jié)點數(shù),不統(tǒng)計頭節(jié)點 * @param head 鏈表的頭結(jié)點 * @return 有效節(jié)點數(shù) */ public static int getLength(HeroNode head) { if (head.next == null) { return 0; } int count = 0; HeroNode temp = head.next; while (temp.next != null) { count++; temp = temp.next; } return count; }再次進行完善功能,添加查找單鏈表中的倒數(shù)第K個節(jié)點功能
/** * 查找單鏈表的倒數(shù)第K個節(jié)點[新浪面試題] * 思路: * 1.先把鏈表從頭到尾遍歷,得到鏈表的總長度 * 2.得到size后,從鏈表的第一個開始遍歷到(size-index)個,就可以得到 * * @param head * @param index 表示倒數(shù)第index個節(jié)點 * @return */ public static HeroNode findLastIndexNode(HeroNode head, int index) { if (head.next == null) { return null; } int size = getLength(head); if (index <= 0 || index > size) { return null; } HeroNode temp = head.next; for (int i = 0; i < (size - index); i++) { temp = temp.next; } return temp; }再次進行完善功能,添加單鏈表反轉(zhuǎn)功能
/** * 反轉(zhuǎn)鏈表[騰訊面試題] * 思路: * 1.先定義一個reverseHead = new HeroHead(); * 2.從頭到尾遍歷原來的鏈表,每遍歷一個節(jié)點,就將其取出,并放在新的鏈表的最前端; * 3.原來的鏈表的head.next = reverseHead.next; */ public static void reverseList(HeroNode head) { if (head.next == null || head.next.next == null) { return; } HeroNode curr = head.next; HeroNode next = null;//指向當前節(jié)點[curr]的下一個節(jié)點 HeroNode reverseHead = new HeroNode(0, "", ""); while (curr != null) { next = curr.next;//先暫時保存curr節(jié)點的下一個節(jié)點 curr.next = reverseHead.next;//將curr的下一個節(jié)點指向新的鏈表的最前端 reverseHead.next = curr;//將curr連接到新的鏈表上 curr = next;//讓curr后移 } head.next = reverseHead.next; }再次進行完善功能,添加從尾到頭打印單鏈表功能
/** * 使用棧的方式逆序打印[百度面試題] */ public static void reversePrint(HeroNode head) { if (head.next == null) { return; } Stack heroNodes = new Stack(); HeroNode temp = head.next; while (temp != null) { heroNodes.add(temp); temp = temp.next; } while (heroNodes.size() > 0) { System.out.println(heroNodes.pop()); } } 關(guān)于Java編程內(nèi)功之怎么使用單鏈表就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
