# 單向鏈結串列(Singly Linked List)
鏈結串列以節點(node)來儲存資料，每個節點中包含兩個域：資料域(data)、指標域(next)，指標域用於指向下一個節點，將這些節點串連起來形成 Linked List，而最後一個節點則指向一個空值。
鏈結串列的各個節點不一定是連續存放的。
**實際應用案例**
客戶端發來好友編號21、1、19、38、5，要求按照編號大小順序將這幾位的資訊傳回來，為了速度不允許經過數據庫，那我們可以使用鏈結串列來解決。
## 新增鏈結串列數據
使用帶head的單向鏈結串列實現 - 水滸英雄排行榜管理。
- **目標**：完成對英雄人物的增、刪、改、查操作。
- 第一種方法在添加英雄時，直接添加到鏈結串列的尾部
- 第二種方式在添加英雄時，根據排名將英雄插入指定位置（如果有這個排名，則添加失敗，並給出提示）
## 代碼實現
### 第一種
添加英雄時，直接添加到鏈結串列的尾部
```java=
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(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);
singleLinkedList.list();
}
}
//定義SingleLinkedList 管理英雄
class SingleLinkedList {
//先初始化一個頭節點,頭節點不要動,不存放具體數據
private HeroNode head = new HeroNode(0, "", "");
//添加節點到單向鏈結串列
//思路:當不考慮編號順序時
//1.找到當前鏈結串列的最後節點
//2.將最後節點的next域指向新的節點
public void add(HeroNode heroNode) {
//因為head節點不能動,因此我們需要一個輔助遍歷 temp
HeroNode temp = head;
//遍歷鏈結串列,找到最後
while(true) {
if (temp.next == null) {
break;
}
temp = temp.next; //沒找到就將temp後移一個節點
}
//當退出while循環時,temp就指向了鏈結串列的最後
//將最後這個節點的next指向新的節點
temp.next = heroNode;
}
//顯示鏈結串列
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
@Override
public String toString() {
return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
}
}
```
接著是需要按照編號順序添加的代碼實現方式。
**原本**
現在我們需要新增新的英雄, 編號為2，本來是no.1,no.4,no.7，欲新增no.2，所以需要插入到no.1,no.4之間。
**思路**
1. 首先找到新添加節點的位置,是通過輔助變數 (通過遍歷找到位置)
2. 新的節點.next = temp.next;
3. temp.next = 新的節點
### 第二種
按照編號順序插入數據，只需要在`SingleLinkedList`類別中新增一個方法 `addByOrder(HeroNode heroNode)`
```java=
public void addByOrder(HeroNode heroNode) {
//因為頭節點不能動,因此仍用輔助變數來幫助找到添加的位置
//因為是單向鏈結串列，所以temp是位於添加位置的前一個節點
HeroNode temp = head;
boolean flag = 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;
}
//判斷flag的值
if(flag) {
System.out.printf("準備添加的英雄編號 %d 已經存在，不能添加\n",heroNode.no);
}else{
//插入到鏈結串列中, temp的後面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
```
加入順序打亂後輸出
```java=
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.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero3); //試著加入已經存在的編號的英雄
singleLinkedList.list();
}
```
即使新增的數據編號不是按照由小到大排序，最終還是會按照編號順序輸出：
## 修改節點數據
在 `SingleLinkedList` 類中新增 update 方法：
```java=
//修改節點的資訊,根據編號來修改
public void updata(HeroNode newHeroNode) {
if(head.next == null) {
System.out.println("鏈結串列為空");
return;
}
//找到需要修改的節點
//定義一個輔助變數
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);
}
}
```
```java=
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.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
singleLinkedList.list();
HeroNode newHeroNode = new HeroNode(2, "小盧", "玉麒麟~~");
singleLinkedList.updata(newHeroNode);
System.out.println("=====修改後的結果=====");
singleLinkedList.list();
}
```
## 鏈結串列刪除數據
首先給各位五分鐘時間思考一下該如何刪除鏈結串列的節點，千萬別犯了跟我一樣的錯。
### 思路
> 1. 遍歷鏈結串列，找到要刪除的節點的前一個節點：`temp.next.no == heroNode.no`
> 2. temp 為要刪除的節點的前一個節點
> 3. 將 temp.next指向要刪除的節點的next節點：`temp.next = heroNode.next;`
這是我在還沒看老師所寫的程式碼之前自己寫的刪除方法，是可以實現的：
```java=
public void delete(HeroNode heroNode) {
HeroNode temp = head.next;
boolean flag = false;
boolean first = false;
while(true) {
if (temp == null) break; //已遍歷結束
if(heroNode.no == head.next.no) { //要刪除的節點為第一個節點
first = true;
System.out.println("first: "+first);
break;
}else if (temp.next.no == heroNode.no) {
flag = true;
System.out.println("flag: "+flag);
break;
}
temp = temp.next;
}
if(flag) {
temp.next = heroNode.next;
}else if(first){
System.out.printf("要刪除的 %d 為頭節點\n",heroNode.no);
head.next = temp.next;
}else {
System.out.printf("沒有找到編號 %d 的節點, 不能刪除\n",heroNode.no);
}
}
```
```java=
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.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
singleLinkedList.list();
System.out.println("=====刪除後的結果=====");
singleLinkedList.delete(hero4); //被刪除的節點不會有其他引用指向，會被垃圾回收機制回收。
singleLinkedList.list();
singleLinkedList.delete(hero2); //刪除編號2
singleLinkedList.list();
singleLinkedList.delete(hero3);; //刪除編號3
singleLinkedList.list();
singleLinkedList.delete(hero1);; //刪除編號4
singleLinkedList.list();
}
```
然而，看了老師寫法後，我才發現什麼叫做自己坑自己
如果把這一段
```java
if(heroNode.no == head.next.no) { //要刪除的節點為第一個節點
first = true;
break;
}else if (temp.next.no == heroNode.no) {
flag = true;
break;
}
```
改為
```java=
if (temp.no == heroNode.no) {
flag = true;
break;
}
```
就萬事太平....
### 簡易寫法
完整程式碼如下：
```java=
public void delete(HeroNode heroNode) {
HeroNode temp = head;
boolean flag = false;
while(true) {
if (temp.next == null) break;
if(temp.next.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if(flag) {
System.out.printf("刪除了 %d 節點.\n",heroNode.no);
temp.next = temp.next.next;
} else {
System.out.printf("要刪除的節點 %d 不存在\n",heroNode.no);
}
}
```
感嘆老師的思路就是清楚.. 自己的思維真的差的可以..
## 面試題(新浪、百度、騰訊)
鏈結串列的常見面試題有如下:
1. [求鏈結串列中有效節點的個數](https://hackmd.io/6HZ85fisTpKWrr76yFwkwg#%E6%B1%82%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E4%B8%AD%E6%9C%89%E6%95%88%E7%AF%80%E9%BB%9E%E7%9A%84%E5%80%8B%E6%95%B8)
1. [查找鏈結串列中的倒數第k個結點 【新浪面試題】](https://hackmd.io/6HZ85fisTpKWrr76yFwkwg#%E6%9F%A5%E6%89%BE%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E4%B8%AD%E7%9A%84%E5%80%92%E6%95%B8%E7%AC%ACk%E5%80%8B%E7%B5%90%E9%BB%9E)
1. [鏈結串列的反轉【騰訊面試題，有點難度】](https://hackmd.io/6HZ85fisTpKWrr76yFwkwg#%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E5%8F%8D%E8%BD%89)
1. [從尾到頭列印鏈結串列 【百度，要求 方式1：反向遍歷, 方式2：Stack棧】](https://hackmd.io/6HZ85fisTpKWrr76yFwkwg#%E5%BE%9E%E5%B0%BE%E5%88%B0%E9%A0%AD%E5%88%97%E5%8D%B0%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97)
1. 合併兩個有序的鏈結串列，合併之後的鏈結串列依然有序【課後練習.】
### 求鏈結串列中有效節點的個數
若是有頭節點的鏈結串列，則不統計頭節點。
**個人寫法**
```java=
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.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
singleLinkedList.list();
HeroNode head = new HeroNode(0, "", "");
System.out.println(singleLinkedList.getLength(head));
}
}
class SingleLinkedList {
//..略
public int getLength(HeroNode heroNode) {
HeroNode temp = head.next;
if(temp == null) return 0;
int count = 0;
while(true) {
if(temp == null) break;
temp = temp.next;
count++;
}
return count;
}
}
```
**老師寫法**
我們的頭節點是在`SingleLinkedList`類別中初始化的
那我們在`SingleLinkedList`類別中新增一個`getHead()`方法用於返回 head
```java=
private HeroNode head = new HeroNode(0, "", "");
public HeroNode getHead() {
return head;
}
```
完整寫法：
```java=
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.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
singleLinkedList.list();
System.out.println(getLength(singleLinkedList.getHead())); //獲得節點個數
singleLinkedList.delete(hero4); //刪除一個節點
singleLinkedList.list();
System.out.println(getLength(singleLinkedList.getHead())); //獲得節點個數
}
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;
}
}
class SingleLinkedList {
private HeroNode head = new HeroNode(0, "", "");
public HeroNode getHead() {
return head;
}
//..略
}
```
### 查找鏈結串列中的倒數第k個結點
**思路**
1. 編寫一個方法，接收head節點，同時接收一個index
2. index表示的是倒數第index個節點
3. 先把鏈結串列從頭到尾遍歷，得到鏈結串列的總長度 getLength() => size
4. 得到size後，從鏈結串列第一個開始遍歷 size - index個
5. 如果找到則返回該節點，否則返回null
需配合剛剛第一題的`getLength()` 方法
```java=
//查找倒數第n個節點
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 cur = head.next;
for(int i=0; i< size-index; i++) {
cur = cur.next;
}
return cur;
}
```
```java=
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.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
singleLinkedList.list();
System.out.println("倒數第 2 個節點為\n"+findLastIndexNode(singleLinkedList.getHead(),2));
System.out.println("倒數第 3 個節點為\n"+findLastIndexNode(singleLinkedList.getHead(),3));
System.out.println("倒數第 0 個節點為\n"+findLastIndexNode(singleLinkedList.getHead(),0));
System.out.println("倒數第 6 個節點為\n"+findLastIndexNode(singleLinkedList.getHead(),6));
}
```
### 鏈結串列的反轉
**示意圖**
**思路**
1. 先定義一個節點 `reverseHead = new HeroNode();`
2. 從頭到尾遍歷原來的鏈結串列，每遍歷一個節點就將其取出並放在新的鏈結串列reverseHead 的最前端
3. 原來的鏈結串列的 `head.next = reverseHead.next;`
因為到這部分還沒有提到Stack的部分，如果有Stack基礎的朋友們也可以多嘗試用Stack解決。
```java=
//將單向鏈結串列反轉
public static void reverseList(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;
}
```
```java=
public static void main(String[] args){
reverseList(singleLinkedList.getHead());
singleLinkedList.list();
}
```
### 從尾到頭列印鏈結串列
**思路**
1. 上面的題目要求就是逆序輸出鏈結串列
2. 方法1: 先將鏈結串列進行反轉操作然後遍歷即可，這樣做的問題是會破壞原來鏈結串列的結構，不建議使用。
3. 方法2：可以利用棧(Stack)這個資料結構，將各個節點push到棧中，利用棧的先進後出特點實現逆序輸出效果。
但現在還沒提到棧，先簡單講下原理。
#### 棧(Stack)的基本原理
數據 push 進 Stack 中，新的資料加在舊資料上方
數據 pop出 Stack 中，新的資料先拿走
你可以用堆書本來理解Stack，我一本書一本書堆起來，第一本堆的會最後拿走。
現在我們大概需要了解到這種程度就可以，後面還會細講Stack的部分。
簡單用java實現一下Stack的push和pop
```java=
public class TestStackDemo {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
while(stack.size() > 0) {
System.out.println(stack.pop());
}
}
}
```
output:
```
3
2
1
```
那我們就來使用Stack來逆序輸出鏈結串列。
```java=
//逆序單向鏈結串列
public static void reversePrint(HeroNode head) {
if(head.next == null) return;
//創建一個stack將各個節點push進stack中
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = head.next;
while(cur != null) {
stack.push(cur);
cur = cur.next;
}
//將stack中節點輸出
while(stack.size() > 0) {
System.out.println(stack.pop());
}
}
```
```java=
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.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
singleLinkedList.list();
System.out.println("====逆序輸出鏈結串列====");
reversePrint(singleLinkedList.getHead());
}
```
## 單向鏈結串列的缺點
1.單向鏈結串列查找的方向只能是一個方向，而雙向鏈結串列可以向前或向後查找。
2.單向鏈結串列不能自我刪除，需要靠輔助節點，而雙向鏈結串列則可以自我刪除。
因此下一節我們將來學習雙向鏈結串列。
> 延伸閱讀: [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
Sign in with Wallet
Connect another wallet