鏈表是什么

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

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

1、鏈接方式不同

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

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

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

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

2、遍歷方式不同

單鏈表：只能單向遍歷，無法回退。

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

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

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

3、應用場景不同

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

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

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

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