🌈個人主頁：聆風吟
🔥系列專欄：算法模板、數(shù)據(jù)結(jié)構(gòu)
🔖少年有夢不應止于心動，更要付諸行動。

---

📋前言

????💬 hello! 各位鐵子們大家好哇，今天作者給大家?guī)淼氖鞘褂檬褂脭?shù)組模擬單鏈表，讓我們一起加油進步。
????📚 系列專欄：本期文章收錄在《算法模板》，大家有興趣可以瀏覽和關注，后面將會有更多精彩內(nèi)容！
????🎉 歡迎大家關注🔍點贊👍收藏??留言📝

---

一. ??使用數(shù)組模擬單鏈表講解

1.1 🔔為什么我們要使用數(shù)組去模擬單鏈表？

????假如你學過數(shù)據(jù)結(jié)構(gòu)，那么你對鏈表的第一反應可能就是：由一系列結(jié)點組成，每個結(jié)點包含兩個域，其中一個域用于存儲數(shù)據(jù)元素，另一個域用于存儲下一個結(jié)點的地址。節(jié)點的表示形式如下：

class Node{
public:int val;Node* next;
};

這種構(gòu)造形式是我們常見的，使用該方法，在創(chuàng)建 一個值為 x 的新結(jié)點的時候，語法如下：

Node* node = new Node();
node->val = x

代碼分析：Node* node = new Node();，中間有一個 new 關鍵字來為新對象分配空間。new 的底層涉及內(nèi)存分配，調(diào)用構(gòu)造函數(shù)，指針轉(zhuǎn)換等多種復雜且費時的操作。由于一秒大概只能 new 一萬次左右。在平時的工程代碼中，不會涉及上萬次的new操作，所以這種使用這種結(jié)構(gòu)創(chuàng)建單鏈表是一種 見代碼知意 的好結(jié)構(gòu)。
????但是在算法比賽中，經(jīng)常碰到在10w級別以上的鏈表操作，如果使用結(jié)構(gòu)體這種方式創(chuàng)建鏈表，是無法在算法規(guī)定時間完成的。因此，在算法比賽這種有嚴格的時間要求的環(huán)境中，不能頻繁使用new操作。所以在這里我們采用數(shù)組去模擬單鏈表。

1.2 🔔用數(shù)組模擬實現(xiàn)單鏈表

1.2.1 👻整體框架說明

初始狀態(tài)：將頭指針head指向空結(jié)點。

插入結(jié)點狀態(tài)：

• 創(chuàng)建數(shù)組val和ne分別存儲某個結(jié)點的值和指向下個結(jié)點的next指針；
• 使用數(shù)組下表進行關聯(lián)，通過數(shù)組ne將整個鏈表鏈接起來；
• 空結(jié)點的下表用 - 1 來表示；

### 1.2.2 👻單鏈表查找和修改 因為是使用數(shù)組模擬出來的鏈表，所以對于查找和修改直接通過數(shù)組下標進行遍歷查找即可，這里就不多敘述。

1.2.3 👻單鏈表插入結(jié)點

1. 頭插：將 x 插入到頭結(jié)點

代碼展示（建議結(jié)合圖示看注釋）：

//將x插到頭結(jié)點
//idx 存儲當前已經(jīng)用到了哪個點,即記錄當前下標位置
void add_to_head(int x)
{val[idx] = x;//記錄要插入結(jié)點的數(shù)據(jù)ne[idx] = head;//將待插結(jié)點指向頭結(jié)點head = idx;//斷開頭指針head指向的頭結(jié)點的箭頭，改為指向待插入結(jié)點idx++;//下標向后移一位，為下一次插入元素做準備。
}

2. 任意位置插入：將 x 插入到下標是k的結(jié)點后面

代碼展示（建議結(jié)合圖示看注釋）：

//將x插到下標是k的結(jié)點后面
//idx 存儲當前已經(jīng)用到了哪個點,即記錄當前下標位置
void add(int k, int x)
{val[idx] = x;//記錄要插入結(jié)點的數(shù)據(jù)ne[idx] = ne[k];//將待插結(jié)點指向下標為k結(jié)點的下個結(jié)點ne[k] = idx;//斷開下標為k到k+1結(jié)點的箭頭，將下標為k的結(jié)點改為指向待插入結(jié)點idx++;//下標向后移一位，為下一次插入元素做準備。
}

1.2.4 👻單鏈表刪除結(jié)點

將下標為 k 的結(jié)點 后面的結(jié)點刪掉

代碼展示（建議結(jié)合圖示看注釋）：

//將下標是k的點后面的點刪掉
void remove(int k)
{ne[k] = ne[ne[k]];//讓k指向的改為指向下下個結(jié)點，那中間的那個結(jié)點就被擠掉了。
}

1.3 🌟模板提取(重點)🌟

模板代碼

// head 表示頭結(jié)點的下標
// val[i] 表示結(jié)點i的值
// ne[i] 表示結(jié)點i的next指針是多少
// idx 存儲當前已經(jīng)用到了哪個點，即記錄當前下標位置
int head, val[N], ne[N], idx;//初始化
void init()
{head = -1;//將頭指針head指向空結(jié)點。idx = 0;//下標置為0
}//將 x 插入到頭結(jié)點
void add_to_head(int x)
{val[idx] = x; ne[idx] = head;head = idx;idx++;
}//將 x 插入到下標是k的結(jié)點后面
void add(int k, int x)
{val[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx++;
}//將下標是k的點后面的點刪掉
void remove(int k)
{ne[k] = ne[ne[k]];
}

---

二. ??題目練習

? 在線OJ鏈接,可以轉(zhuǎn)至此處自行練習 ?

2.1 題目

2.2 輸入樣例

3
H ?9
I ??1 ?1
D??1

2.3 輸出樣例

9

2.4 c++代碼

#include <iostream>using namespace std;const int N = 100010;
// head 表示頭結(jié)點的下標
// val[i] 表示結(jié)點i的值
// ne[i] 表示結(jié)點i的next指針是多少
// idx 存儲當前已經(jīng)用到了哪個點，即記錄當前下標位置
int head, val[N], ne[N], idx;//初始化
void init()
{head = -1;idx = 0;
}//將 x 插入到頭結(jié)點
void add_to_head(int x)
{val[idx] = x; ne[idx] = head;head = idx;idx++;
}//將 x 插入到下標是k的結(jié)點后面
void add(int k, int x)
{val[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx++;
}//將下標是k的點后面的點刪掉
void remove(int k)
{ne[k] = ne[ne[k]];
}int main()
{int m;cin >> m;init();//切記：初始化while(m--){int k, x;char op;cin >> op;//判斷執(zhí)行哪種操作if(op == 'H'){//執(zhí)行頭插操作cin >> x;add_to_head(x);}else if(op == 'D'){//執(zhí)行刪除操作cin >> k;if(k == 0) head = ne[head];//刪除頭節(jié)點remove(k - 1);//注意刪除第k個輸入后面的數(shù)，那函數(shù)里放的是下標，k要減去1}else{//執(zhí)行指定位置插入操作cin >> k >> x;add(k - 1, x);}}for(int i = head; i != -1; i = ne[i]) cout << val[i] << " ";cout << endl;return 0;
}

---

📝結(jié)語

???? 今天的干貨分享到這里就結(jié)束啦！如果覺得文章還可以的話，希望能給個三連支持一下，聆風吟的主頁還有很多有趣的文章，歡迎小伙伴們前去點評，您的支持就是作者前進的最大動力！