數組模擬單鏈表你會了嗎？
鏈表
實現鏈表的方式
struct Node
{
int val;
Node *next;
};// 不講——競賽不常用
每次創建一個新的鏈表的時候，就會調用一次new函數來創建新的節點（動態創建鏈表），這個操作是非常慢的
單鏈表：演算法題中單鏈表用的最多的是鄰接表（n個鏈表）。應用：存儲樹和圖
雙鏈表：優化某些問題
模擬單鏈表
1.使用數組來模擬單鏈表
// head 表示頭節點的下標
// e[i] 表示節點i的值
// ne[i] 表示節點i的next指針（下一個節點的位置）是多少
// idx 存儲當前已經用到的節點（當前已經用到哪個節點了）
int head, e[N], ne[N], idx;
2.初始化單鏈表
初始化：默認-1是代表空節點 head 初始值為-1，idx 初始值為0;
//初始化
void init()
{
head = -1;
idx = 0;
}
3.插入操作（頭插法）
- 創建這個節點的值（e[idx] = x）
- head的賦值給當前節點next[i]指針（ne[idx] = head）
- 讓head重新指向頭節點（head = idx）
- 將idx後移（idx++）為下次插入操作做好準備
//將x插到頭節點（用的最多！）
void add_to_head(int x)
{
e[idx] = x;// 將插入節點的value值存下
ne[idx] = head;// 操作1：將新插入節點的指針指向後一個節點（這裡的後一個節點說的就是頭節點！）
head = idx;// 操作2：更新頭節點的指針（head為指向第一個節點的指針（第一個節點的下標！））
idx++; // 新節點插入之後(節點被使用之後)idx++後移（為下一次插入做準備）
}
4.在下標為k的節點後插入x
- 創建這個節點的值(e[idx]=val)
- head的值賦給當前新節點next[i]指針(ne[idx]=ne[k])
- 將下標為k的節點指向當前節點(ne[k]=idx)
- 將idx向後移動(idx++)
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k]; //02 :新插入節點的指針指向k位置節點的後一個節點
ne[k] = idx; // 03:k位置的節點的指針指向新插入的節點
idx++;
}
5.刪除下標為k的節點的後一個節點
// 將下標是k的點後面的點刪掉
void remove(int k)
{
ne[k] = ne[ne[k]];
}
6.刪除頭節點
head = ne[head];
7.例題
實現一個單鏈表，鏈表初始為空，支援三種操作：
- 向鏈表頭插入一個數；
- 刪除第 k 個插入的數後面的數；
- 在第 k 個插入的數後插入一個數。
現在要對該鏈表進行 M 次操作，進行完所有操作後，從頭到尾輸出整個鏈表。
注意:題目中第 k 個插入的數並不是指當前鏈表的第 k 個數。例如操作過程中一共插入了 n 個數，則按照插入的時間順序，這 n 個數依次為：第 1 個插入的數，第 2 個插入的數，…第 n 個插入的數。
輸入格式
第一行包含整數 M，表示操作次數。
接下來 M 行，每行包含一個操作命令，操作命令可能為以下幾種：
H x，表示向鏈表頭插入一個數 xx。D k，表示刪除第 k 個插入的數後面的數（當 k 為 0 時，表示刪除頭結點）。I k x，表示在第 k 個插入的數後面插入一個數 x（此操作中 k 均大於 0）。輸出格式
共一行，將整個鏈表從頭到尾輸出。
數據範圍
1≤M≤100000
所有操作保證合法。輸入樣例：
10 H 9 I 1 1 D 1 D 0 H 6 I 3 6 I 4 5 I 4 5 I 3 4 D 6輸出樣例：
6 4 6 5
【參考程式碼】
#include<iostream>
using namespace std;
const int N = 100000+10;
int e[N], ne[N], idx, head;
//初始化單鏈表
void init()
{
head = -1;
idx = 0;
}
// 向表頭插入數據
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
// 在下標為k的節點後插入x
void add(int k, int x)
{
e[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 opt;
cin>>opt;
if(opt == 'H')
{
cin>>x;
add_to_head(x); // 頭插
}
else if(opt == 'D')
{
cin>>k;
if(k == 0) head = ne[head];// 當 k 為 0 時，表示刪除頭結點
remove(k - 1); // 刪除第 k 個插入的數後面的數(第k個對應下標：k - 1)
}
else if(opt == 'I')
{
cin>>k>>x;
add(k - 1, x); // 在第 k 個插入的數後面插入一個數 x
}
}
// 遍歷單鏈表 i = ne[i]使得i往後走(ne[i]是當前節點的下一個節點的位置)
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
總結
一開始在頭插法那裡卡了好久，其主要原因還是對
head, e[N], ne[N], idx;的含義沒有理解透，從而導致不理解具體操作的程式碼是怎麼得來的，通過幾次手動模擬畫圖之後就能更好的理解啦！
註：如果文章有任何錯誤或不足，請各位大佬盡情指出，評論留言留下您寶貴的建議！如果這篇文章對你有些許幫助，希望可愛親切的您點個贊推薦一手，非常感謝啦
