基本數(shù)據(jù)結(jié)構(gòu)：鏈表（list）
作者：C小加 更新時(shí)間：2012-7-31
談到鏈表之前，先說(shuō)一下線性表。線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。線性表有兩種存儲(chǔ)方式，一種是順序存儲(chǔ)結(jié)構(gòu)，另一種是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
順序存儲(chǔ)結(jié)構(gòu)就是兩個(gè)相鄰的元素在內(nèi)存中也是相鄰的。這種存儲(chǔ)方式的優(yōu)點(diǎn)是查詢的時(shí)間復(fù)雜度為O(1)，通過(guò)首地址和偏移量就可以直接訪問(wèn)到某元素，關(guān)于查找的適配算法很多，最快可以達(dá)到O(logn)。缺點(diǎn)是插入和刪除的時(shí)間復(fù)雜度最壞能達(dá)到O(n)，如果你在第一個(gè)位置插入一個(gè)元素，你需要把數(shù)組的每一個(gè)元素向后移動(dòng)一位，如果你在第一個(gè)位置刪除一個(gè)元素，你需要把數(shù)組的每一個(gè)元素向前移動(dòng)一位。還有一個(gè)缺點(diǎn)，就是當(dāng)你不確定元素的數(shù)量時(shí)，你開(kāi)的數(shù)組必須保證能夠放下元素最大數(shù)量，遺憾的是如果實(shí)際數(shù)量比最大數(shù)量少很多時(shí)，你開(kāi)的數(shù)組沒(méi)有用到的內(nèi)存就只能浪費(fèi)掉了。
我們常用的數(shù)組就是一種典型的順序存儲(chǔ)結(jié)構(gòu)，如圖1。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是兩個(gè)相鄰的元素在內(nèi)存中可能不是相鄰的，每一個(gè)元素都有一個(gè)指針域，指針域一般是存儲(chǔ)著到下一個(gè)元素的指針。這種存儲(chǔ)方式的優(yōu)點(diǎn)是插入和刪除的時(shí)間復(fù)雜度為O(1)，不會(huì)浪費(fèi)太多內(nèi)存，添加元素的時(shí)候才會(huì)申請(qǐng)內(nèi)存，刪除元素會(huì)釋放內(nèi)存，。缺點(diǎn)是訪問(wèn)的時(shí)間復(fù)雜度最壞為O(n)，關(guān)于查找的算法很少，一般只能遍歷，這樣時(shí)間復(fù)雜度也是線性（O(n)）的了,頻繁的申請(qǐng)和釋放內(nèi)存也會(huì)消耗時(shí)間。
順序表的特性是隨機(jī)讀取，也就是訪問(wèn)一個(gè)元素的時(shí)間復(fù)雜度是O(1)，鏈?zhǔn)奖淼奶匦允遣迦牒蛣h除的時(shí)間復(fù)雜度為O(1)。要根據(jù)實(shí)際情況去選取適合自己的存儲(chǔ)結(jié)構(gòu)。
鏈表就是鏈?zhǔn)酱鎯?chǔ)的線性表。根據(jù)指針域的不同，鏈表分為單向鏈表、雙向鏈表、循環(huán)鏈表等等。
一、 單向鏈表（slist）
鏈表中最簡(jiǎn)單的一種是單向鏈表，每個(gè)元素包含兩個(gè)域，值域和指針域，我們把這樣的元素稱之為節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)的指針域內(nèi)有一個(gè)指針，指向下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值。如圖2就是一個(gè)單向鏈表。
一個(gè)單向鏈表的節(jié)點(diǎn)被分成兩個(gè)部分。第一個(gè)部分保存或者顯示關(guān)于節(jié)點(diǎn)的信息，第二個(gè)部分存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址。單向鏈表只可向一個(gè)方向遍歷。
我寫(xiě)了一個(gè)簡(jiǎn)單的C++版單向鏈表類模板，就用這段代碼講解一下一個(gè)具體的單向鏈表該怎么寫(xiě)（代碼僅供學(xué)習(xí)），當(dāng)然首先你要具備C++基礎(chǔ)知識(shí)和簡(jiǎn)單的模板元編程。
完整代碼
首先我們要寫(xiě)一個(gè)節(jié)點(diǎn)類，鏈表中的每一個(gè)節(jié)點(diǎn)就是一個(gè)節(jié)點(diǎn)類的對(duì)象。如圖3。
代碼如下：
template<class T>
class slistNode
{
public:
slistNode(){next=NULL;}//初始化
T data;//值
slistNode* next;//指向下一個(gè)節(jié)點(diǎn)的指針
};
第二步，寫(xiě)單鏈表類的聲明，包括屬性和方法。
代碼如下：
template<class T>
class myslist
{
private:
unsigned int listlength;
slistNode<T>* node;//臨時(shí)節(jié)點(diǎn)
slistNode<T>* lastnode;//頭結(jié)點(diǎn)
slistNode<T>* headnode;//尾節(jié)點(diǎn)
public:
myslist();//初始化
unsigned int length();//鏈表元素的個(gè)數(shù)
void add(T x);//表尾添加元素
void traversal();//遍歷整個(gè)鏈表并打印
bool isEmpty();//判斷鏈表是否為空
slistNode<T>* find(T x);//查找第一個(gè)值為x的節(jié)點(diǎn),返回節(jié)點(diǎn)的地址,找不到返回NULL
void Delete(T x);//刪除第一個(gè)值為x的節(jié)點(diǎn)
void insert(T x,slistNode<T>* p);//在p節(jié)點(diǎn)后插入值為x的節(jié)點(diǎn)
void insertHead(T x);//在鏈表的頭部插入節(jié)點(diǎn)
};
第三步，寫(xiě)構(gòu)造函數(shù)，初始化鏈表類的屬性。
代碼如下：
template<class T>
myslist<T>::myslist()
{
node=NULL;
lastnode=NULL;
headnode=NULL;
listlength=0;
}
第四步，實(shí)現(xiàn)add()方法。
代碼如下：
template<class T>
void myslist<T>::add(T x)
{
node=new slistNode<T>();//申請(qǐng)一個(gè)新的節(jié)點(diǎn)
node->data=x;//新節(jié)點(diǎn)賦值為x
if(lastnode==NULL)//如果沒(méi)有尾節(jié)點(diǎn)則鏈表為空,node既為頭結(jié)點(diǎn),又是尾節(jié)點(diǎn)
{
headnode=node;
lastnode=node;
}
else//如果鏈表非空
{
lastnode->next=node;//node既為尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
lastnode=node;//node變成了尾節(jié)點(diǎn),把尾節(jié)點(diǎn)賦值為node
}
++listlength;//元素個(gè)數(shù)+1
}
第五步，實(shí)現(xiàn)traversal()函數(shù)，遍歷并輸出節(jié)點(diǎn)信息。
代碼如下：
template<class T>
void myslist<T>::traversal()
{
node=headnode;//用臨時(shí)節(jié)點(diǎn)指向頭結(jié)點(diǎn)
while(node!=NULL)//遍歷鏈表并輸出
{
cout<<node->data<<ends;
node=node->next;
}
cout<<endl;
}
第六步，實(shí)現(xiàn)isEmpty()函數(shù)，判斷鏈表是否為空，返回真為空，假則不空。
代碼如下：
template<class T>
bool myslist<T>::isEmpty()
{
return listlength==0;
}
第七步，實(shí)現(xiàn)find()函數(shù)。
代碼如下：
template<class T>
slistNode<T>* myslist<T>::find(T x)
{
node=headnode;//用臨時(shí)節(jié)點(diǎn)指向頭結(jié)點(diǎn)
while(node!=NULL&&node->data!=x)//遍歷鏈表,遇到值相同的節(jié)點(diǎn)跳出
{
node=node->next;
}
return node;//返回找到的節(jié)點(diǎn)的地址,如果沒(méi)有找到則返回NULL
}
第八步，實(shí)現(xiàn)delete()函數(shù)，刪除第一個(gè)值為x的節(jié)點(diǎn)，如圖4。
代碼如下：
template<class T>
void myslist<T>::Delete(T x)
{
slistNode<T>* temp=headnode;//申請(qǐng)一個(gè)臨時(shí)節(jié)點(diǎn)指向頭節(jié)點(diǎn)
if(temp==NULL) return;//如果頭節(jié)點(diǎn)為空,則該鏈表無(wú)元素,直接返回
if(temp->data==x)//如果頭節(jié)點(diǎn)的值為要?jiǎng)h除的值,則刪除投節(jié)點(diǎn)
{
headnode=temp->next;//把頭節(jié)點(diǎn)指向頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
if(temp->next==NULL) lastnode=NULL;//如果鏈表中只有一個(gè)節(jié)點(diǎn),刪除之后就沒(méi)有節(jié)點(diǎn)了,把尾節(jié)點(diǎn)置為空
delete(temp);//刪除頭節(jié)點(diǎn)
return;
}
while(temp->next!=NULL&&temp->next->data!=x)//遍歷鏈表找到第一個(gè)值與x相等的節(jié)點(diǎn),temp表示這個(gè)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
{
temp=temp->next;
}
if(temp->next==NULL) return;//如果沒(méi)有找到則返回
if(temp->next==lastnode)//如果找到的時(shí)候尾節(jié)點(diǎn)
{
lastnode=temp;//把尾節(jié)點(diǎn)指向他的上一個(gè)節(jié)點(diǎn)
delete(temp->next);//刪除尾節(jié)點(diǎn)
temp->next=NULL;
}
else//如果不是尾節(jié)點(diǎn),如圖4
{
node=temp->next;//用臨時(shí)節(jié)點(diǎn)node指向要?jiǎng)h除的節(jié)點(diǎn)
temp->next=node->next;//要?jiǎng)h除的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)指向要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
delete(node);//刪除節(jié)點(diǎn)
node=NULL;
}
}
第九步，實(shí)現(xiàn)insert()和insertHead()函數(shù)，在p節(jié)點(diǎn)后插入值為x的節(jié)點(diǎn)。如圖5。
代碼如下：
template<class T>
void myslist<T>::insert(T x,slistNode<T>* p)
{
if(p==NULL) return;
node=new slistNode<T>();//申請(qǐng)一個(gè)新的空間
node->data=x;//如圖5
node->next=p->next;
p->next=node;
if(node->next==NULL)//如果node為尾節(jié)點(diǎn)
lastnode=node;
}
template<class T>
void myslist<T>::insertHead(T x)
{
node=new slistNode<T>();
node->data=x;
node->next=headnode;
headnode=node;
}
最終，我們完成一個(gè)簡(jiǎn)單的單向鏈表。此單向鏈表代碼還有很多待完善的地方，以后會(huì)修改代碼并不定時(shí)更新。
二、 雙向鏈表
雙向鏈表的指針域有兩個(gè)指針，每個(gè)數(shù)據(jù)結(jié)點(diǎn)分別指向直接后繼和直接前驅(qū)。單向鏈表只能從表頭開(kāi)始向后遍歷，而雙向鏈表不但可以從前向后遍歷，也可以從后向前遍歷。除了雙向遍歷的優(yōu)點(diǎn)，雙向鏈表的刪除的時(shí)間復(fù)雜度會(huì)降為O（1），因?yàn)橹苯油ㄟ^(guò)目的指針就可以找到前驅(qū)節(jié)點(diǎn)，單向鏈表得從表頭開(kāi)始遍歷尋找前驅(qū)節(jié)點(diǎn)。缺點(diǎn)是每個(gè)節(jié)點(diǎn)多了一個(gè)指針的空間開(kāi)銷。如圖6就是一個(gè)雙向鏈表。
三、 循環(huán)鏈表
循環(huán)鏈表就是讓鏈表的最后一個(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)，這樣就形成了一個(gè)圓環(huán)，可以循環(huán)遍歷。單向循環(huán)鏈表可以單向循環(huán)遍歷，雙向循環(huán)鏈表的頭節(jié)點(diǎn)的指針也要指向最后一個(gè)節(jié)點(diǎn)，這樣的可以雙向循環(huán)遍歷。如圖7就是一個(gè)雙向循環(huán)鏈表。
四、 鏈表相關(guān)問(wèn)題
1、如何判斷一個(gè)單鏈表有環(huán)
2、如何判斷一個(gè)環(huán)的入口點(diǎn)在哪里
3、如何知道環(huán)的長(zhǎng)度
4、如何知道兩個(gè)單鏈表（無(wú)環(huán)）是否相交
5、如果兩個(gè)單鏈表（無(wú)環(huán)）相交，如何知道它們相交的第一個(gè)節(jié)點(diǎn)是什么
6、如何知道兩個(gè)單鏈表（有環(huán)）是否相交
7、如果兩個(gè)單鏈表（有環(huán)）相交，如何知道它們相交的第一個(gè)節(jié)點(diǎn)是什么
答案