【原創】淺談指針（十）鏈表的寫法
前言
最近我又來更新這個系列了，其實感覺指針對於我們還是非常重要的存在。指針之所以是初學者們的「噩夢」，它的難度源於它的靈活性。
這篇文章，我想要來寫一下指針的實際運用，如果指針只是一些考試的考題，那就沒有意義了。最重要的，指針在C語言，乃至C++，都是不可或缺的一部分。
鏈表的簡單回顧
鏈表是一種數據結構。
對於一個鏈表來說，每個結點有兩個域，即數據域和指針域，數據域是用來存放這個鏈表的數字，指針域用來存放下一個結點的地址。特別的，最後一個結點的指針域設為NULL。
這樣，就不需要讓整個鏈表順序存儲了。
對於數據的插入和刪除操作，鏈表只需要新建結點即可：
插入和刪除的時間複雜度是O(1)，不需要移動元素。而對於普通的線性表，需要移動數據，因此時間複雜度為O(n)。
結構體聲明
對於鏈表的結構體，我們可以這樣寫：
typedef struct List{
int data;
List *next;
List(int x){
this->data=x;
next=NULL;
}
};
List *lst;
data是數據域，next是指針域。
其中，List(x)是一個構造函數，這樣在使用new進行結點分配的時候可以簡便書寫。分配的時候就需要這樣寫：
l=new List(x);
這個構造函數做了兩件事：一個是把data進行賦值，一個是把next設為NULL。
補充1：this指針
其中，寫this->data，this是指這個結構體本身，例如調用：
l=new List(x);
此時this就指向l。this是一個特殊的指針。有一種形象的比喻方式：
當你進入一個房子後，你可以看見桌子、椅子、地板等，但是房子你是看不到全貌了。
對於一個類的實例來說，你可以看到它的成員函數、成員變量，但是實例本身呢？
this是一個指針，它時時刻刻指向你這個實例本身。
當然，這裡不寫this也是可以的。這只是寫法問題。
補充2：->運算符
這個運算符，我們一般稱為「箭頭運算符」。
假設我們有現在下面的一個結構體：
struct info{
string name;
int age;
}
如果現在有一個普通變量x，那麼引用其中的age，寫作：x.age
如果現在有一個指針變量p，那麼引用其中的age，要寫作p->age
也就是說，對於一個指針結構體，引用其中的成員需要使用->運算符。
本質上，p->age等同於(*p).age，注意這裡括號雖然麻煩但是不可省略。箭頭運算符只是一種簡便寫法。
在鏈表的最後添加元素
我們知道，如果一個鏈表的當前結點為NULL，那麼它必定是最後的結點。因此，我們可以採用遞歸的寫法，如果鏈表當前節點不為NULL，那麼就下一個結點。
void add(List *&l,int x){
if(l==NULL){
l=new List(x);
return;
}
else add(l->next,x);
}
l=new List(x);，之前說過的構造函數寫法。
add(l->next,x)表示找下一個結點。
補充3：*&是什麼鬼！
我們知道，&是引用傳遞參數。我之前的淺談指針（三）寫過，網頁鏈接
如果懶得在原文找的話，我這裡直接把原文貼出來了：
在這裡，*表示指針，&表示引用傳遞，那麼加在一起就是指針的引用傳遞，雖然聲明看上去很煩，但是理解了也就是這麼回事。
輸出鏈表的所有元素
毫無難度的函數，我直接貼出來了，邏輯和add函數類似。
void write(List *l){
if(l==NULL)return;
else{
printf("%d ",l->data);
write(l->next);
}
}
插入元素
鏈表的靈活之處就是它的插入和刪除函數。
如下圖所示，我們要在2之後插入一個10：
首先，我們需要把10和3連接起來，否則一旦斷掉2和3之間的連接，那麼整個鏈表就直接分離了，無法再找到3的位置。
下一步，就是把2和10連接起來，同時斷開2和3的連接。
這樣就把插入的操作完成了，其實本質是很簡單了。
void insert(int pos,List *&l,int x){
if(pos==1){
List *p=new List(x);
p->next=l->next;
l->next=p;
}
else insert(pos-1,l->next,x);
}
為了找到待插入的位置pos，我們可以採用遞歸的方法，每往後一個結點pos-1，最終當pos=1時就到了想要的位置。
刪除元素
同樣的鏈表，假設刪除其中的3：
首先，先新建一個指針，指向3，否則後續操作過後就無法釋放這塊內存：
第二步，把2連接到4上面去。
最後，釋放這個新建的指針，本質就是釋放3。
代碼還是一樣，注意最終到pos=2就要停止了，這個算法無法刪除首個結點的位置。
void remove(int pos,List *&l){
if(pos==2){
List *p=l->next;
l->next=l->next->next;
delete p;
}
else remove(pos-1,l->next);
}
完整思路
一套完整的鏈表寫下來也是有四五十行代碼的，完整代碼如下：
#include<bits/stdc++.h>
using namespace std;
typedef struct List{
int data;
List *next;
List(int x){
this->data=x;
next=NULL;
}
};
List *lst;
void add(List *&l,int x){
if(l==NULL){
l=new List(x);
return;
}
else add(l->next,x);
}
void write(List *l){
if(l==NULL)return;
else{
printf("%d ",l->data);
write(l->next);
}
}
void insert(int pos,List *&l,int x){
if(pos==1){
List *p=new List(x);
p->next=l->next;
l->next=p;
}
else insert(pos-1,l->next,x);
}
void remove(int pos,List *&l){
if(pos==2){
List *p=l->next;
l->next=l->next->next;
delete p;
}
else remove(pos-1,l->next);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
add(lst,x);
}
while(m--){
int k;
scanf("%d",&k);
if(k==1){//插入操作
int pos,val;
scanf("%d%d",&pos,&val);
insert(pos,lst,val);
write(lst);putchar('\n');
}
else if(k==2){//刪除操作
int pos;
scanf("%d",&pos);
remove(pos,lst);
write(lst);putchar('\n');
}
}
return 0;
}
