線性表
????????線性表是由個(gè)相同類型的數(shù)據(jù)元素組成的有限序列茄茁，它是最基本魂贬、最常用的一種線性結(jié)構(gòu)。顧名思義裙顽，線性表就像是一條線付燥，不會分叉。線性表有唯一的開始和結(jié)束锦庸，除了第一個(gè)元素外机蔗，每一個(gè)元素都有唯一的直接前驅(qū)，除了最后一個(gè)元素外甘萧，每一個(gè)元素都有唯一的直接后繼。
順序表
????????順序表是順序存儲方式梆掸，即邏輯上相鄰的數(shù)據(jù)在計(jì)算機(jī)內(nèi)的存儲位置也是相鄰的扬卷。順序存儲方式，元素存儲是連續(xù)的酸钦，中間不允許有空怪得，可以快速定位第幾個(gè)元素，但是插入卑硫、刪除時(shí)需要移動大量元素徒恋。
鏈表
????????鏈表是線性表的鏈?zhǔn)酱鎯Ψ绞剑壿嬌舷噜彽臄?shù)據(jù)在計(jì)算機(jī)內(nèi)的存儲位置不一定相鄰欢伏。
單鏈表
????????單鏈表是鏈表中的一種形式入挣，那么如何定義單鏈表：
????????單鏈表一般由兩個(gè)變量組成，data變量代表單鏈表中存儲的值硝拧，next變量代表單鏈表中指向下一個(gè)節(jié)點(diǎn)的指針径筏。以下兩張圖分別是不帶哨兵節(jié)點(diǎn)的單鏈表和帶哨兵節(jié)點(diǎn)的單鏈表。
單鏈表的操作
- 初始化
- 創(chuàng)建
- 查找障陶、取值
- 插入
- 刪除
初始化
????????初始化一般就是聲明頭指針滋恬。
創(chuàng)建
????????創(chuàng)建的方式，一般有兩種頭插法和尾插法
//L為頭結(jié)點(diǎn)抱究，r為最后一個(gè)節(jié)點(diǎn)恢氯，s為新增節(jié)點(diǎn)
//頭插法的偽代碼
s->next = L->next
L->next = s
//尾插法的偽代碼
r -> next = s
取值、查找
????????單鏈表的取值操作一般都是從頭結(jié)點(diǎn)往后進(jìn)行遍歷，時(shí)間復(fù)雜度為O(n)勋拟。
//頭指針L遏暴， j為所要取的數(shù)，p為當(dāng)前指針, v為查找的值
//取值偽代碼
i = 0;
p = L ->next;
while(p != null || i != j){
p = p ->next;
i = i + 1;
}
//查找偽代碼
i = 0;
p = L ->next;
while(p != null && p ->value != v){
i++;
p = p ->next;
}
插入
????????單鏈表的插入非常簡便指黎，只需將插入節(jié)點(diǎn)的next指針指向后一個(gè)節(jié)點(diǎn)朋凉，前一個(gè)節(jié)點(diǎn)的next指針指向插入的節(jié)點(diǎn)。時(shí)間復(fù)雜度O(1)醋安。
//e為插入節(jié)點(diǎn)杂彭，p指針指向當(dāng)前插入的節(jié)點(diǎn)
e ->next = p ->next;
p ->next = e;
刪除
????????單點(diǎn)表的刪除操作也非常簡便，將當(dāng)前刪除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next指針指向刪除節(jié)點(diǎn)的next指針指向的節(jié)點(diǎn)就好了吓揪。時(shí)間復(fù)雜度O(1)亲怠。
//p為刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，q為刪除節(jié)點(diǎn)
p ->next = q ->next
雙向鏈表
????????雙向鏈表與單鏈表相比多了一個(gè)前驅(qū)柠辞。所以在操作中团秽，它比單鏈表還多了一個(gè)privor指針操作。舉個(gè)插入例子：
//p為當(dāng)前節(jié)點(diǎn)叭首，a為插入的節(jié)點(diǎn)
p ->next ->privor = a
a ->next = p ->next
a ->privor = p
