Java編程內功之怎么使用單鏈表

這篇文章將為大家詳細講解有關Java編程內功之怎么使用單鏈表，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

 基本介紹

鏈表是有序的列表,但是它在內存中存儲如下

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. 鏈表是以節點的方式來存儲.

3. 每個節點包含data域,next域:指向下一個節點.

4. 如圖:發現每個鏈表的各個節點不一定是連續存儲

5. 鏈表分帶頭節點的鏈表和沒有頭節點的鏈表,根據實際的需求來確定.

單鏈表介紹

單鏈表(帶頭節點)邏輯結構示意圖如下

單鏈表的應用實例

使用帶head頭的單向鏈表實現-水滸英雄排行榜管理

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 {     //先初始化一個頭節點,頭節點不能動,將來遍歷用     private HeroNode head = new HeroNode(0, "", "");      //添加節點到單向鏈表     //思路:當不考慮編號的順序時     //1. 找到當前鏈表的最后節點     //2. 將最后這個節點的next域指向新的節點     public void add(HeroNode node) {         //因為head節點不能動,因此我們需要一個輔助遍歷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("鏈表為空");         }         //因為頭節點不能動,因此我們需要一個輔助變量來遍歷         HeroNode temp = head.next;         while (temp != null) {             //判斷是否到最后             //輸出節點的信息             System.out.println(temp);             //將temp后移             temp = temp.next;         }     } }  //定義一個HeroNode,每個HeroNode對象就是一個節點 class HeroNode {     public int no;     public String name;     public String nickName;     public HeroNode next;//指向下一個節點      //構造器     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='及時雨'} */

可以看到以上鏈表的實現方式,在添加英雄時,并未按照英雄的編號進行排序. 下面重新寫一個添加方法,實現插入英雄時按編號排序

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 {     //先初始化一個頭節點,頭節點不能動,將來遍歷用     private HeroNode head = new HeroNode(0, "", "");      //添加節點到單向鏈表     //思路:當不考慮編號的順序時     //1. 找到當前鏈表的最后節點     //2. 將最后這個節點的next域指向新的節點     public void add(HeroNode node) {         //因為head節點不能動,因此我們需要一個輔助遍歷temp         HeroNode temp = head;         //遍歷鏈表,找到最后         while (temp.next != null) {             //找到鏈表的最后             //如果沒有找到temp就后移             temp = temp.next;         }         temp.next = node;     }      //第二種添加英雄的方式,在添加英雄時,根據排名將英雄插入到指定位置     //如果有這個排名,則添加失敗,并給出提示     public void addByNo(HeroNode heroNode) {         //因為head節點不能動,因此我們需要一個輔助遍歷temp         //因為單鏈表,因此找的temp是位于添加位置的前一個節點,否則加入不了         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("鏈表為空");         }         //因為頭節點不能動,因此我們需要一個輔助變量來遍歷         HeroNode temp = head.next;         while (temp != null) {             //判斷是否到最后             //輸出節點的信息             System.out.println(temp);             //將temp后移             temp = temp.next;         }     } }  //定義一個HeroNode,每個HeroNode對象就是一個節點 class HeroNode {     public int no;     public String name;     public String nickName;     public HeroNode next;//指向下一個節點      //構造器     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='豹子頭'} */

再次進行完善功能,添加修改節點功能

//修改節點的信息,根據no編號來修改,即編號no不能修改.     public void update(HeroNode heroNode) {         //判斷是否為空         if (head.next == null) {             System.out.println("鏈表為空");         }         //找到需要修改的節點,根據no編號         HeroNode temp = head.next;         boolean flag = false;//表示節點是否找到         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 的節點,不能修改\n", heroNode.no);         }     }

再次進行完善功能,添加刪除節點功能

//刪除節點     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 的節點,\n", heroNode.no);         }     }

再次進行完善功能,添加統計單鏈表的有效節點數功能

/**      * 獲取單鏈表的有效節點數,不統計頭節點      * @param head 鏈表的頭結點      * @return 有效節點數      */     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;     }

再次進行完善功能,添加查找單鏈表中的倒數第K個節點功能

/**      * 查找單鏈表的倒數第K個節點[新浪面試題]      * 思路:      * 1.先把鏈表從頭到尾遍歷,得到鏈表的總長度      * 2.得到size后,從鏈表的第一個開始遍歷到(size-index)個,就可以得到      *      * @param head      * @param index 表示倒數第index個節點      * @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;     }

再次進行完善功能,添加單鏈表反轉功能

/**    * 反轉鏈表[騰訊面試題]    * 思路:    * 1.先定義一個reverseHead = new HeroHead();    * 2.從頭到尾遍歷原來的鏈表,每遍歷一個節點,就將其取出,并放在新的鏈表的最前端;    * 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;//指向當前節點[curr]的下一個節點       HeroNode reverseHead = new HeroNode(0, "", "");        while (curr != null) {           next = curr.next;//先暫時保存curr節點的下一個節點           curr.next = reverseHead.next;//將curr的下一個節點指向新的鏈表的最前端           reverseHead.next = curr;//將curr連接到新的鏈表上           curr = next;//讓curr后移       }       head.next = reverseHead.next;   }

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

/**     * 使用棧的方式逆序打印[百度面試題]     */    public static void reversePrint(HeroNode head) {        if (head.next == null) {            return;        }        Stack<HeroNode> heroNodes = new Stack<HeroNode>();        HeroNode temp = head.next;        while (temp != null) {            heroNodes.add(temp);            temp = temp.next;        }        while (heroNodes.size() > 0) {            System.out.println(heroNodes.pop());        }    }

關于Java編程內功之怎么使用單鏈表就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。