1、 鏈表的概念
概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的
1、鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成。
2、結(jié)點可以在運行時動態(tài)(malloc)生成。
3、每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域（詳見1.2 節(jié)點部分）。
4、相比于線性表順序結(jié)構(gòu)，鏈表操作復(fù)雜。但是由于不需按順序存儲，鏈表在插入的時候可以達到O(1)的復(fù)雜度，比順序表快得多；但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而順序表只需O(1)
2、 結(jié)點
鏈表由一個個結(jié)點構(gòu)成，每個結(jié)點采用結(jié)構(gòu)體的形式。結(jié)構(gòu)體內(nèi)前面的變量按照需要給予，最后一個變量是這個結(jié)構(gòu)體類型的指針，用來存放下一節(jié)點的首地址‘
鏈表結(jié)點分為兩個域
數(shù)據(jù)域 ：存放各種實際的數(shù)據(jù)
指針域 ：存放下一結(jié)點的地址
（圖為帶哨兵位頭結(jié)點的鏈表）
3、 鏈表的使用場景
線性表在 需要經(jīng)常插入或刪除數(shù)據(jù)元素 的情況下適合采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。
因為對于鏈表來說，插入或刪除數(shù)據(jù)只需要創(chuàng)建一個結(jié)點、輸入數(shù)據(jù)、修改指針把該結(jié)點連接到鏈表中的某一位置即可； 而對于順序表，插入一個數(shù)據(jù)可能需要搬移其他數(shù)據(jù)，復(fù)雜度高。
4、 鏈表分類 和 常用的結(jié)構(gòu)
各種鏈表的結(jié)構(gòu)：
雖然組合起來一共有8種鏈表可以選擇，但是實際中最常用的主要還是 無頭單向非循環(huán) 鏈表和 帶頭雙向循環(huán) 鏈表。
1、無頭單向非循環(huán)鏈表：俗稱 “單鏈表”。結(jié)構(gòu)簡單，一般不會單獨用來存儲數(shù)據(jù)。實際上更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)（如哈希桶、圖的鄰接表、棧的鏈?zhǔn)浇Y(jié)構(gòu)等）
2、帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用來單獨存儲數(shù)據(jù)。實際使用的鏈表，大多都是帶頭雙向循環(huán)鏈表。雖然結(jié)構(gòu)最復(fù)雜，但是這種結(jié)構(gòu)會帶來很多優(yōu)勢。
5、 與順序表的比較
鏈表： 鏈表是通過結(jié)點把離散的數(shù)據(jù)鏈接成一個表，通過對結(jié)點的插入、刪除操作從而實現(xiàn)對數(shù)據(jù)的存取。
順序表： 順序表是通過開辟一段連續(xù)的內(nèi)存（直接使用 數(shù)組 或者 malloc后realloc擴容）來存儲數(shù)據(jù)。
但是由于 realloc 擴容分為原地擴容和異地擴容，前者代價較低，而后者擴容時不僅需要拷貝數(shù)據(jù)，還要釋放舊空間。再者，擴容時一般會擴到原來容量的2倍，擴容次數(shù)多了就容易造成空間的浪費文章來源：http://www.zghlxwxcb.cn/news/detail-406557.html
順序表的每個成員對應(yīng)鏈表的結(jié)點；成員和結(jié)點的數(shù)據(jù)類型可以是標(biāo)準(zhǔn)的c類型或者是用戶自定義的結(jié)構(gòu)體類型。文章來源地址http://www.zghlxwxcb.cn/news/detail-406557.html
| 比較對象 | 順序表 | 鏈表 |
|---|---|---|
| 存儲空間 | 連續(xù) | 不連續(xù) |
| 插入或刪除數(shù)據(jù) | 可能要搬移數(shù)據(jù)，復(fù)雜度O(n) | 只需修改指針 |
| push | 動態(tài)順序表：空間不夠了需要擴容 | 沒有“容量”的概念，push時直接malloc新的結(jié)點 |
| 應(yīng)用 | 需要頻繁訪問 | 需要頻繁插入、刪除數(shù)據(jù) |
到了這里，關(guān)于＜數(shù)據(jù)結(jié)構(gòu)＞ 鏈表 - 鏈表的概念及結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
