數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn) 2.1：鏈表（C++版）

• 1. 概念及基本框架

• 2. 基本操作程序?qū)崿F(xiàn)

• 2.1 增加操作

• 2.2 刪除操作

• 2.3 修改操作

• 2.4 查找操作

• 2.5 其他操作

• 3. 算法復(fù)雜度分析

• 3.1 增加操作

• 3.2 刪除操作

• 3.3 修改操作

• 3.4 查找操作

• 4. 完整代碼

1. 概念及基本框架

鏈表?是一種?線性結(jié)構(gòu)?，而且存儲(chǔ)上屬于?鏈?zhǔn)酱鎯?chǔ)（即內(nèi)存的物理空間是不連續(xù)的），是線性表的一種。鏈表結(jié)構(gòu)如下圖所示：

下面以一個(gè)我實(shí)現(xiàn)的一個(gè)簡(jiǎn)單的鏈表類來(lái)進(jìn)一步理解鏈表。

首先設(shè)計(jì)一個(gè)?結(jié)點(diǎn)類?，這個(gè)結(jié)點(diǎn)類包含?數(shù)據(jù)?和?指向下一個(gè)結(jié)點(diǎn)的指針?。結(jié)點(diǎn)類的構(gòu)造函數(shù)可以直接對(duì)結(jié)點(diǎn)賦值，然后利用結(jié)點(diǎn)類對(duì)象來(lái)創(chuàng)建一個(gè)鏈表。鏈表類的設(shè)計(jì)如下：

這里為了避免重復(fù)設(shè)計(jì)就可以兼容更多數(shù)據(jù)類型，引入了?泛型?，即?模板?的概念。（模板的關(guān)鍵字是?class?或?typename）

這里的?m_size?表示?鏈表長(zhǎng)度?。為了保護(hù)數(shù)據(jù)，這個(gè)變量以及?結(jié)點(diǎn)數(shù)據(jù)?都設(shè)置為?private?。
與動(dòng)態(tài)數(shù)組不同，動(dòng)態(tài)數(shù)組的“動(dòng)態(tài)”含義是可以自動(dòng)擴(kuò)容（縮容），但實(shí)質(zhì)還是靜態(tài)的，而鏈表則實(shí)現(xiàn)了真正意義上的動(dòng)態(tài)。因?yàn)橹挥行枰粋€(gè)結(jié)點(diǎn)，才會(huì)添加一個(gè)結(jié)點(diǎn)，不需要就會(huì)刪除。在這里，為了下面程序代碼編寫方便、統(tǒng)一，引入了?虛擬頭結(jié)點(diǎn)（也稱?哨兵結(jié)點(diǎn)?）的概念。這個(gè)結(jié)點(diǎn)本身不存放數(shù)據(jù)，用戶也不知道它的存在。
實(shí)現(xiàn)了前面的程序之后，接下來(lái)就是一個(gè)鏈表的增、刪、改、查以及一些其他基本操作，接下來(lái)利用代碼去實(shí)現(xiàn)。

2. 基本操作程序?qū)崿F(xiàn)

2.1 增加操作

首先，在類體內(nèi)進(jìn)行增加操作函數(shù)的原型說(shuō)明。這里包括三個(gè)函數(shù)：
add（添加到任意位置）
addFirst（添加到頭部）
addLast（添加到尾部）
然后分別去實(shí)現(xiàn)它們。

由于這些函數(shù)在類體外，所以每個(gè)函數(shù)頭部必須添加一行代碼：

表示該函數(shù)使用模板，下面同理。

如果不使用虛擬頭結(jié)點(diǎn)，代碼編寫就要區(qū)分第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)，從這里可以看出引入虛擬頭結(jié)點(diǎn)的好處，統(tǒng)一了代碼編寫形式，下面的同理。

2.2 刪除操作

同理，在類體內(nèi)進(jìn)行刪除函數(shù)的原型說(shuō)明。這里包括四個(gè)函數(shù)：
remove（刪除任意位置元素）：返回刪除元素的值。
removeFirst（刪除頭部元素）：返回刪除元素的值。
removeLast（刪除尾部元素）：返回刪除元素的值。
removeElement（刪除特定元素）：這里刪除的是第一個(gè)這樣的元素，如果想把這樣的元素都刪掉，可以寫一個(gè)新的函數(shù)來(lái)實(shí)現(xiàn)。
然后分別去實(shí)現(xiàn)它們。

這里刪除操作的“刪除位置非法”后面返回的?NULL?也可以用?throw?拋異常來(lái)實(shí)現(xiàn)，這里只是為了方便。

2.3 修改操作

修改操作只有一個(gè)函數(shù)
set（修改指定位置的值）
同理，在類體內(nèi)進(jìn)行修改函數(shù)的原型說(shuō)明，然后在類體外實(shí)現(xiàn)。

2.4 查找操作

查找函數(shù)有四個(gè)：
get（返回特定位置元素）
getFirst（返回第一個(gè)元素）
getLast（返回最后一個(gè)元素）
contains（返回是否包含特定元素）
這里并沒(méi)有實(shí)現(xiàn)?find?函數(shù)，因?yàn)榧词公@得了元素位置索引，也不能像數(shù)組一樣方便的再次通過(guò)位置索引獲得數(shù)據(jù)，依然需要遍歷鏈表來(lái)獲得數(shù)據(jù)。
分別對(duì)它們進(jìn)行實(shí)現(xiàn)。

同理，這里?get?函數(shù)的“訪問(wèn)位置非法”后面返回的?NULL?也可以用?throw?拋異常來(lái)實(shí)現(xiàn)，這里只是為了方便。

2.5 其他操作

鏈表還有一些其他的操作，這些函數(shù)我在類體內(nèi)進(jìn)行了實(shí)現(xiàn)。
包括?鏈表長(zhǎng)度?的查詢，還有?鏈表的打印?等操作。

3. 算法復(fù)雜度分析

3.1 增加操作

這里的時(shí)間復(fù)雜度與數(shù)組相反，原因在于，引起數(shù)組時(shí)間復(fù)雜度增加的是元素的移動(dòng)，而引起鏈表時(shí)間復(fù)雜度增加的是元素的遍歷。

3.2 刪除操作

同理，刪除操作的時(shí)間復(fù)雜度與數(shù)組也相反。

3.3 修改操作

3.4 查找操作

總體情況：

因?yàn)殒湵硇枰闅v，所以操作的復(fù)雜度都是?O(n)?級(jí)別的，但是，如果只針對(duì)頭結(jié)點(diǎn)操作，那么操作時(shí)間復(fù)雜度就會(huì)變成?O(1)?級(jí)別。

4. 完整代碼

程序完整代碼（這里使用了頭文件的形式來(lái)實(shí)現(xiàn)類）如下：