文章目錄

一、連結清單介紹
二、單向連結清單的基本實作
- 2.1 節點類HeroNode
- 2.2 連結清單類SingleLinkedList
- 2.3 增
- - 2.1.1 添加到連結清單尾部add()
  - 2.1.2 按照編号的順序添加addByOrder()
- 2.4 删del()
- 2.5 改update()
- 2.6 查list()
三、基本面試題
- 3.1 擷取單連結清單節點的個數
- 3.2 查找單連結清單中的倒數第k個結點
- 3.3 單連結清單的反轉
- 3.4 逆序列印連結清單

歡迎通路筆者個人技術部落格：http://rukihuang.xyz/

一、連結清單介紹

連結清單是有序的清單，但是和數組這一資料結構不同，它在記憶體中可以是不連續的。如圖所示：

資料結構 03 — 單向連結清單一、連結清單介紹二、單向連結清單的基本實作三、基本面試題

連結清單的主要特點：
1. 連結清單是以節點的方式來存儲，是鍊式存儲
2. 每個結點包含 data 域， next 域（指向下一個節點）
3. 如上圖所示，連結清單的每一個結點不一定是連續存儲
4. 連結清單分帶頭節點的連結清單和沒有頭節點的連結清單，這根據實際的需求來确定
單連結清單（帶頭結點）邏輯結構如下：

資料結構 03 — 單向連結清單一、連結清單介紹二、單向連結清單的基本實作三、基本面試題

二、單向連結清單的基本實作

案例：以梁山好漢為對象，建立連結清單

2.1 節點類HeroNode

//定義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
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
}

2.2 連結清單類SingleLinkedList

//定義SingleLinkedList 管理我們的英雄
class SingleLinkedList {
	//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
	private HeroNode head = new HeroNode(0, "", "");
	
	//傳回頭節點
	public HeroNode getHead() {
		return head;
	}

	//添加節點到單向連結清單
	public void add(HeroNode heroNode) {
	}
	
	//第二種方式在添加英雄時，根據排名将英雄插入到指定位置
	public void addByOrder(HeroNode heroNode) {
	}

	//修改節點的資訊, 根據no編号來修改，即no編号不能改
	public void update(HeroNode newHeroNode) {
	}
	
	//删除節點
	public void del(int no) {
	}
	
	//顯示連結清單[周遊]
	public void list() {
	}
}

2.3 增

2.1.1 添加到連結清單尾部add()

思路分析
1. 建立一個 head 節點，作用就是表示單連結清單的頭
2. 每添加一個節點，就直接加入到連結清單的最後
3. 需要建立一個輔助節點變量 temp ，幫助周遊連結清單
代碼實作

//添加節點到單向連結清單
	//思路，當不考慮編号順序時
	//1. 找到目前連結清單的最後節點
	//2. 将最後這個節點的next 指向 新的節點
	public void add(HeroNode heroNode) {
		//因為head節點不能動，是以我們需要一個輔助周遊 temp
		HeroNode temp = head;
		//周遊連結清單，找到最後
		while(true) {
			//找到連結清單的最後
			if(temp.next == null) {//
				break;
			}
			//如果沒有找到最後, 将将temp後移
			temp = temp.next;
		}
		//當退出while循環時，temp就指向了連結清單的最後
		//将最後這個節點的next 指向 新的節點
		temp.next = heroNode;
	}

2.1.2 按照編号的順序添加addByOrder()

思路分析
1. 首先找到新添加的節點的位置，通過輔助變量（指針）周遊實作。
2. 找到後， 新節點.next = temp.next
3. temp.next = 新節點

//第二種方式在添加英雄時，根據排名将英雄插入到指定位置
	//(如果有這個排名，則添加失敗，并給出提示)
	public void addByOrder(HeroNode heroNode) {
		//因為頭節點不能動，是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
		//因為單連結清單，因為我們找的temp 是位于 添加位置的前一個節點，否則插入不了
		HeroNode temp = head;
		boolean flag = false; // flag标志添加的編号是否存在，預設為false
		while(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;
		}
	}

2.4 删del()

思路分析
1. 先要找到需要删除的這個節點的前一個節點 temp
2. temp.next = temp.next.next ，直接跳過目标節點，達到删除的目的
3. 被删除（被跳過）的節點，将不會有其他引用指向，會被垃圾回收機制回收
代碼實作

