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

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

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要提前知道數(shù)據(jù)大小的缺點(diǎn)。鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的動態(tài)內(nèi)存管理。然而，鏈表失去了隨機(jī)數(shù)組讀取的優(yōu)勢，由于增加了節(jié)點(diǎn)的指針字段，鏈表的空間開銷相對較大。鏈表最明顯的優(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ī)訪問。鏈表有許多不同的類型：單向鏈表、雙向鏈表和循環(huán)鏈表。鏈表可以用許多編程語言實(shí)現(xiàn)。鏈表的訪問和操作包含在LISP和scheme等語言的內(nèi)置數(shù)據(jù)類型中。編程語言或面向?qū)ο笳Z言（如C、C和Java）依賴于變量工具來生成鏈表。