一宵呛、線性表簡單介紹
1.1、描述
線性表是數(shù)據(jù)結構中最基礎的一種結構夕凝，一個線性表是由n個具有相同特性的數(shù)據(jù)元素組成的有限序列宝穗，并且數(shù)據(jù)元素之間是1對1的關系。
例如：線性表（a1,a2,a3,...,ai-1,ai,ai+1）
根據(jù)其定義分析：
1.1.1码秉、a1~ai+1逮矛，每個對象都必須是相同的數(shù)據(jù)元素；
1.1.2转砖、取其中三個元素(ai-1,ai,ai+1),ai-1是ai的前驅(qū)须鼎，ai+1是ai的后繼，相鄰兩個節(jié)點的關系必須是1對1的府蔗。
1.2晋控、線性表物理分類
線性表順序存儲結構：
線性表鏈式存儲結構：
二、線性表順序的存儲結構
線性表的順序存儲結構是在計算機內(nèi)存分配一塊連續(xù)的空間依次存儲線性表的數(shù)據(jù)元素姓赤。我們經(jīng)常使用的數(shù)組就是這樣一種數(shù)據(jù)結構赡译。
線性表順序存儲-數(shù)組分析：
2.1、指定數(shù)組初始大小不铆，分配一塊連續(xù)的內(nèi)存空間
當我們給定的初始大小偏小時蝌焚，數(shù)組容易上溢，如果添加新增元素判斷邏輯誓斥，當數(shù)組沒有剩余空間只洒，重新申請一塊連續(xù)的內(nèi)存，空間是原來的1.5倍劳坑，然后將數(shù)據(jù)從原來的數(shù)組移動到新數(shù)組毕谴，Copy數(shù)組是個很耗時的操作。比如數(shù)組初始空間是1G距芬，現(xiàn)在已經(jīng)存儲1G數(shù)據(jù)涝开，當有新數(shù)據(jù)來是，發(fā)生擴容操作蔑穴，壓力是很大的忠寻。
當我們給定的初始大小偏大時，如果實際用不到這么多內(nèi)存存和，就會造成空間浪費奕剃。
public class ArrayList<T> {
private Object[] data;
private int length;//數(shù)組長度
private int size;//數(shù)據(jù)長度
public ArrayList(int length) {
data = new Object[length];
this.length = length;
this.size = 0;
}
public ArrayList() {
this(16);
}
}
2.2、向下標為i的位置捐腿，插入數(shù)據(jù)
當我們需要在下標i插入數(shù)據(jù)纵朋，需要將下標>=i的數(shù)據(jù)全都往后移動一次靶擦，數(shù)組(數(shù)組長度為n)插入操作的時間復雜度是O(n)
2.3容燕、刪除下標為i的數(shù)據(jù)
當我們需要刪除下標為i的數(shù)據(jù)，需要將>i的數(shù)據(jù)全都往前移動一次,數(shù)組(數(shù)組長度為n)刪除操作的時間復雜度是O(n)
2.4请毛、查詢下標為i的數(shù)據(jù)
假定數(shù)組的第一個數(shù)據(jù)的地址是base_address,當我們需要查詢下標為i的數(shù)據(jù)時宪祥，直接查詢地址為base_address+i*sizeof(data)聂薪，sizeof(data)表示元素類型的字節(jié)長家乘。
總結：
1、按下標查找數(shù)據(jù)藏澳，數(shù)組的時間復雜是O(1),查詢快仁锯；
2、插入翔悠、刪除數(shù)組數(shù)據(jù)业崖，時間復雜度是O(n),耗時；
3蓄愁、連續(xù)的存儲空間如果分配太大双炕，容易造成空間浪費，分配太小撮抓，動態(tài)擴容妇斤，時間復雜度高。
三胀滚、線性表的鏈式存儲結構
線性表的鏈式存儲結構是一組任意的內(nèi)存空間存儲數(shù)據(jù)元素趟济，用引用將數(shù)據(jù)元素關聯(lián)，數(shù)據(jù)元素包含數(shù)據(jù)域和指針域咽笼，指針域存放下一個元素的地址顷编，同一種數(shù)據(jù)元素用鏈表比數(shù)組占用更多的空間。
線性表鏈式存儲-單鏈表分析
3.1剑刑、運用哨兵機制媳纬，創(chuàng)建頭結點，構造鏈表
在構造方法創(chuàng)建哨兵頭結點施掏，便于操作鏈表钮惠，之后所有節(jié)點都是基于頭結點操作的。頭結點的數(shù)據(jù)域不存放數(shù)據(jù)七芭，指針域存放頭指針素挽。
public class SingleLinkList<T> {
private Node<T> head;
private int count;
public SingleLinkList() {
this.head = new Node<T>(null);
this.count = 0;
}
public static class Node<T>{
private T data;
private Node next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
}
3.2、運用頭插法狸驳，插入數(shù)據(jù)
頭插法指的是new一個新節(jié)點预明，將頭結點的指針域的值賦值給新節(jié)點的指針域，將新節(jié)點的地址賦值給頭結點的指針域耙箍，這樣就是通過頭插法插入一個新節(jié)點撰糠，插入一個節(jié)點的時間復雜度是O(1)。
3.3辩昆、刪除指定節(jié)點
例如連續(xù)的三個節(jié)點a1,a2,a3阅酪，現(xiàn)在需要將a2節(jié)點刪除，鏈表可以直接將a2節(jié)點指針域的值賦值給a1節(jié)點的指針域，刪除一個節(jié)點時間復雜度是O(1)
3.4术辐、查詢某個節(jié)點的數(shù)據(jù)
鏈表查詢指定節(jié)點的數(shù)據(jù)砚尽，不能像數(shù)組一樣直接通過計算地址找到數(shù)據(jù)，鏈表需要從頭結點開始辉词，一個節(jié)點接著一個節(jié)點往下找尉辑，所以鏈表的查詢沒有數(shù)組快，時間復雜度是O(n)
總結：
1较屿、通過節(jié)點地址，查詢數(shù)據(jù)卓练，鏈表的時間復雜度是O(n);
2隘蝎、插入刪除鏈表節(jié)點，時間復雜度是O(1);
3襟企、鏈表不需要連續(xù)的內(nèi)存空間嘱么，如果大數(shù)據(jù)量需要插入和刪除操作，鏈表的優(yōu)勢就很明顯顽悼。
雙向鏈表的節(jié)點有兩個指針域和一個數(shù)據(jù)域曼振，前面的指針域指向前一個節(jié)點，后面的指針域指向下一個節(jié)點蔚龙，對比單鏈表冰评，存儲相同的數(shù)據(jù)，占用更多的空間木羹，但是在任何一個節(jié)點甲雅，都可以很快找到它的前一個節(jié)點。
