最近經(jīng)常聽到朋友面試有被問到鏈表的問題,自己也總結(jié)了一下,應(yīng)該算是比較入門向的介紹吧

線性表（數(shù)組）

數(shù)據(jù)與元素一一對應(yīng) 除了第一個和最后一個其他數(shù)據(jù)元素首位相接

順序表

線性表中用地址連續(xù)的存儲單元來存放數(shù)據(jù)元素的數(shù)據(jù)結(jié)構(gòu)，結(jié)點放在地址連續(xù)的存儲單元中（實現(xiàn)方式為數(shù)組）——

鏈表

①物理存儲單元上非連續(xù)，非順序的存儲結(jié)構(gòu)（內(nèi)存之中不連續(xù)）

②數(shù)據(jù)元素之間的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)

③鏈表由一系列結(jié)點組成（鏈表中的元素稱為結(jié)點），結(jié)點可以在運行時動態(tài)生成

④結(jié)點包括兩個部分：1.存儲數(shù)據(jù)元素的數(shù)據(jù)域

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.存儲下一個結(jié)點地址的指針域

（實現(xiàn)方式為指針）

ps1:尾結(jié)點 指針域為null,若尾結(jié)點指針指向首結(jié)點，那么構(gòu)成環(huán)形鏈表

相對于線性表的優(yōu)勢

①鏈表比較方便插入和刪除操作，線性表中插入一個元素，那么后面的元素地址都要往后移，刪除同理。而鏈表只需要修改結(jié)點中的指針信息，不需要修改結(jié)點地址。

②線性表在建立時就確定的總長度 因此初始長度過大或者過小都會引起內(nèi)存問題：如果內(nèi)存中沒辦法一次性給出整個線性表所需的存儲空間那么就會提示內(nèi)存不足，鏈表可以用分散的存儲空間

③鏈表的擴展性比線性表（數(shù)組）好，一個線性表在建立后空間大小是固定的，要擴展只能新建一個更大的，而鏈表可以很方便的擴展

線性表相對于鏈表的優(yōu)勢

①線性表存儲空間小，因為鏈表要在存儲單元里放一個或者兩個指針（雙向鏈表）

②線性表內(nèi)容可以隨機訪問，因為是連續(xù)的內(nèi)存單元，地址連續(xù)所以在這個區(qū)間內(nèi)可以進行隨機，鏈表存儲地址

③查找速度由于存儲地址原因也快于鏈表

雙向鏈表

一句話 結(jié)點中有兩個指針 一個指針指向直接前驅(qū)，一個指針指向直接后繼

優(yōu)勢：查找更方便，用于大量數(shù)據(jù)的遍歷

相對于單向 存儲空間也更大