Java玩轉《啊哈算法》之模擬鏈表

人應該支配習慣，而絕不是讓習慣支配人。一個人要是不能改掉壞習慣，那么他就一文不值。

緣

各位小伙伴們好呀！本人最近看了下《啊哈算法》，寫的確實不錯。

但稍顯遺憾的是，書籍示例代碼是c語言，而不是本人常用的Java。

那就彌補遺憾，說干就干，把這本書的示例語言用java寫一遍，順帶附上一些自己的理解！

今天這篇博客講的是如何用數組來模擬鏈表。
在這里插入圖片描述

來不及買紙質書但又想盡快感受算法魅力的童鞋也甭擔心，電子版的下載鏈接已經放到下方了，可盡情下載。

鏈接：https://pan.baidu.com/s/1imxiElcCorw2F-HJEnB-PA?pwd=jmgs
提取碼：jmgs

代碼地址

本文代碼已開源：

git clone https://gitee.com/guqueyue/my-blog-demo.git

請切換到gitee分支，

然后查看aHaAlgorithm模塊下的src/main/java/com/guqueyue/aHaAlgorithm/chapter_2_StackAndChainTable即可！

模擬鏈表

在往期的博客中，我們用數組模擬了隊列、棧，并且說了用鏈表也可以模擬隊列、棧。

于是乎，我們還介紹了鏈表，但是鏈表指來指去的難免讓人奇奇怪怪、暈頭轉向。

Java玩轉《啊哈算法》解密QQ號之隊列
Java玩轉《啊哈算法》解密回文之棧
Java玩轉《啊哈算法》之鏈表

那么，這期博客，我們來講一下如何用數組來模擬鏈表。

數組可以模擬隊列、棧，鏈表也可以模擬隊列、棧，數組也能模擬鏈表？沒想到吧。

創建

那么，要怎么用數組來模擬鏈表呢？我們需要準備兩個數組，一個數組存元素，一個數組用來存元素對應的下一個元素的位置。
在這里插入圖片描述
如上圖所示，我們data數組用于存放元素內容，right數組用以存放相同索引處對應data數組的下一個元素的索引。

如圖我們頭節點的元素為data[1]也就是2，下一個元素為data[right[1]]也就是3。

當然，我們這里可以做一些小小的改動：

為了不浪費空間，我們的存放數組的索引從0開始而不是從1開始。
鏈表尾節點的下一個位置的索引，我們用-1表示，而不是0。

首先，我們聲明一下需要使用的兩個數組、鏈表的長度以便于錄入數據以及控制臺輸入的對象：

   // 用于控制臺輸入private static Scanner scanner = new Scanner(System.in);private static int[] data = new int[101]; // 元素數組private static int[] right = new int[101]; // 索引數組private static int n = 0; // 鏈表長度

