Linear List 線性表
[TOC]
基本概念
最常用，最簡單的一種數(shù)據(jù)結(jié)構(gòu)。
是由n（n>=0）個數(shù)據(jù)元素（結(jié)點）a[0]，a[1]，a[2]…，a[n-1]組成的有限序列。
一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項item組成。數(shù)據(jù)元素稱為記錄record，含有大量記錄的線性表又稱為文件file。
這種結(jié)構(gòu)具有下列特點 ：
- 頭元素：存在一個唯一的沒有前驅(qū)的（頭）數(shù)據(jù)元素；
- 尾元素：存在一個唯一的沒有后繼的（尾）數(shù)據(jù)元素；
- 除此之外，每一個數(shù)據(jù)元素均有一個直接前驅(qū)和一個直接后繼數(shù)據(jù)元素。
一、兩種表示結(jié)構(gòu) 1.順序表示 2.鏈?zhǔn)奖硎?/h2>
1.1 順序表示
使用數(shù)組來存儲線性表。
隨機(jī)訪問效率高，插入刪除可能需要移動大量的數(shù)據(jù)。
1.2 鏈?zhǔn)奖硎荆烘湵? linked list
使用鏈表來存儲線性表。
數(shù)據(jù)存儲于節(jié)點Node的數(shù)據(jù)域中，節(jié)點之間使用指針或引用連接。
插入效率高，隨機(jī)訪問效率低。
1.2.1 線性鏈表(又名單鏈表、單向鏈表) singly linked list
特點是鏈表的方向是單向的
1.2.2 循環(huán)鏈表 circular linked list
單向鏈表的表尾指向表頭，則整個鏈表形成一個環(huán)。
是否為空的判斷條件是下一個節(jié)點是不是頭指針。
1.2.2 雙向鏈表 double linked list
單向鏈表只能順著一個方向查找元素，指針域只指示后繼節(jié)點。
因此 nextElement的時間復(fù)雜度是O(1),而PriorElement的時間復(fù)雜度是O(n)。
為了克服這種缺點，產(chǎn)生了雙向鏈表double linked list.指針域有兩個指針，分別指向前驅(qū)和后繼節(jié)點。
1.2.3 其他鏈表：靜態(tài)鏈表 Static Linked List
static_linked_list.png
用數(shù)組描述的鏈表，即稱為靜態(tài)鏈表
對于線性鏈表，也可用一維數(shù)組來進(jìn)行描述。這種描述方法便于在沒有指針類型的高級程序設(shè)計語言中使用鏈表結(jié)構(gòu)。
仍舊有指針型鏈表的優(yōu)點。
