鏈表是什么

鏈表是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)體指針在這里得到了充分的利用。鏈表可以動(dòng)態(tài)的進(jìn)行存儲(chǔ)分配，也就是說，鏈表是一個(gè)功能極為強(qiáng)大的數(shù)組，他可以在節(jié)點(diǎn)中定義多種數(shù)據(jù)類型，還可以根據(jù)需要隨意增添，刪除，插入節(jié)點(diǎn)。鏈表都有一個(gè)頭指針，一般以head來表示，存放的是一個(gè)地址。鏈表中的節(jié)點(diǎn)分為兩類，頭結(jié)點(diǎn)和一般節(jié)點(diǎn)，頭結(jié)點(diǎn)是沒有數(shù)據(jù)域的。鏈表中每個(gè)節(jié)點(diǎn)都分為兩部分，一個(gè)數(shù)據(jù)域，一個(gè)是指針域。說到這里你應(yīng)該就明白了，鏈表就如同車鏈子一樣，head指向第一個(gè)元素：第一個(gè)元素又指向第二個(gè)元素;……，直到最后一個(gè)元素，該元素不再指向其它元素，它稱為“表尾”，它的地址部分放一個(gè)“NULL”(表示“空地址”)，鏈表到此結(jié)束。

單鏈表雙鏈表單循環(huán)鏈表雙循環(huán)鏈表有什么區(qū)別

1、鏈接方式不同

單鏈表：每個(gè)節(jié)點(diǎn)只有一個(gè)指針，指向下一個(gè)節(jié)點(diǎn)，從而形成一個(gè)單向的鏈表。

雙鏈表：每個(gè)節(jié)點(diǎn)有兩個(gè)指針，一個(gè)指向前驅(qū)節(jié)點(diǎn)，一個(gè)指向后繼節(jié)點(diǎn)，使得鏈表成為一個(gè)雙向的鏈表。

單循環(huán)鏈表：每個(gè)節(jié)點(diǎn)也只有一個(gè)指針，但是可以將鏈表最后一個(gè)節(jié)點(diǎn)的指針指向鏈表的頭節(jié)點(diǎn)，從而形成一個(gè)循環(huán)鏈表。

雙循環(huán)鏈表：每個(gè)節(jié)點(diǎn)有兩個(gè)指針，一個(gè)指向前驅(qū)節(jié)點(diǎn)，一個(gè)指向后繼節(jié)點(diǎn)，同時(shí)鏈表的第一個(gè)節(jié)點(diǎn)的前驅(qū)指針指向最后一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的后繼指針指向第一個(gè)節(jié)點(diǎn)，也就是形成一個(gè)環(huán)。

2、遍歷方式不同

單鏈表：只能單向遍歷，無(wú)法回退。

雙鏈表：可以雙向遍歷，可以在單鏈表的基礎(chǔ)上支持反向遍歷。

單循環(huán)鏈表：可以循環(huán)遍歷。

雙循環(huán)鏈表：可以通過任何一個(gè)節(jié)點(diǎn)開始正向或反向遍歷整個(gè)鏈表，通過尾節(jié)點(diǎn)開始遍歷也可以回到頭節(jié)點(diǎn)。

3、應(yīng)用場(chǎng)景不同

單鏈表：節(jié)點(diǎn)占用空間小，插入和刪除節(jié)點(diǎn)速度快，適用于不需要反向遍歷的場(chǎng)合。

雙鏈表：節(jié)點(diǎn)占用空間比單鏈表大，插入和刪除節(jié)點(diǎn)的操作復(fù)雜度更高，適用于需要雙向遍歷的場(chǎng)合。

單循環(huán)鏈表：在處理循環(huán)遍歷的問題上更加方便，也可用于實(shí)現(xiàn)循環(huán)隊(duì)列。

雙循環(huán)鏈表：在需要首尾相連的問題中比較適用。