然后，我們就可以愉快的編寫創建鏈表的方法了：

   /*** @Description 創建鏈表* @return void**/private static void createChainTable() {System.out.print("請輸入數字個數： ");n = scanner.nextInt();System.out.printf("請輸入%d個數，中間用空格隔開，輸入完回車： ", n);for (int i = 0; i < n; i++) {data[i] = scanner.nextInt();}// 初始化right數組for (int i = 0; i < n; i++) {right[i] = i == n-1 ? -1 : i+1;}}

遍歷打印

有了創建鏈表的方法，當然要有一個打印的方法，不然怎么驗證：

  /*** @Description 打印鏈表* @return void**/private static void printChainTable() {// 輸出int t = 0;System.out.print("鏈表為：" + data[t]);while(right[t] != -1) {t = right[t]; // 獲取下一個元素的索引System.out.print("->" + data[t]);}System.out.println();}

ok了，下面讓我們來驗證一下：

package com.guqueyue.aHaAlgorithm.chapter_2_StackAndChainTable;import java.util.Scanner;/*** @Author: guqueyue* @Description: 用數組模擬鏈表* @Date: 2024/1/15**/
public class ChainTableTest2 {// 用于控制臺輸入private static Scanner scanner = new Scanner(System.in);private static int[] data = new int[101]; // 元素數組private static int[] right = new int[101]; // 索引數組private static int n = 0; // 鏈表長度public static void main(String[] args) {// 創建鏈表createChainTable();// 打印鏈表printChainTable();}/*** @Description 打印鏈表* @return void**/private static void printChainTable() {// 輸出int t = 0;System.out.print("鏈表為：" + data[t]);while(right[t] != -1) {t = right[t]; // 獲取下一個元素的索引System.out.print("->" + data[t]);}System.out.println();}/*** @Description 創建鏈表* @return void**/private static void createChainTable() {System.out.print("請輸入數字個數： ");n = scanner.nextInt();System.out.printf("請輸入%d個數，中間用空格隔開，輸入完回車： ", n);for (int i = 0; i < n; i++) {data[i] = scanner.nextInt();}// 初始化right數組for (int i = 0; i < n; i++) {right[i] = i == n-1 ? -1 : i+1;}}
}

運行代碼，控制臺輸入，可得：
在這里插入圖片描述

插入

在這里插入圖片描述

同樣的，按照書上的邏輯，我們來寫一個往鏈表中插入元素的方法：

   /*** @Description 插入鏈表* @return void**/private static void insertChainTable() {// 插入一個數int len = n;System.out.print("請輸入插入的數：");data[len] = scanner.nextInt();// 按照鏈表順序遍歷 data 數組，找到比 num 大的數int t = 0;while (t != -1) {if (data[right[t]] > data[len]) { // 如果當前節點的下一個節點大于插入數，則插入right[len] = right[t]; // 插入的節點 指向當前節點的下一個節點right[t] = len; // 當前節點 指向插入的節點break;}t = right[t];}}

我們來驗證一下(完整代碼已開源，在本博客最后也可查看)：

   public static void main(String[] args) {// 創建鏈表createChainTable();// 打印鏈表printChainTable();// 往鏈表中插入數據insertChainTable();// 打印鏈表printChainTable();}

運行，得：

在這里插入圖片描述
看起來好像沒啥問題，但是同上期博客一樣，存在著兩個問題：

如果插入的節點值大小小于頭節點，該節點會被插入到頭節點后面，違背了從小到大的順序。
如果插入的節點值大于等于尾結點，則該節點不會被插入，甚至于直接報錯！

如：
在這里插入圖片描述
又比如：

在這里插入圖片描述

插入優化

因此，我們來把插入方法優化一下，增加插入頭節點和尾節點的邏輯：

	/*** @Description 按照從小到大的順序插入鏈表* @return void**/private static void insertChainTable2() {// 插入一個數int len = n;System.out.print("請輸入插入的數：");data[len] = scanner.nextInt();// 如果新插入的節點比 頭節點 小，則插入到鏈表頭部if (data[len] < data[0]) {// 頭節點和尾節點互換int temp = data[0]; data[0] = data[len]; data[len] = temp;right[len] = right[0]; // 保持舊頭節點原有的連接關系不變right[0] = len; // 將新的頭節點指向舊的節點}else {// 按照鏈表順序遍歷 data 數組，找到比 num 大的數int t = 0;while (right[t] != -1) {if (data[right[t]] > data[len]) { // 如果當前節點的下一個節點大于插入數，則插入right[len] = right[t]; // 插入的節點 指向當前節點的下一個節點right[t] = len; // 當前節點 指向插入的節點break;}t = right[t];}// 插入的數如果比鏈表的最后一個節點大，則插入到鏈表尾部if (right[t] == -1) {right[n-1] = len;right[len] = -1;}}}

改動代碼，來驗證一下吧：

public static void main(String[] args) {// 創建鏈表createChainTable();// 打印鏈表printChainTable();// 往鏈表中插入數據
//        insertChainTable();insertChainTable2();// 打印鏈表printChainTable();
}

運行代碼，分別驗證，插入中間節點：

在這里插入圖片描述
頭節點：

尾節點：

很是完美！！！

完整代碼

package com.guqueyue.aHaAlgorithm.chapter_2_StackAndChainTable;import java.util.Scanner;/*** @Author: guqueyue* @Description: 用數組模擬鏈表* @Date: 2024/1/15**/
public class ChainTableTest2 {// 用于控制臺輸入private static Scanner scanner = new Scanner(System.in);private static int[] data = new int[101]; // 元素數組private static int[] right = new int[101]; // 索引數組private static int n = 0; // 鏈表長度public static void main(String[] args) {// 創建鏈表createChainTable();// 打印鏈表printChainTable();// 往鏈表中插入數據
//        insertChainTable();insertChainTable2();// 打印鏈表printChainTable();}/*** @Description 打印鏈表* @return void**/private static void printChainTable() {// 輸出int t = 0;System.out.print("鏈表為：" + data[t]);while(right[t] != -1) {t = right[t]; // 獲取下一個元素的索引System.out.print("->" + data[t]);}System.out.println();}/*** @Description 插入鏈表* @return void**/private static void insertChainTable() {// 插入一個數int len = n;System.out.print("請輸入插入的數：");data[len] = scanner.nextInt();// 按照鏈表順序遍歷 data 數組，找到比 num 大的數int t = 0;while (t != -1) {if (data[right[t]] > data[len]) { // 如果當前節點的下一個節點大于插入數，則插入right[len] = right[t]; // 插入的節點 指向當前節點的下一個節點right[t] = len; // 當前節點 指向插入的節點break;}t = right[t];}}/*** @Description 按照從小到大的順序插入鏈表* @return void**/private static void insertChainTable2() {// 插入一個數int len = n;System.out.print("請輸入插入的數：");data[len] = scanner.nextInt();// 如果新插入的節點比 頭節點 小，則插入到鏈表頭部if (data[len] < data[0]) {// 頭節點和尾節點互換int temp = data[0]; data[0] = data[len]; data[len] = temp;right[len] = right[0]; // 保持舊頭節點原有的連接關系不變right[0] = len; // 將新的頭節點指向舊的節點}else {// 按照鏈表順序遍歷 data 數組，找到比 num 大的數int t = 0;while (right[t] != -1) {if (data[right[t]] > data[len]) { // 如果當前節點的下一個節點大于插入數，則插入right[len] = right[t]; // 插入的節點 指向當前節點的下一個節點right[t] = len; // 當前節點 指向插入的節點break;}t = right[t];}// 插入的數如果比鏈表的最后一個節點大，則插入到鏈表尾部if (right[t] == -1) {right[n-1] = len;right[len] = -1;}}}/*** @Description 創建鏈表* @return void**/private static void createChainTable() {System.out.print("請輸入數字個數： ");n = scanner.nextInt();System.out.printf("請輸入%d個數，中間用空格隔開，輸入完回車： ", n);for (int i = 0; i < n; i++) {data[i] = scanner.nextInt();}// 初始化right數組for (int i = 0; i < n; i++) {right[i] = i == n-1 ? -1 : i+1;}}
}