自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

Java編程內(nèi)功-數(shù)據(jù)結(jié)構(gòu)與算法「單鏈表」

作者：Java精髓
開(kāi)發(fā) 后端 算法
本篇繼續(xù)給大家介紹Java編程內(nèi)功數(shù)據(jù)結(jié)構(gòu)與算法，今天主要介紹有關(guān)單鏈表的相關(guān)知識(shí)，希望能夠幫助到你。

[[386512]]

 基本介紹

鏈表是有序的列表,但是它在內(nèi)存中存儲(chǔ)如下


  1. 鏈表是以節(jié)點(diǎn)的方式來(lái)存儲(chǔ).
  2. 每個(gè)節(jié)點(diǎn)包含data域,next域:指向下一個(gè)節(jié)點(diǎn).
  3. 如圖:發(fā)現(xiàn)每個(gè)鏈表的各個(gè)節(jié)點(diǎn)不一定是連續(xù)存儲(chǔ)
  4. 鏈表分帶頭節(jié)點(diǎn)的鏈表和沒(méi)有頭節(jié)點(diǎn)的鏈表,根據(jù)實(shí)際的需求來(lái)確定.

單鏈表介紹

單鏈表(帶頭節(jié)點(diǎn))邏輯結(jié)構(gòu)示意圖如下


單鏈表的應(yīng)用實(shí)例

