[[386512]]

 基本介紹

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

1. 鏈表是以節點的方式來存儲.
2. 每個節點包含data域,next域:指向下一個節點.
3. 如圖:發現每個鏈表的各個節點不一定是連續存儲
4. 鏈表分帶頭節點的鏈表和沒有頭節點的鏈表,根據實際的需求來確定.

單鏈表介紹

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

單鏈表的應用實例

使用帶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()); 
       } 
   } 

 【編輯推薦】