揭開鏈表的真面目

鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，鏈表是由一連串的結(jié)點(diǎn)組成，這個(gè)節(jié)點(diǎn)就是鏈結(jié)點(diǎn)，每個(gè)鏈結(jié)點(diǎn)都由數(shù)據(jù)域和指針域兩部分組成。

使用鏈表結(jié)構(gòu)可以克服數(shù)組結(jié)構(gòu)需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大。

鏈表比較好的一種理解是：將鏈表看成一個(gè)火車，每個(gè)車廂之間都是相互連接的，只要找到火車頭，就可以找到具體的車身。鏈表也是，我們只關(guān)心它的頭。

一 單向鏈表

1.1 單向鏈表原理圖

單向鏈表的一個(gè)鏈結(jié)點(diǎn)包含數(shù)據(jù)域和下一個(gè)鏈結(jié)點(diǎn)的指針。頭結(jié)點(diǎn)也包含數(shù)據(jù)域和指針域，但是一般為了方便查找，頭節(jié)點(diǎn)不寫數(shù)據(jù)，最后一個(gè)結(jié)點(diǎn)的指針指向空。

1.2 實(shí)現(xiàn)單向鏈表的存儲(chǔ)等操作

創(chuàng)建一個(gè)鏈結(jié)點(diǎn)的實(shí)體類

public?class?Node?{

????//?數(shù)據(jù)域
????public?long?data;
????//?指針域
????public?Node?next;

????public?Node(long?value){
????????this.data?=?value;
????}
}

1.2.1 插入一個(gè)節(jié)點(diǎn)

在頭節(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)，第一步需要將新插入的結(jié)點(diǎn)指向頭結(jié)點(diǎn)指向的結(jié)點(diǎn)，第二步將頭結(jié)點(diǎn)指向新插入的結(jié)點(diǎn)。插入結(jié)點(diǎn)只需要改變一個(gè)引用，所以復(fù)雜度為O(1)。

public?class?LinkList?{

????private?Node?head;
????/**
?????*?在頭節(jié)點(diǎn)之后插入一個(gè)節(jié)點(diǎn)
?????*/
????public?void?insertFirst(long?value){
????????Node?node?=?new?Node(value);
????????node.next?=?head;
????????head?=?node;
????}
}

1.2.2 頭結(jié)點(diǎn)后刪除一個(gè)結(jié)點(diǎn)

在頭結(jié)點(diǎn)后刪除一個(gè)結(jié)點(diǎn)，就是讓頭結(jié)點(diǎn)指向這個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。復(fù)雜度也是O(1)。

public?Node?deleteFirst(){
????Node?tmp?=?head;
????head?=?tmp.next;
????return?tmp;
}

1.2.3 根據(jù)數(shù)據(jù)域查找結(jié)點(diǎn)

查找需要比對(duì)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)，理論上查找一個(gè)結(jié)點(diǎn)平均需要N/2次，所以復(fù)雜度為O(N)。

public?Node?find(long?value){

????Node?current?=?head;
????while?(current.data?!=?value){
????????if(current.next?==?null){
????????????return?null;
????????}
????????current?=?current.next;
????}
????return?current;
}

1.2.4 根據(jù)數(shù)據(jù)與刪除結(jié)點(diǎn)

查找需要比對(duì)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)，理論上刪除一個(gè)結(jié)點(diǎn)平均需要N/2次，所以復(fù)雜度為O(N)。

public?Node?delete(int?value){
????Node?current?=?head;
????//?當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
????Node?pre?=?head;
????while?(current.data?!=?value){
????????if(current.next?==?null){
????????????return?null;
????????}
????????pre?=?current;
????????current?=?current.next;
????}
????if(current?==?head){
????????head?=?head.next;
????}else{
????????pre.next?=?current.next;
????}
????return?current;
}

二 雙端鏈表

2.1 雙端鏈表原理圖

雙端鏈表是在單向鏈表的基礎(chǔ)上，頭結(jié)點(diǎn)增加了一個(gè)尾結(jié)點(diǎn)的引用。

2.2 實(shí)現(xiàn)雙端鏈表的存儲(chǔ)等操作

2.2.1 從頭部插入結(jié)點(diǎn)

如果鏈表為空，則設(shè)置尾結(jié)點(diǎn)就是新添加的結(jié)點(diǎn)。復(fù)雜度為O(1)。

public?class?FirstLastLinkList?{

????private?Node?first;
????private?Node?last;
????/**
?????*?在頭結(jié)點(diǎn)之后插入一個(gè)節(jié)點(diǎn)
?????*/
????public?void?insertFirst(long?value){
????????Node?node?=?new?Node(value);
????????if(first?==?null){
????????????last?=?node;
????????}
????????node.next?=?first;
????????first?=?node;
????}
}

2.2.2 從尾部插入結(jié)點(diǎn)

如果鏈表為空，則設(shè)置頭結(jié)點(diǎn)為新添加的結(jié)點(diǎn)，否則設(shè)置尾結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)為新添加的結(jié)點(diǎn)。復(fù)雜度為O(1)。