使用帶head頭的單向鏈表實(shí)現(xiàn)-水滸英雄排行榜管理

  1. package com.structures.linkedlist; 
  2.  
  3. public class SingleLinkedListDemo { 
  4.     public static void main(String[] args) { 
  5.         HeroNode heroNode1 = new HeroNode(1, "宋江", "及時(shí)雨"); 
  6.         HeroNode heroNode2 = new HeroNode(2, "盧俊義", "玉麒麟"); 
  7.         HeroNode heroNode3 = new HeroNode(3, "吳用", "智多星"); 
  8.         HeroNode heroNode4 = new HeroNode(4, "林沖", "豹子頭"); 
  9.         SingleLinkedList singleLinkedList = new SingleLinkedList(); 
  10.         singleLinkedList.add(heroNode3); 
  11.         singleLinkedList.add(heroNode2); 
  12.         singleLinkedList.add(heroNode4); 
  13.         singleLinkedList.add(heroNode1); 
  14.         singleLinkedList.list(); 
  15.     } 
  16. } 
  17.  
  18. //定義SingleLinkedList管理我們的英雄 
  19. class SingleLinkedList { 
  20.     //先初始化一個(gè)頭節(jié)點(diǎn),頭節(jié)點(diǎn)不能動(dòng),將來(lái)遍歷用 
  21.     private HeroNode head = new HeroNode(0, "", ""); 
  22.  
  23.     //添加節(jié)點(diǎn)到單向鏈表 
  24.     //思路:當(dāng)不考慮編號(hào)的順序時(shí) 
  25.     //1. 找到當(dāng)前鏈表的最后節(jié)點(diǎn) 
  26.     //2. 將最后這個(gè)節(jié)點(diǎn)的next域指向新的節(jié)點(diǎn) 
  27.     public void add(HeroNode node) { 
  28.         //因?yàn)閔ead節(jié)點(diǎn)不能動(dòng),因此我們需要一個(gè)輔助遍歷temp 
  29.         HeroNode temp = head; 
  30.         //遍歷鏈表,找到最后 
  31.         while (temp.next != null) { 
  32.             //找到鏈表的最后 
  33.             //如果沒(méi)有找到temp就后移 
  34.             temp = temp.next; 
  35.         } 
  36.         temp.next = node; 
  37.     } 
  38.  
  39.     //顯示鏈表[遍歷] 
  40.     public void list() { 
  41.         //判斷鏈表是否為空 
  42.         if (head.next == null) { 
  43.             System.out.println("鏈表為空"); 
  44.         } 
  45.         //因?yàn)轭^節(jié)點(diǎn)不能動(dòng),因此我們需要一個(gè)輔助變量來(lái)遍歷 
  46.         HeroNode temp = head.next; 
  47.         while (temp != null) { 
  48.             //判斷是否到最后 
  49.             //輸出節(jié)點(diǎn)的信息 
  50.             System.out.println(temp); 
  51.             //將temp后移 
  52.             temp = temp.next; 
  53.         } 
  54.     } 
  55. } 
  56.  
  57. //定義一個(gè)HeroNode,每個(gè)HeroNode對(duì)象就是一個(gè)節(jié)點(diǎn) 
  58. class HeroNode { 
  59.     public int no; 
  60.     public String name; 
  61.     public String nickName; 
  62.     public HeroNode next;//指向下一個(gè)節(jié)點(diǎn) 
  63.  
  64.     //構(gòu)造器 
  65.     public HeroNode(int no, String name, String nickName) { 
  66.         this.no = no; 
  67.         this.name = name; 
  68.         this.nickName = nickName; 
  69.     } 
  70.  
  71.     public HeroNode getNext() { 
  72.         return next; 
  73.     } 
  74.  
  75.     public void setNext(HeroNode next) { 
  76.         this.next = next; 
  77.     } 
  78.  
  79.     @Override 
  80.     public String toString() { 
  81.         return "HeroNode{" + 
  82.                 "no=" + no + 
  83.                 ", name='" + name + '\'' + 
  84.                 ", nickName='" + nickName + '\'' + 
  85.                 '}'; 
  86.     } 
  87. } 
  88. /* 
  89. HeroNode{no=3, name='吳用', nickName='智多星'} 
  90. HeroNode{no=2, name='盧俊義', nickName='玉麒麟'} 
  91. HeroNode{no=4, name='林沖', nickName='豹子頭'} 
  92. HeroNode{no=1, name='宋江', nickName='及時(shí)雨'} 
  93. */ 

 可以看到以上鏈表的實(shí)現(xiàn)方式,在添加英雄時(shí),并未按照英雄的編號(hào)進(jìn)行排序. 下面重新寫(xiě)一個(gè)添加方法,實(shí)現(xiàn)插入英雄時(shí)按編號(hào)排序

  1. package com.structures.linkedlist; 
  2.  
  3. public class SingleLinkedListDemo { 
  4.     public static void main(String[] args) { 
  5.         HeroNode heroNode1 = new HeroNode(1, "宋江", "及時(shí)雨"); 
  6.         HeroNode heroNode2 = new HeroNode(2, "盧俊義", "玉麒麟"); 
  7.         HeroNode heroNode3 = new HeroNode(3, "吳用", "智多星"); 
  8.         HeroNode heroNode4 = new HeroNode(4, "林沖", "豹子頭"); 
  9.         SingleLinkedList singleLinkedList = new SingleLinkedList(); 
  10.         singleLinkedList.addByNo(heroNode3); 
  11.         singleLinkedList.addByNo(heroNode2); 
  12.         singleLinkedList.addByNo(heroNode4); 
  13.         singleLinkedList.addByNo(heroNode1); 
  14.         singleLinkedList.list(); 
  15.     } 
  16. } 
  17.  
  18. //定義SingleLinkedList管理我們的英雄 
  19. class SingleLinkedList { 
  20.     //先初始化一個(gè)頭節(jié)點(diǎn),頭節(jié)點(diǎn)不能動(dòng),將來(lái)遍歷用 
  21.     private HeroNode head = new HeroNode(0, "", ""); 
  22.  
  23.     //添加節(jié)點(diǎn)到單向鏈表 
  24.     //思路:當(dāng)不考慮編號(hào)的順序時(shí) 
  25.     //1. 找到當(dāng)前鏈表的最后節(jié)點(diǎn) 
  26.     //2. 將最后這個(gè)節(jié)點(diǎn)的next域指向新的節(jié)點(diǎn) 
  27.     public void add(HeroNode node) { 
  28.         //因?yàn)閔ead節(jié)點(diǎn)不能動(dòng),因此我們需要一個(gè)輔助遍歷temp 
  29.         HeroNode temp = head; 
  30.         //遍歷鏈表,找到最后 
  31.         while (temp.next != null) { 
  32.             //找到鏈表的最后 
  33.             //如果沒(méi)有找到temp就后移 
  34.             temp = temp.next; 
  35.         } 
  36.         temp.next = node; 
  37.     } 
  38.  
  39.     //第二種添加英雄的方式,在添加英雄時(shí),根據(jù)排名將英雄插入到指定位置 
  40.     //如果有這個(gè)排名,則添加失敗,并給出提示 
  41.     public void addByNo(HeroNode heroNode) { 
  42.         //因?yàn)閔ead節(jié)點(diǎn)不能動(dòng),因此我們需要一個(gè)輔助遍歷temp 
  43.         //因?yàn)閱捂湵?因此找的temp是位于添加位置的前一個(gè)節(jié)點(diǎn),否則加入不了 
  44.         HeroNode temp = head; 
  45.         boolean flag = false;//標(biāo)識(shí)添加的編號(hào)是否存在,默認(rèn)false 
  46.         while (true) { 
  47.             if (temp.next == null) { 
  48.                 break; 
  49.             } 
  50.             if (temp.next.no > heroNode.no) {//位置找到,就在temp的后面插入 
  51.                 break; 
  52.             } else if (temp.next.no == heroNode.no) { 
  53.                 //編號(hào)已存在 
  54.                 flag = true; 
  55.                 break; 
  56.             } 
  57.             temp = temp.next; 
  58.         } 
  59.         if (flag) { 
  60.             System.out.printf("準(zhǔn)備插入的英雄的編號(hào) %d 已存在,不能加入\n", heroNode.no); 
  61.         } else { 
  62.             //插入鏈表temp的后面 
  63.             heroNode.next = temp.next; 
  64.             temp.next = heroNode; 
  65.         } 
  66.     } 
  67.  
  68.     //顯示鏈表[遍歷] 
  69.     public void list() { 
  70.         //判斷鏈表是否為空 
  71.         if (head.next == null) { 
  72.             System.out.println("鏈表為空"); 
  73.         } 
  74.         //因?yàn)轭^節(jié)點(diǎn)不能動(dòng),因此我們需要一個(gè)輔助變量來(lái)遍歷 
  75.         HeroNode temp = head.next; 
  76.         while (temp != null) { 
  77.             //判斷是否到最后 
  78.             //輸出節(jié)點(diǎn)的信息 
  79.             System.out.println(temp); 
  80.             //將temp后移 
  81.             temp = temp.next; 
  82.         } 
  83.     } 
  84. } 
  85.  
  86. //定義一個(gè)HeroNode,每個(gè)HeroNode對(duì)象就是一個(gè)節(jié)點(diǎn) 
  87. class HeroNode { 
  88.     public int no; 
  89.     public String name; 
  90.     public String nickName; 
  91.     public HeroNode next;//指向下一個(gè)節(jié)點(diǎn) 
  92.  
  93.     //構(gòu)造器 
  94.     public HeroNode(int no, String name, String nickName) { 
  95.         this.no = no; 
  96.         this.name = name; 
  97.         this.nickName = nickName; 
  98.     } 
  99.  
  100.     public HeroNode getNext() { 
  101.         return next; 
  102.     } 
  103.  
  104.     public void setNext(HeroNode next) { 
  105.         this.next = next; 
  106.     } 
  107.  
  108.     @Override 
  109.     public String toString() { 
  110.         return "HeroNode{" + 
  111.                 "no=" + no + 
  112.                 ", name='" + name + '\'' + 
  113.                 ", nickName='" + nickName + '\'' + 
  114.                 '}'; 
  115.     } 
  116. } 
  117. /* 
  118. HeroNode{no=1, name='宋江', nickName='及時(shí)雨'} 
  119. HeroNode{no=2, name='盧俊義', nickName='玉麒麟'} 
  120. HeroNode{no=3, name='吳用', nickName='智多星'} 
  121. HeroNode{no=4, name='林沖', nickName='豹子頭'} 
  122. */ 

 再次進(jìn)行完善功能,添加修改節(jié)點(diǎn)功能

  1. //修改節(jié)點(diǎn)的信息,根據(jù)no編號(hào)來(lái)修改,即編號(hào)no不能修改. 
  2.     public void update(HeroNode heroNode) { 
  3.         //判斷是否為空 
  4.         if (head.next == null) { 
  5.             System.out.println("鏈表為空"); 
  6.         } 
  7.         //找到需要修改的節(jié)點(diǎn),根據(jù)no編號(hào) 
  8.         HeroNode temp = head.next; 
  9.         boolean flag = false;//表示節(jié)點(diǎn)是否找到 
  10.         while (true) { 
  11.             if (temp == null) { 
  12.                 break; 
  13.             } 
  14.             if (temp.no == heroNode.no) { 
  15.                 flag = true; 
  16.                 break; 
  17.             } 
  18.             temp = temp.next; 
  19.         } 
  20.         if (flag) { 
  21.             temp.name = heroNode.name; 
  22.             temp.nickName = heroNode.nickName; 
  23.         } else { 
  24.             System.out.printf("沒(méi)有找到 編號(hào)%d 的節(jié)點(diǎn),不能修改\n", heroNode.no); 
  25.         } 
  26.     } 

 再次進(jìn)行完善功能,添加刪除節(jié)點(diǎn)功能

  1. //刪除節(jié)點(diǎn) 
  2.     public void remove(HeroNode heroNode) { 
  3.         //判斷是否為空 
  4.         if (head.next == null) { 
  5.             System.out.println("鏈表為空"); 
  6.         } 
  7.         HeroNode temp = head.next; 
  8.         boolean flag = false;//標(biāo)識(shí)是否找到待刪除的點(diǎn) 
  9.         while (true) { 
  10.             if (temp == null) { 
  11.                 break; 
  12.             } 
  13.             if (temp.next.no == heroNode.no) { 
  14.                 flag = true; 
  15.                 break; 
  16.             } 
  17.             temp = temp.next; 
  18.         } 
  19.         if (flag) { 
  20.             temp.next = temp.next.next; 
  21.         } else { 
  22.             System.out.printf("無(wú)法刪除 編號(hào)%d 的節(jié)點(diǎn),\n", heroNode.no); 
  23.         } 
  24.     } 

 再次進(jìn)行完善功能,添加統(tǒng)計(jì)單鏈表的有效節(jié)點(diǎn)數(shù)功能

  1. /** 
  2.      * 獲取單鏈表的有效節(jié)點(diǎn)數(shù),不統(tǒng)計(jì)頭節(jié)點(diǎn) 
  3.      * @param head 鏈表的頭結(jié)點(diǎn) 
  4.      * @return 有效節(jié)點(diǎn)數(shù) 
  5.      */ 
  6.     public static int getLength(HeroNode head) { 
  7.         if (head.next == null) { 
  8.             return 0; 
  9.         } 
  10.         int count = 0; 
  11.         HeroNode temp = head.next; 
  12.         while (temp.next != null) { 
  13.             count++; 
  14.             temp = temp.next; 
  15.         } 
  16.         return count; 
  17.     } 

 再次進(jìn)行完善功能,添加查找單鏈表中的倒數(shù)第K個(gè)節(jié)點(diǎn)功能

  1. /** 
  2.      * 查找單鏈表的倒數(shù)第K個(gè)節(jié)點(diǎn)[新浪面試題] 
  3.      * 思路: 
  4.      * 1.先把鏈表從頭到尾遍歷,得到鏈表的總長(zhǎng)度 
  5.      * 2.得到size后,從鏈表的第一個(gè)開(kāi)始遍歷到(size-index)個(gè),就可以得到 
  6.      * 
  7.      * @param head 
  8.      * @param index 表示倒數(shù)第index個(gè)節(jié)點(diǎn) 
  9.      * @return 
  10.      */ 
  11.     public static HeroNode findLastIndexNode(HeroNode head, int index) { 
  12.         if (head.next == null) { 
  13.             return null; 
  14.         } 
  15.         int size = getLength(head); 
  16.         if (index <= 0 || index > size) { 
  17.             return null; 
  18.         } 
  19.         HeroNode temp = head.next; 
  20.         for (int i = 0; i < (size - index); i++) { 
  21.             temp = temp.next; 
  22.         } 
  23.         return temp; 
  24.     } 

 再次進(jìn)行完善功能,添加單鏈表反轉(zhuǎn)功能

  1. /** 
  2.    * 反轉(zhuǎn)鏈表[騰訊面試題] 
  3.    * 思路: 
  4.    * 1.先定義一個(gè)reverseHead = new HeroHead(); 
  5.    * 2.從頭到尾遍歷原來(lái)的鏈表,每遍歷一個(gè)節(jié)點(diǎn),就將其取出,并放在新的鏈表的最前端; 
  6.    * 3.原來(lái)的鏈表的head.next = reverseHead.next; 
  7.    */ 
  8.   public static void reverseList(HeroNode head) { 
  9.       if (head.next == null || head.next.next == null) { 
  10.           return; 
  11.       } 
  12.       HeroNode curr = head.next; 
  13.       HeroNode next = null;//指向當(dāng)前節(jié)點(diǎn)[curr]的下一個(gè)節(jié)點(diǎn) 
  14.       HeroNode reverseHead = new HeroNode(0, "", ""); 
  15.  
  16.       while (curr != null) { 
  17.           next = curr.next;//先暫時(shí)保存curr節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) 
  18.           curr.next = reverseHead.next;//將curr的下一個(gè)節(jié)點(diǎn)指向新的鏈表的最前端 
  19.           reverseHead.next = curr;//將curr連接到新的鏈表上 
  20.           curr = next;//讓curr后移 
  21.       } 
  22.       head.next = reverseHead.next; 
  23.   } 

 再次進(jìn)行完善功能,添加從尾到頭打印單鏈表功能

  1. /** 
  2.     * 使用棧的方式逆序打印[百度面試題] 
  3.     */ 
  4.    public static void reversePrint(HeroNode head) { 
  5.        if (head.next == null) { 
  6.            return; 
  7.        } 
  8.        Stack<HeroNode> heroNodes = new Stack<HeroNode>(); 
  9.        HeroNode temp = head.next; 
  10.        while (temp != null) { 
  11.            heroNodes.add(temp); 
  12.            temp = temp.next; 
  13.        } 
  14.        while (heroNodes.size() > 0) { 
  15.            System.out.println(heroNodes.pop()); 
  16.        } 
  17.    } 

 【編輯推薦】

 

責(zé)任編輯：姜華 來(lái)源： 今日頭條
Java數(shù)據(jù)結(jié)構(gòu)算法單鏈表
相關(guān)推薦

2021-03-11 08:53:20

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-05-12 09:07:09

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-13 09:37:41

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-09 06:30:32

JAVA數(shù)據(jù)結(jié)構(gòu)算法

2021-03-18 08:44:20

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-26 08:40:28

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-12 09:13:47

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-23 08:33:22

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-17 09:27:36

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-08 06:28:57

JAVA數(shù)據(jù)結(jié)構(gòu)與算法稀疏數(shù)組

2021-04-16 09:40:52

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-07 09:26:37

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-15 09:36:44

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-22 10:07:45

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-14 08:27:40

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-23 09:12:09

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-05-13 07:34:56

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-24 10:41:04

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-05-08 08:28:38

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-27 06:21:29

Java數(shù)據(jù)結(jié)構(gòu)算法
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)