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

---

📋前言

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

---

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

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

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

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

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

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

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

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

1.2.1 👻整體框架說明

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

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

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

### 1.2.2 👻單鏈表查找和修改 因?yàn)槭鞘褂脭?shù)組模擬出來的鏈表，所以對(duì)于查找和修改直接通過數(shù)組下標(biāo)進(jìn)行遍歷查找即可，這里就不多敘述。

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

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

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

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

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

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

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

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

將下標(biāo)為 k 的結(jié)點(diǎn) 后面的結(jié)點(diǎn)刪掉

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

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

1.3 🌟模板提取(重點(diǎn))🌟

模板代碼

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

---

二. ??題目練習(xí)

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

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é)點(diǎn)的下標(biāo)
// val[i] 表示結(jié)點(diǎn)i的值
// ne[i] 表示結(jié)點(diǎn)i的next指針是多少
// idx 存儲(chǔ)當(dāng)前已經(jīng)用到了哪個(gè)點(diǎn)，即記錄當(dāng)前下標(biāo)位置
int head, val[N], ne[N], idx;//初始化
void init()
{head = -1;idx = 0;
}//將 x 插入到頭結(jié)點(diǎn)
void add_to_head(int x)
{val[idx] = x; ne[idx] = head;head = idx;idx++;
}//將 x 插入到下標(biāo)是k的結(jié)點(diǎn)后面
void add(int k, int x)
{val[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx++;
}//將下標(biāo)是k的點(diǎn)后面的點(diǎn)刪掉
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é)點(diǎn)remove(k - 1);//注意刪除第k個(gè)輸入后面的數(shù)，那函數(shù)里放的是下標(biāo)，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é)束啦！如果覺得文章還可以的話，希望能給個(gè)三連支持一下，聆風(fēng)吟的主頁還有很多有趣的文章，歡迎小伙伴們前去點(diǎn)評(píng)，您的支持就是作者前進(jìn)的最大動(dòng)力！