//删除節點
	//思路
	//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) {
				//找到的待删除節點的前一個節點temp
				flag = true;
				break;
			}
			temp = temp.next; //temp後移，周遊
		}
		//判斷flag
		if(flag) { //找到
			//可以删除
			temp.next = temp.next.next;
		}else {
			System.out.printf("要删除的 %d 節點不存在\n", no);
		}
	}

2.5 改update()

思路分析
1. 通過輔助指針，周遊找到該節點
2. 直接替換資訊即可
代碼實作

//修改節點的資訊, 根據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);
		}
	}

2.6 查list()

思路分析
1. 直接周遊，列印即可
代碼實作

//顯示連結清單[周遊]
	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;
		}
	}

三、基本面試題

3.1 擷取單連結清單節點的個數

思路分析
- 比較簡單，循環周遊節點，判斷是否為空，不為空自加1即可
代碼實作

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;
	}

3.2 查找單連結清單中的倒數第k個結點

思路分析：
1. 暴力法：周遊連結清單，得到連結清單的長度 size ， for 循環至 size-k 即可
2. 雙指針法：定義快指針變量和慢指針變量，慢指針比快指針晚k個節點出發，當快指針到達連結清單最後時，慢指針位置即為倒數第k個節點
代碼實作

//暴力法：
	//查找單連結清單中的倒數第k個結點 【新浪面試題】
	//思路
	//1. 編寫一個方法，接收head節點，同時接收一個index 
	//2. index 表示是倒數第index個節點
	//3. 先把連結清單從頭到尾周遊，得到連結清單的總的長度 getLength
	//4. 得到size 後，我們從連結清單的第一個開始周遊 (size-index)個，就可以得到
	//5. 如果找到了，則傳回該節點，否則傳回nulll
	public static HeroNode findLastIndexNode(HeroNode head, int index) {
		//判斷如果連結清單為空，傳回null
		if(head.next == null) {
			return null;//沒有找到
		}
		//第一個周遊得到連結清單的長度(節點個數)
		int size = getLength(head);
		//第二次周遊  size-index 位置，就是我們倒數的第K個節點
		//先做一個index的校驗
		if(index <=0 || index > size) {
			return null; 
		}
		//定義給輔助變量， for 循環定位到倒數的index
		HeroNode cur = head.next; //3 // 3 - 1 = 2
		for(int i =0; i< size - index; i++) {
			cur = cur.next;
		}
		return cur;
		
	}

//雙指針法
    public Node findLastIndexNode(int index) {
        if (index < 0) throw new RuntimeException("下标異常");
        Node fast = head.next;//快指針
        Node slow = head.next;//慢指針
        int count = 0;//記錄慢指針比快指針差距的節點數量
        while (fast != null) {
            if (count < index) {//沒到目标數，快跑，慢不跑
                fast = fast.next;
                count++;
            } else if (count == index) {//當差距為目标差距，快慢指針一起跑
                fast = fast.next;
                slow = slow.next;
            }
        }

        if (count < index) {
            throw new RuntimeException("超過連結清單長度");
        } else {
            return slow;
        }
    }

3.3 單連結清單的反轉

思路分析
1. 先定義一個結點 reversedHead
2. 從頭到尾周遊原來的連結清單，每周遊一個結點，就将其取出，并放在新的連結清單 reversedHead 的最前端
3. 原來的連結清單的 head.next = reversedHead.next
代碼實作

//将單連結清單反轉
	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;
	}

3.4 逆序列印連結清單

思路分析
- 方式一：先反轉，再周遊，但不建議，會破壞原來單連結清單的結構
- 方式二：利用棧。将各個節點壓入棧中，利用棧先進後出的特點，實作逆序列印
代碼實作

//可以利用棧這個資料結構，将各個節點壓入到棧中，然後利用棧的先進後出的特點，就實作了逆序列印的效果
	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的特點是先進後出
		}
	}

資料結構 03 — 單向連結清單一、連結清單介紹二、單向連結清單的基本實作三、基本面試題

文章目錄

一、連結清單介紹

二、單向連結清單的基本實作

2.1 節點類HeroNode

2.2 連結清單類SingleLinkedList

2.3 增

2.1.1 添加到連結清單尾部add()

2.1.2 按照編号的順序添加addByOrder()

2.4 删del()

2.5 改update()

2.6 查list()

三、基本面試題

3.1 擷取單連結清單節點的個數

3.2 查找單連結清單中的倒數第k個結點

3.3 單連結清單的反轉

3.4 逆序列印連結清單

繼續閱讀

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

基礎算法之二分查找

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

poj3249

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

PAT 1089 Insert or Merge[難]

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器