鏈表與數(shù)組在數(shù)據(jù)結(jié)構(gòu)的江湖上被并稱(chēng)為南數(shù)組烫堤、北鏈表指煎，其江湖地位可見(jiàn)一斑
概念
鏈表作為最基礎(chǔ)的通用存儲(chǔ)結(jié)構(gòu)仗阅，它的作用和數(shù)組是一樣的，但存儲(chǔ)數(shù)據(jù)的方式略有不同重归。數(shù)組需要預(yù)先獲取一定的內(nèi)存空間米愿，且內(nèi)存的地址是連續(xù)的，在存儲(chǔ)數(shù)據(jù)的時(shí)候鼻吮，插入和刪除都需要遍歷數(shù)組育苟，還需要移動(dòng)部分?jǐn)?shù)據(jù)，是十分低效的椎木。而鏈表能夠解決以上問(wèn)題违柏，下面來(lái)看一下鏈表的結(jié)構(gòu)。
鏈表的數(shù)據(jù)項(xiàng)存儲(chǔ)在鏈表節(jié)點(diǎn)中香椎，一個(gè)節(jié)點(diǎn)可以叫Node也可以叫Link漱竖，它包含數(shù)據(jù)項(xiàng)和一個(gè)引用，數(shù)據(jù)項(xiàng)存儲(chǔ)數(shù)據(jù)本身畜伐，通常是一個(gè)包含各種數(shù)據(jù)的類(lèi)的對(duì)象馍惹，而引用則是引用下一個(gè)節(jié)點(diǎn)，一般記為next玛界，鏈表的核心實(shí)現(xiàn)就是這個(gè)next万矾，它標(biāo)記了每個(gè)節(jié)點(diǎn)之間的聯(lián)系，像一根線一樣把這些散落在內(nèi)存各個(gè)角落的節(jié)點(diǎn)對(duì)象串了起來(lái)慎框。下面通過(guò)代碼來(lái)直觀的理解一下：
/**
* 鏈表的節(jié)點(diǎn)良狈，用來(lái)存放數(shù)據(jù)
*/
public class Node {
// 數(shù)據(jù)變量
private String data;
// next引用
public Node next;
// 構(gòu)造函數(shù)
public Node(String str) {
data = str;
}
// getter
public String getData() {
return data;
}
// Node的打印方法
public void displayNode() {
System.out.print("{ Node: " + data + " }..");
}
}
可以看到，鏈表節(jié)點(diǎn)的關(guān)鍵兩個(gè)屬性笨枯，一個(gè)是數(shù)據(jù)項(xiàng)（這里簡(jiǎn)單的表示為String類(lèi)型的data）薪丁，一個(gè)是指向下一個(gè)鏈表節(jié)點(diǎn)的next引用（這里為了訪問(wèn)簡(jiǎn)單設(shè)置為public）遇西，雖然還不知道下一個(gè)節(jié)點(diǎn)是誰(shuí)，但在鏈表的數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)中窥突，將數(shù)據(jù)插入時(shí)努溃，就會(huì)建立這個(gè)聯(lián)系硫嘶。
單向鏈表
以上說(shuō)明了鏈表的重要概念阻问，節(jié)點(diǎn)與引用，下面來(lái)展示如何構(gòu)成一個(gè)鏈表沦疾，首先從最簡(jiǎn)單的單向鏈表開(kāi)始称近，單向鏈表顧名思義，只有一端可以插入和訪問(wèn)的鏈表哮塞，鏈表類(lèi)LinkList值僅維護(hù)第一個(gè)鏈表節(jié)點(diǎn)first的信息刨秆，其它的節(jié)點(diǎn)通過(guò)next引用，以下是實(shí)現(xiàn)代碼：
/**
* 單向鏈表：維護(hù)頭節(jié)點(diǎn)的信息忆畅，對(duì)鏈表的操作都從頭部開(kāi)始
*/
public class LinkList {
// 頭節(jié)點(diǎn)的引用
Node first;
// 構(gòu)造方法
public LinkList() {
first = null;
}
// 插入方法衡未，頭插法
public void insertFirst(String str) {
Node newNode = new Node(str);
newNode.next = first;
first = newNode;
}
// 刪除方法，刪除頭部節(jié)點(diǎn)
public Node deleteFirst() {
Node temp = first;
first = first.next;
return temp;
}
// 打印鏈表方法
public void display() {
System.out.print("LinkList: ");
Node current = first;
while (current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}
// 判斷鏈表是否為空的方法
public Boolean isEmpty() {
return first == null;
}
// 在鏈表中查找的方法
public Node find(String str) {
Node current = first;
while (current != null) {
if (current.getData() != str)
current = current.next;
return current;
}
System.out.println("could not find Node :" + str);
return null;
}
// 從鏈表中查找元素刪除方法
public Node delete(String str) {
Node current = first;
Node previous = first;
while (current != null) {
if (current.getData() != str) {
previous = current;
current = current.next;
} else {
previous.next = current.next;
return current;
}
}
System.out.println("cloud not find Node:" + str + ", failed to delete it");
return null;
}
}
代碼中定義了唯一一個(gè)變量：頭節(jié)點(diǎn)的引用first家凯，還有一些鏈表的常用方法：插入缓醋、刪除、查找绊诲、展示等送粱，可以發(fā)現(xiàn)這些方法都是由頭節(jié)點(diǎn)first展開(kāi)的，在表達(dá)這些方法的時(shí)候需要注意邊界和特殊情況first的分析掂之。
雙端鏈表
注意是雙端列表抗俄，不是雙向鏈表，在上面的單向鏈表中世舰，鏈表類(lèi)僅維護(hù)了一個(gè)頭節(jié)點(diǎn)的引用first动雹，那么如果要在鏈表尾部插入一個(gè)數(shù)據(jù)，需要遍歷整個(gè)鏈表跟压，這種效率很低胰蝠。雙端鏈表不僅維護(hù)了first頭節(jié)點(diǎn)的引用，而且還維護(hù)了last尾節(jié)點(diǎn)的引用裆馒，這樣訪問(wèn)尾節(jié)點(diǎn)就像訪問(wèn)頭節(jié)點(diǎn)一樣方便姊氓，這種特性使得雙端鏈表比起單向鏈表在一些場(chǎng)合更有效率，比如說(shuō)隊(duì)列喷好。
以下展示雙端鏈表的實(shí)現(xiàn)代碼翔横，節(jié)點(diǎn)還是引用上面的Node類(lèi)
public class DoubleSideLinkList {
// 首節(jié)點(diǎn)和尾節(jié)點(diǎn)的引用
Node first;
Node last;
// constructor
public DoubleSideLinkList() {
first = null;
last = null;
}
// isEmpty
public boolean isEmpty() {
return first == null;
}
// insert first
public void insertFirst(String str) {
Node newNode = new Node(str);
if (isEmpty()) {
last = newNode;
}
newNode.next = first;
first = newNode;
}
// insert last
public void insertLast(String str) {
Node newNode = new Node(str);
if (isEmpty()) {
first = newNode;
}
last.next = newNode;
last = newNode;
}
// delete first
public Node deleteFirst() {
Node temp = first;
// 僅有一個(gè)元素
if (first.next == null)
last = null;
first = first.next;
return temp;
}
// display
public void displayList() {
System.out.println("List (first-->last): ");
Node current = first;
while(current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}
}
可以看出，雙端鏈表可以很方便的從尾節(jié)點(diǎn)插入數(shù)據(jù)梗搅，這里需要說(shuō)明的是禾唁，這個(gè)鏈表依然是單向的效览，每個(gè)節(jié)點(diǎn)也僅有一個(gè)引用next指向下一個(gè)節(jié)點(diǎn)，所以遍歷和查找的方法與單向鏈表沒(méi)什么差別荡短，在此就不做展示丐枉。在實(shí)現(xiàn)雙端鏈表的insert與delete方法的時(shí)候需要注意特殊情況：列表為空或者列表將要為空時(shí)，first與last的處理掘托。
有序鏈表
有序鏈表中瘦锹，數(shù)據(jù)是按照關(guān)鍵值的有序排列的，有序鏈表的插入速度優(yōu)于有序數(shù)組闪盔，而且可以擴(kuò)展到所有有效的內(nèi)存弯院，所以在很多場(chǎng)合可以使用有序鏈表，在以下的實(shí)現(xiàn)中泪掀，我們還是引用上面的Node類(lèi)听绳，因?yàn)閿?shù)據(jù)項(xiàng)data為String類(lèi)型，我們以數(shù)據(jù)項(xiàng)的hashcode為序來(lái)實(shí)現(xiàn)有序鏈表：
public class SortedLinkList {
// filed
Node first;
// constructor
public SortedLinkList() {
first = null;
}
public boolean isEmpty() {
return (first==null);
}
public void insert(String key) {
Node current = first;
Node previous = null;
Node newNode = new Node(key);
while (current != null && current.getData().hashCode() < key.hashCode()) {
previous = current;
current = current.next;
}
if (previous == null) {
first = newNode;
} else {
previous.next = newNode;
}
newNode.next = current;
}
public Node remove() {
Node temp = first;
first = first.next;
return temp;
}
public void display() {
System.out.print("LinkList: ");
Node current = first;
while (current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}
}
有序鏈表主要是insert方法比較難實(shí)現(xiàn)异赫，也是需要考慮特殊情況椅挣，即鏈表為空。
雙向鏈表
雙向鏈表與雙端鏈表不同塔拳，雙端鏈表雖然可以從尾部插入節(jié)點(diǎn)鼠证，但是每個(gè)節(jié)點(diǎn)引用的還是其下一個(gè)節(jié)點(diǎn)，遍歷也是單向的蝙斜，而雙向鏈表則可以從頭部或者從尾部開(kāi)始遍歷名惩，為了實(shí)現(xiàn)這一特性，我們需要修改一下節(jié)點(diǎn)類(lèi)Node孕荠，為了區(qū)分娩鹉，我們以Link為節(jié)點(diǎn)命名，在Link中稚伍，不僅實(shí)現(xiàn)對(duì)下一節(jié)點(diǎn)的引用next弯予，而且還實(shí)現(xiàn)了對(duì)上一個(gè)節(jié)點(diǎn)的引用previous，如下：
public class Link {
private int data;
public Link next;
public Link previous;
public Link(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void displayLink() {
System.out.print(data + " ");
}
}
唯一不同的點(diǎn)就是指向上一個(gè)節(jié)點(diǎn)的引用previous个曙，雖然僅在節(jié)點(diǎn)中加了一個(gè)引用锈嫩，但是雙向鏈表的實(shí)現(xiàn)卻麻煩了很多，其中各種引用關(guān)系特別容易混亂垦搬，而且還有一些特殊情況需要考慮呼寸，下面一起來(lái)感受一下：
public class DoublyLinkList {
// 頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的引用，也是雙端的
Link first;
Link last;
// constructor
public DoublyLinkList() {
first = null;
last = null;
}
// isEmpty
public boolean isEmpty() {
return first == null;
}
// insert first
public void insertFirst(int data) {
Link newLink = new Link(data);
if (isEmpty()) {
last = newLink;
} else {
first.previous = newLink;
}
newLink.next = first;
first = newLink;
}
// insert last
public void insertLast(int data) {
Link newLink = new Link(data);
if (isEmpty()) {
first = newLink;
} else {
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}
// insert after
public boolean insertAfter(int key, int data) {
Link newLink = new Link(data);
Link current = first;
// find
while(current != null) {
if (current.getData() != key) {
current = current.next;
} else {
if (current == last) {
newLink.next = null;
last = newLink;
} else {
newLink.next = current.next;
current.next.previous = newLink;
}
current.next = newLink;
newLink.previous = current;
return true;
}
}
System.out.println("cloud not find the key: " + data);
return false;
}
// delete first
public Link deleteFirst() {
Link temp = first;
if (first.next == null) {
last = null;
} else {
first.next.previous = null;
}
first = first.next;
return temp;
}
// delete last
public Link deleteLast() {
Link temp = last;
if (first.next == null) {
first = null;
} else {
last.previous.next = null;
}
last = last.previous;
return temp;
}
// delete key
public Link deleteKey(int data) {
Link current = first;
while (current != null) {
if (current.getData() != data) {
current = current.next;
} else {
if (current == first) {
first = first.next;
} else {
current.previous.next = current.next;
}
if (current == last) {
last = last.previous;
} else {
current.next.previous = current.previous;
}
return current;
}
}
System.out.println("cloud not find the key: " + data + ", delete failed!");
return null;
}
// display forward
public void displayForward() {
System.out.println("List (first-->last): ");
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println();
}
// display backward
public void displayBackward() {
System.out.println("List (last-->first): ");
Link current = last;
while (current != null) {
current.displayLink();
current = current.previous;
}
System.out.println();
}
}
這是一個(gè)雙向鏈表猴贰，同時(shí)也是雙端列表对雪，可以從前向后或者從后向前遍歷，也可以在鏈表的任何地方插入或是刪除節(jié)點(diǎn)米绕，在實(shí)現(xiàn)這些方法時(shí)瑟捣，需要修改與插入或刪除節(jié)點(diǎn)有關(guān)系的前后四個(gè)引用馋艺，且還需要考慮first與last、列表為空或者僅有一個(gè)元素的特殊情況迈套，可以通過(guò)畫(huà)圖來(lái)加深理解捐祠。
效率與總結(jié)
以上我們介紹并實(shí)現(xiàn)了單向鏈表、雙端鏈表桑李、有序鏈表和雙向鏈表踱蛀，接下來(lái)我們來(lái)討論一下這些鏈表的效率。
鏈表與數(shù)組作為通用數(shù)據(jù)結(jié)構(gòu)經(jīng)常被拿來(lái)做對(duì)比芙扎，以鏈表和數(shù)組這兩個(gè)通用數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)的一些抽象數(shù)據(jù)模型星岗，比如java中的ArrayList與LinkedList填大，也經(jīng)常被拿出來(lái)作比較戒洼，總的來(lái)說(shuō)主要有兩大區(qū)別：
鏈表插入和刪除的效率高于數(shù)組，鏈表插入允华、刪除頭節(jié)點(diǎn)圈浇、尾節(jié)點(diǎn)的時(shí)間效率為O(1)，而在鏈表中間插入靴寂、刪某一節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(N)磷蜀，雖然與數(shù)組相同操作的時(shí)間復(fù)雜度相同，可是數(shù)組需要復(fù)制移動(dòng)元素位置來(lái)填補(bǔ)空洞百炬，所以鏈表的效率還是要優(yōu)于數(shù)組的褐隆，特別是復(fù)制時(shí)間占比較重的情況中。
數(shù)組則是隨機(jī)訪問(wèn)元素的效率要高于鏈表剖踊，可以通過(guò)數(shù)組下標(biāo)直接訪問(wèn)的到庶弃。鏈表比數(shù)組優(yōu)越的另一個(gè)重要因素就是，鏈表可以擴(kuò)展到所有可用的內(nèi)存空間德澈，且不用像數(shù)組一樣初始化容量歇攻，也不需要可以擴(kuò)容。另外當(dāng)一個(gè)數(shù)組對(duì)象需要一個(gè)連續(xù)的大內(nèi)存空間時(shí)梆造，會(huì)有幾率觸發(fā)jvm的GC去整理內(nèi)存空間以獲取一片連續(xù)的內(nèi)存缴守，而鏈表則沒(méi)有這方面的限制，所以在內(nèi)存的使用效率上镇辉，鏈表優(yōu)于數(shù)組屡穗。
正如以上所述，一般來(lái)說(shuō)忽肛，鏈表如果采用頭插法(或刪除)村砂，則時(shí)間復(fù)雜度均為O(1)，而如果是隨機(jī)插入或者向有序鏈表中插入的時(shí)間效率均為O(N)麻裁，因?yàn)樾枰业胶线m的位置箍镜；
有序鏈表可以在O(1)的時(shí)間返回或刪除最小或最大值源祈，如果一個(gè)應(yīng)用需要頻繁的返回最小值且不需要快速的插入時(shí)間，則可以選擇有序鏈表來(lái)實(shí)現(xiàn)色迂，如優(yōu)先級(jí)隊(duì)列香缺；
雙向鏈表由于兩端都可以插入、刪除和遍歷歇僧，所以可以用來(lái)做雙端隊(duì)列图张。
參考文章
《Data Structures & Algorithms in Java》 Robert Lafore著
