原文地址:傳送門

鏈表(Linked List)介紹

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

小結:

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

每個節點包含 data 域， next 域：指向下一個節點.

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

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

結合一個實際的工作案例, 說明鏈表的實用價值

單鏈表

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

單鏈表的應用實例

使用帶head頭的單向鏈表實現 –水滸英雄排行榜管理 完成對英雄人物的增刪改查操作， 注: 刪除和修改,查找可以考慮學員獨立完成，也可帶學員完成 第一種方法在添加英雄時，直接添加到鏈表的尾部 第二種方式在添加英雄時，根據排名將英雄插入到指定位置(如果有這個排名，則添加失敗，并給出提示)

單鏈表的常見面試題有如下:

求單鏈表中有效節點的個數

查找單鏈表中的倒數第k個結點 【新浪面試題】

單鏈表的反轉【騰訊面試題，有點難度】

從尾到頭打印單鏈表 【百度，要求方式1：反向遍歷 。 方式2：Stack棧】

合并兩個有序的單鏈表，合并之后的鏈表依然有序【課后練習.】

直接看老師代碼演示 。

package com.atguigu.linkedlist;import java.util.Stack;public class SingleLinkedListDemo {public static void main(String[] args) {//進行測試//先創建節點HeroNode hero1 = new HeroNode(1, "宋江", "及時雨");HeroNode hero2 = new HeroNode(2, "盧俊義", "玉麒麟");HeroNode hero3 = new HeroNode(3, "吳用", "智多星");HeroNode hero4 = new HeroNode(4, "林沖", "豹子頭");//創建要給鏈表SingleLinkedList singleLinkedList = new SingleLinkedList();//加入singleLinkedList.add(hero1);singleLinkedList.add(hero4);singleLinkedList.add(hero2);singleLinkedList.add(hero3);// 測試一下單鏈表的反轉功能System.out.println("原來鏈表的情況~~");singleLinkedList.list();//        System.out.println("反轉單鏈表~~");
//        reversetList(singleLinkedList.getHead());
//        singleLinkedList.list();System.out.println("測試逆序打印單鏈表, 沒有改變鏈表的結構~~");reversePrint(singleLinkedList.getHead());/*        //加入按照編號的順序singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);//顯示一把singleLinkedList.list();//測試修改節點的代碼HeroNode newHeroNode = new HeroNode(2, "小盧", "玉麒麟~~");singleLinkedList.update(newHeroNode);System.out.println("修改后的鏈表情況~~");singleLinkedList.list();//刪除一個節點singleLinkedList.del(1);singleLinkedList.del(4);System.out.println("刪除后的鏈表情況~~");singleLinkedList.list();//測試一下 求單鏈表中有效節點的個數System.out.println("有效的節點個數=" + getLength(singleLinkedList.getHead()));//2//測試一下看看是否得到了倒數第K個節點HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3);System.out.println("res=" + res);
*/        }//方式2：//可以利用棧這個數據結構，將各個節點壓入到棧中，然后利用棧的先進后出的特點，就實現了逆序打印的效果public static void reversePrint(HeroNode head) {if(head.next == null) {return;//空鏈表，不能打印}//創建要給一個棧，將各個節點壓入棧Stack<HeroNode> stack = new Stack<HeroNode>();HeroNode cur = head.next;//將鏈表的所有節點壓入棧while(cur != null) {stack.push(cur);cur = cur.next; //cur后移，這樣就可以壓入下一個節點}//將棧中的節點進行打印,pop 出棧while (stack.size() > 0) {System.out.println(stack.pop()); //stack的特點是先進后出}}//將單鏈表反轉public static void reversetList(HeroNode head) {//如果當前鏈表為空，或者只有一個節點，無需反轉，直接返回if(head.next == null || head.next.next == null) {return ;}//定義一個輔助的指針(變量)，幫助我們遍歷原來的鏈表HeroNode cur = head.next;HeroNode next = null;// 指向當前節點[cur]的下一個節點HeroNode reverseHead = new HeroNode(0, "", "");//遍歷原來的鏈表，每遍歷一個節點，就將其取出，并放在新的鏈表reverseHead 的最前端//動腦筋while(cur != null) { next = cur.next;//先暫時保存當前節點的下一個節點，因為后面需要使用cur.next = reverseHead.next;//將cur的下一個節點指向新的鏈表的最前端reverseHead.next = cur; //將cur 連接到新的鏈表上cur = next;//讓cur后移}//將head.next 指向 reverseHead.next , 實現單鏈表的反轉head.next = reverseHead.next;}//查找單鏈表中的倒數第k個結點 【新浪面試題】//思路//1. 編寫一個方法，接收head節點，同時接收一個index //2. index 表示是倒數第index個節點//3. 先把鏈表從頭到尾遍歷，得到鏈表的總的長度 getLength//4. 得到size 后，我們從鏈表的第一個開始遍歷 (size-index)個，就可以得到//5. 如果找到了，則返回該節點，否則返回nulllpublic static HeroNode findLastIndexNode(HeroNode head, int index) {//判斷如果鏈表為空，返回nullif(head.next == null) {return null;//沒有找到}//第一個遍歷得到鏈表的長度(節點個數)int size = getLength(head);//第二次遍歷  size-index 位置，就是我們倒數的第K個節點//先做一個index的校驗if(index <=0 || index > size) {return null; }//定義給輔助變量， for 循環定位到倒數的indexHeroNode cur = head.next; //3 // 3 - 1 = 2for(int i =0; i< size - index; i++) {cur = cur.next;}return cur;}//方法：獲取到單鏈表的節點的個數(如果是帶頭結點的鏈表，需求不統計頭節點)/*** * @param head 鏈表的頭節點* @return 返回的就是有效節點的個數*/public static int getLength(HeroNode head) {if(head.next == null) { //空鏈表return 0;}int length = 0;//定義一個輔助的變量, 這里我們沒有統計頭節點HeroNode cur = head.next;while(cur != null) {length++;cur = cur.next; //遍歷}return length;}}//定義SingleLinkedList 管理我們的英雄
class SingleLinkedList {//先初始化一個頭節點, 頭節點不要動, 不存放具體的數據private HeroNode head = new HeroNode(0, "", "");//返回頭節點public HeroNode getHead() {return head;}//添加節點到單向鏈表//思路，當不考慮編號順序時//1. 找到當前鏈表的最后節點//2. 將最后這個節點的next 指向 新的節點public void add(HeroNode heroNode) {//因為head節點不能動，因此我們需要一個輔助遍歷 tempHeroNode temp = head;//遍歷鏈表，找到最后while(true) {//找到鏈表的最后if(temp.next == null) {//break;}//如果沒有找到最后, 將將temp后移temp = temp.next;}//當退出while循環時，temp就指向了鏈表的最后//將最后這個節點的next 指向 新的節點temp.next = heroNode;}//第二種方式在添加英雄時，根據排名將英雄插入到指定位置//(如果有這個排名，則添加失敗，并給出提示)public void addByOrder(HeroNode heroNode) {//因為頭節點不能動，因此我們仍然通過一個輔助指針(變量)來幫助找到添加的位置//因為單鏈表，因為我們找的temp 是位于 添加位置的前一個節點，否則插入不了HeroNode temp = head;boolean flag = false; // flag標志添加的編號是否存在，默認為falsewhile(true) {if(temp.next == null) {//說明temp已經在鏈表的最后break; //} if(temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入break;} else if (temp.next.no == heroNode.no) {//說明希望添加的heroNode的編號已然存在flag = true; //說明編號存在break;}temp = temp.next; //后移，遍歷當前鏈表}//判斷flag 的值if(flag) { //不能添加，說明編號存在System.out.printf("準備插入的英雄的編號 %d 已經存在了, 不能加入\n", heroNode.no);} else {//插入到鏈表中, temp的后面heroNode.next = temp.next;temp.next = heroNode;}}//修改節點的信息, 根據no編號來修改，即no編號不能改.//說明//1. 根據 newHeroNode 的 no 來修改即可public void update(HeroNode newHeroNode) {//判斷是否空if(head.next == null) {System.out.println("鏈表為空~");return;}//找到需要修改的節點, 根據no編號//定義一個輔助變量HeroNode temp = head.next;boolean flag = false; //表示是否找到該節點while(true) {if (temp == null) {break; //已經遍歷完鏈表}if(temp.no == newHeroNode.no) {//找到flag = true;break;}temp = temp.next;}//根據flag 判斷是否找到要修改的節點if(flag) {temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;} else { //沒有找到System.out.printf("沒有找到 編號 %d 的節點，不能修改\n", newHeroNode.no);}}//刪除節點//思路//1. head 不能動，因此我們需要一個temp輔助節點找到待刪除節點的前一個節點//2. 說明我們在比較時，是temp.next.no 和  需要刪除的節點的no比較public void del(int no) {HeroNode temp = head;boolean flag = false; // 標志是否找到待刪除節點的while(true) {if(temp.next == null) { //已經到鏈表的最后break;}if(temp.next.no == no) {//找到的待刪除節點的前一個節點tempflag = true;break;}temp = temp.next; //temp后移，遍歷}//判斷flagif(flag) { //找到//可以刪除temp.next = temp.next.next;}else {System.out.printf("要刪除的 %d 節點不存在\n", no);}}//顯示鏈表[遍歷]public void list() {//判斷鏈表是否為空if(head.next == null) {System.out.println("鏈表為空");return;}//因為頭節點，不能動，因此我們需要一個輔助變量來遍歷HeroNode temp = head.next;while(true) {//判斷是否到鏈表最后if(temp == null) {break;}//輸出節點的信息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;}//為了顯示方法，我們重新toString@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}}

運行結果

原來鏈表的情況~~
HeroNode [no=1, name=宋江, nickname=及時雨]
HeroNode [no=4, name=林沖, nickname=豹子頭]
HeroNode [no=2, name=盧俊義, nickname=玉麒麟]
HeroNode [no=3, name=吳用, nickname=智多星]
測試逆序打印單鏈表, 沒有改變鏈表的結構~~
HeroNode [no=3, name=吳用, nickname=智多星]
HeroNode [no=2, name=盧俊義, nickname=玉麒麟]
HeroNode [no=4, name=林沖, nickname=豹子頭]
HeroNode [no=1, name=宋江, nickname=及時雨]Process finished with exit code 0

原文地址:傳送門