鏈表是物理存儲(chǔ)單元上的一種非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接順序來(lái)實(shí)現(xiàn)的。鏈表由一系列節(jié)點(diǎn)組成（鏈表中的每個(gè)元素稱為節(jié)點(diǎn)），這些節(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)節(jié)點(diǎn)包括兩

鏈表是物理存儲(chǔ)單元上的一種非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接順序來(lái)實(shí)現(xiàn)的。鏈表由一系列節(jié)點(diǎn)組成（鏈表中的每個(gè)元素稱為節(jié)點(diǎn)），這些節(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)節(jié)點(diǎn)包括兩部分：一部分是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)字段，另一部分是存儲(chǔ)下一個(gè)節(jié)點(diǎn)地址的指針字段。與線性表序結(jié)構(gòu)相比，操作更為復(fù)雜。由于鏈表不需要按順序存儲(chǔ)，因此鏈表插入時(shí)的復(fù)雜度可以達(dá)到o（1），比其他線性序列表快得多。但是，查找節(jié)點(diǎn)或訪問(wèn)具有特定編號(hào)的節(jié)點(diǎn)需要O（n）個(gè)時(shí)間。線性表和序列表的時(shí)間復(fù)雜度分別為o（logn）和o（1）。

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要提前知道數(shù)據(jù)大小的缺點(diǎn)。鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的動(dòng)態(tài)內(nèi)存管理。然而，鏈表失去了隨機(jī)數(shù)組讀取的優(yōu)勢(shì)，由于增加了節(jié)點(diǎn)的指針字段，鏈表的空間開(kāi)銷相對(duì)較大。鏈表最明顯的優(yōu)點(diǎn)是關(guān)聯(lián)項(xiàng)的常規(guī)數(shù)組排列可能與這些數(shù)據(jù)項(xiàng)在內(nèi)存或磁盤中的排列順序不同，數(shù)據(jù)的存取往往需要按不同的排列順序進(jìn)行轉(zhuǎn)換。鏈表允許在列表的任何位置插入和刪除節(jié)點(diǎn)，但不允許隨機(jī)訪問(wèn)。鏈表有許多不同的類型：?jiǎn)蜗蜴湵?、雙向鏈表和循環(huán)鏈表。鏈表可以用許多編程語(yǔ)言實(shí)現(xiàn)。鏈表的訪問(wèn)和操作包含在LISP和scheme等語(yǔ)言的內(nèi)置數(shù)據(jù)類型中。編程語(yǔ)言或面向?qū)ο笳Z(yǔ)言（如C、C和Java）依賴于變量工具來(lái)生成鏈表。