鏈表的概念、實踐和面試題
一、鏈表簡介
鏈表是有序的列表，在內存中的存儲方式如圖：
- 鏈表是以節點的方式來存儲，是鏈式存儲；
- 每個節點包含data域，next指針（指向下一個節點）；
- 鏈表的節點不一定連續存儲，是離散的狀態；
- 鏈表分為帶頭節點的鏈表和沒有頭結點的鏈表，帶頭結點的邏輯結構示意圖如下：
二、單鏈表的應用實例
2.1 單鏈表的基礎方法的實現
使用帶頭結點的單向鏈表實現，完成對水滸英雄的CRUD。
- 普通新增方法
此方法添加英雄時，直接添加到鏈表尾部。
- 先創建一個head節點，不記錄具體信息，作用就是表示單鏈表的頭結點；
- 此後每添加一個節點，就直接添加在鏈表的最後
- 示意圖：
- 按序新增方法
此方法在添加英雄時，根據英雄的排名將英雄添加到指定的位置。
- 首先找到新節點應該添加的位置，通過輔助指針來遍歷找到位置；
- 將新節點的next設置為指針指向節點的next節點；
- 將指針指向的節點的next設置新節點；（2、3步驟順序不能互換）
- 不能添加相同排名的英雄；
- 示意圖：
- 修改節點方法
- 先通過遍歷找到對應節點；
- 修改數據。
- 刪除節點方法
- 找到需要刪除的del節點；
- 將del節點的前一個節點的next指向del節點的next節點；
- 示意圖：
- 代碼實現
GitHub：//github.com/goSilver/daydayup/blob/master/datastructure/src/hanshunping/chapter04/SingleLinkedListDemo.java
2.2 單鏈表的相關面試題
- 求單鏈表中的有效節點的個數
思路：
遍歷單鏈表，如果有頭結點忽略頭結點
代碼：
/**
* 獲取鏈表的長度
*
* @param head 鏈表頭結點
* @return 長度
*/
int getLength(HeroNode head) {
int length = 0;
while (Objects.nonNull(head.getNext())) {
length++;
head = head.getNext();
}
return length;
}
- 查找單鏈表中的倒數第k個節點
思路：
- 先求得鏈表的長度length；
- 用length – k即可算出倒數第k個節點所處位置；
- 從鏈表頭結點遍歷length – k次即可。
代碼：
/**
* 尋找倒數第k個節點
*
* @param singleLinkedList 鏈表
* @param k k值
* @return 倒數第k個節點
*/
HeroNode findTheKthFromBottom(SingleLinkedList singleLinkedList, int k) {
int length = getLength(singleLinkedList.head);
int index = length + 1 - k;
HeroNode temp = singleLinkedList.head;
while (Objects.nonNull(singleLinkedList.head.getNext()) && index > 0) {
temp = temp.getNext();
index--;
}
return temp;
}
- 反轉鏈表
- 定義一個新的頭結點newHead；
- 遍歷原來的鏈表，每遍歷一個節點，就將這個節點放到newHead的next即可；
- 打印時以newHead為頭結點打印。
示意圖：
代碼：
/**
* 反轉鏈表
* 思路：
* 定義一個新的頭結點newHead，遍歷鏈表，依次將遍歷的節點取出放到newHead的後面即可
*
* @param oldHead 鏈表的舊頭結點
*/
void reverse(HeroNode oldHead) {
// 定義一個新的頭結點
HeroNode newHead = new HeroNode(0L, "", "");
// 定義一個臨時節點，記錄即將遍歷的下一個節點
HeroNode next;
// 跳過頭節點
HeroNode current = oldHead.getNext();
while (Objects.nonNull(current)) {
// 記錄即將遍歷的下一個節點
next = current.getNext();
// 將newHead的下一個節點設置為當前節點的next
current.setNext(newHead.getNext());
// 將newHead的next設置為當前節點
newHead.setNext(current);
// 恢復遍歷指針
current = next;
}
// 修改鏈表頭結點
head = newHead;
}
- 從尾到頭打印單鏈表
思路：
方式1：將單鏈表先進行反轉操作，然後再遍歷打印即可，缺點是會破壞原來的單鏈表的存儲結構；
方式2：可以利用棧數據結構先進後出的特性，從頭到尾遍歷時將節點依次壓入棧中，打印時依次從棧中pop即可。
代碼：
/**
* 逆向打印鏈表
* 思路：
* 1、先反轉鏈表，再打印鏈表，缺點是會破壞原鏈表的結構
* 2、利用棧數據結構先進後出的特性來輔助實現
* 這裡用棧來實現
*/
void reversePrint() {
Stack<HeroNode> nodeStack = new Stack<>();
HeroNode current = head.getNext();
while (Objects.nonNull(current)) {
nodeStack.push(current);
current = current.getNext();
}
while (!nodeStack.isEmpty()) {
System.out.println(nodeStack.pop());
}
}
