C/C++編程筆記：鏈接列表（鏈表）及其遍歷，今天就教你

2020-12-09 21:30 作者:C語言編程__Plus 0人讀過 | 我要投稿

像數(shù)組一樣，鏈表是線性數(shù)據(jù)結(jié)構(gòu)。與數(shù)組不同，鏈接列表元素不存儲(chǔ)在連續(xù)的位置；元素使用指針鏈接。

為什么要鏈接列表？

數(shù)組可用于存儲(chǔ)相似類型的線性數(shù)據(jù)，但是數(shù)組具有以下限制。

1）數(shù)組的大小是固定的：因此，我們必須提前知道元素?cái)?shù)量的上限。而且，通常，所分配的存儲(chǔ)器與用途無關(guān)而等于上限。

2）在元素?cái)?shù)組中插入新元素非常昂貴，因?yàn)楸仨殲樾略貏?chuàng)建空間，并且為創(chuàng)建房間而必須移動(dòng)現(xiàn)有元素。

例如，在系統(tǒng)中，如果我們?cè)跀?shù)組id []中維護(hù)ID的排序列表。

id [] = [1000，1010，1050，2000，2040]。

如果要插入新的ID 1005，則要保持排序順序，我們必須將所有元素都移到1000（不包括1000）之后。

除非使用某些特殊技術(shù)，否則刪除數(shù)組也很昂貴。例如，要?jiǎng)h除id []中的1010，必須移動(dòng)1010之后的所有內(nèi)容。

相對(duì)于陣列的優(yōu)勢(shì)

1）動(dòng)態(tài)大小

2）易于插入/刪除

缺點(diǎn)：

1）不允許隨機(jī)訪問。我們必須從第一個(gè)節(jié)點(diǎn)開始順序訪問元素。因此，我們無法使用默認(rèn)實(shí)現(xiàn)對(duì)鏈接列表進(jìn)行有效的二進(jìn)制搜索。

2）列表的每個(gè)元素都需要用于指針的額外存儲(chǔ)空間。

3）不適合緩存。由于數(shù)組元素是連續(xù)的位置，因此存在引用位置，而在鏈接列表的情況下則不存在。

表示形式：

鏈表由指向鏈表第一個(gè)節(jié)點(diǎn)的指針表示。第一個(gè)節(jié)點(diǎn)稱為頭。如果鏈表為空，則head的值為NULL。

列表中的每個(gè)節(jié)點(diǎn)至少由兩部分組成：

1）數(shù)據(jù)

2）指向下一個(gè)節(jié)點(diǎn)的指針（或引用）

在C語言中，我們可以使用結(jié)構(gòu)表示一個(gè)節(jié)點(diǎn)。以下是帶有整數(shù)數(shù)據(jù)的鏈表節(jié)點(diǎn)的示例。

在Java或C＃中，LinkedList可以表示為一個(gè)類，而Node可以表示為單獨(dú)的類。LinkedList類包含Node類類型的引用。

C

C++

C中的第一個(gè)簡(jiǎn)單鏈接列表讓我們創(chuàng)建一個(gè)包含3個(gè)節(jié)點(diǎn)的簡(jiǎn)單鏈接列表。

C ++（注釋為英文）

C

鏈表遍歷

在上一個(gè)程序中，我們創(chuàng)建了一個(gè)具有三個(gè)節(jié)點(diǎn)的簡(jiǎn)單鏈表。讓我們遍歷創(chuàng)建的列表并打印每個(gè)節(jié)點(diǎn)的數(shù)據(jù)。為了進(jìn)行遍歷，讓我們編寫一個(gè)通用函數(shù)printList（）來打印任何給定的列表。

C ++