public?void?insertLast(long?value){
????Node?node?=?new?Node(value);
????if(first?==?null){
????????first?=?node;
????}else{
????????last.next?=?node;
????}
????last?=?node;
}

2.2.3 從頭部進(jìn)行刪除

判斷頭結(jié)點(diǎn)是否有下一個(gè)結(jié)點(diǎn)，如果沒有則設(shè)置尾結(jié)點(diǎn)為null，復(fù)雜度為O(1)。

public?Node?deleteFirst(){

????Node?tmp?=?first;
????if(first.next?==?null){
????????last?=?null;
????}
????first?=?tmp.next;
????return?tmp;
}

三 雙向鏈表

3.1 雙向鏈表原理圖

每個(gè)結(jié)點(diǎn)除了保存對(duì)后一個(gè)結(jié)點(diǎn)的引用外，還保存著對(duì)前一個(gè)結(jié)點(diǎn)的引用。

3.2 實(shí)現(xiàn)雙向鏈表的存儲(chǔ)等操作

鏈結(jié)點(diǎn)實(shí)體類

public?class?Node?{

????//?數(shù)據(jù)域
????public?long?data;
????//?后一個(gè)結(jié)點(diǎn)指針域
????public?Node?next;
????//?前一個(gè)結(jié)點(diǎn)指針域
????public?Node?prev;

????public?Node(long?value){
????????this.data?=?value;
????}
}

3.2.1 從頭部插入結(jié)點(diǎn)

如果鏈表為空，則設(shè)置尾結(jié)點(diǎn)為新添加的結(jié)點(diǎn)，如果不為空，還需要設(shè)置頭結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)為新添加的結(jié)點(diǎn)。插入結(jié)點(diǎn)只需要改變兩個(gè)結(jié)點(diǎn)的引用，所以復(fù)雜度為O(1)。

public?class?DoubleLinkList?{

????private?Node?first;
????private?Node?last;

????/**
?????*?在頭結(jié)點(diǎn)之后插入一個(gè)節(jié)點(diǎn)
?????*/
????public?void?insertFirst(long?value){
????????Node?node?=?new?Node(value);
????????if(first?==?null){
????????????last?=?node;
????????}?else{
????????????first.prev?=?node;
????????}
????????node.next?=?first;
????????first?=?node;
????}
}

3.2.2 從尾部插入結(jié)點(diǎn)

如果鏈表為空，則設(shè)置頭結(jié)點(diǎn)為新添加的結(jié)點(diǎn)，否則設(shè)置尾結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)為新添加的結(jié)點(diǎn)。同時(shí)設(shè)置新添加的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)為尾結(jié)點(diǎn)。插入結(jié)點(diǎn)只需要改變1個(gè)結(jié)點(diǎn)的引用，所以復(fù)雜度為O(1)。

public?void?insertLast(long?value){
????Node?node?=?new?Node(value);
????if(first?==?null){
????????first?=?node;
????}else{
????????last.next?=?node;
????????node.prev?=?last;
????}
????last?=?node;
}

3.2.3 從頭部刪除結(jié)點(diǎn)

判斷頭結(jié)點(diǎn)是否有下一個(gè)結(jié)點(diǎn)，如果沒有則設(shè)置尾結(jié)點(diǎn)為null，否則設(shè)置頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的prev為null。復(fù)雜度也為O(1)。

public?Node?deleteFirst(){

????Node?tmp?=?first;
????if(first.next?==?null){
????????last?=?null;
????}else{
????????first.next.prev?=?null;
????}
????first?=?tmp.next;
????return?tmp;
}

3.2.4 從尾部刪除結(jié)點(diǎn)

如果頭結(jié)點(diǎn)后沒有其他結(jié)點(diǎn)，則設(shè)置頭結(jié)點(diǎn)為null，否則設(shè)置尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的next為null，設(shè)置尾結(jié)點(diǎn)為前一個(gè)結(jié)點(diǎn)。復(fù)雜度為O(1)。

public?Node?deleteLast(){

????Node?tmp?=?last;?
????if(first.next?==?null){
????????first?=?null;
????}else{
????????last.prev.next?=?null;??
????}
????last?=?last.prev;
????return?last;
}

四 總結(jié)

鏈表包含一個(gè)頭結(jié)點(diǎn)和多個(gè)結(jié)點(diǎn)，頭結(jié)點(diǎn)包含一個(gè)引用，這個(gè)引用通常叫做first，它指向鏈表的第一個(gè)鏈結(jié)點(diǎn)。結(jié)點(diǎn)的next為null，則意味著這個(gè)結(jié)點(diǎn)是尾結(jié)點(diǎn)。與數(shù)組相比，鏈表更適合做插入、刪除操作，而查找操作的復(fù)雜度更高。還有一個(gè)優(yōu)勢(shì)就是鏈表不需要初始化內(nèi)存大小，不會(huì)造成內(nèi)存溢出（數(shù)組中插入元素個(gè)數(shù)超過(guò)數(shù)組長(zhǎng)度）或內(nèi)存浪費(fèi)（聲明的數(shù)組長(zhǎng)度比實(shí)際放的元素長(zhǎng)）。