數(shù)據(jù)結(jié)構(gòu)（4）：鏈表的原理和實(shí)現(xiàn)

上、簡(jiǎn)單的單端鏈表

完整代碼向下拉

鏈表是一種常用的數(shù)據(jù)結(jié)構(gòu)，在插入和移除操作中有著優(yōu)秀的表現(xiàn)，同為數(shù)據(jù)結(jié)構(gòu)的數(shù)組哭暈，其實(shí)數(shù)組的訪問(wèn)效率比鏈表高多了有木有。

我們先看一下鏈表的樣子



有同學(xué)可能要說(shuō)了，這不就是我們生活中的交通工具——火車，沒(méi)錯(cuò)鏈表的結(jié)構(gòu)和下圖簡(jiǎn)直就是一個(gè)模子刻出來(lái)的。(咳咳，忽略這靈魂的畫法)



通過(guò)火車示意圖可以觀察到，火車由火車頭和n節(jié)車廂組成，每節(jié)車廂都與下一節(jié)車廂相連，能理解這句話，鏈表你就掌握一半了。

以小學(xué)掌握的物品分類知識(shí)來(lái)對(duì)上圖進(jìn)行面向?qū)ο蟪橄?，火車整體可以認(rèn)為是鏈表，火車又由車廂組成的，同樣可以理解鏈表是由節(jié)點(diǎn)組成的，鏈表起到了組合節(jié)點(diǎn)的作用。

1、創(chuàng)建節(jié)點(diǎn)(車廂)

車廂都有哪些特點(diǎn)呢？車廂能存放物品，車廂與下一節(jié)車廂相連。
public class Node { public Object data;//存放的數(shù)據(jù) public Node next;//指向下一個(gè)節(jié)點(diǎn)
public Node(Object value) { this.data = value; } //展示節(jié)點(diǎn)數(shù)據(jù) public void display()
{ System.out.print(data+" "); } }
2、創(chuàng)建鏈表（將車廂組合）

在現(xiàn)實(shí)中我們要想查看整個(gè)火車由一個(gè)十分暴力的方法，那就是找到火車頭，找到火車頭后沿著每節(jié)車廂向后查找就可以完整的查看整輛火車。
public class LinkList { private Node first;//第一個(gè)節(jié)點(diǎn) }
在代碼中 Node 類已經(jīng)聲明了指向下一個(gè)節(jié)點(diǎn)的屬性，所以只需要找到第一個(gè)節(jié)點(diǎn)，調(diào)用next屬性即可無(wú)限向后查找。

3、判斷鏈表是否為空

第一個(gè)節(jié)點(diǎn)為空即為鏈表為空
public boolean isEmpty() { return first == null; }
4、添加數(shù)據(jù)到鏈表的頭部

添加數(shù)據(jù)到鏈表頭部，就是將新節(jié)點(diǎn)的next指向原來(lái)的首節(jié)點(diǎn)，再將新節(jié)點(diǎn)標(biāo)記為first即可。
public void addFirst(Object value) { Node newNode = new Node(value);//創(chuàng)建新節(jié)點(diǎn) if
(isEmpty()) { first = newNode;//沒(méi)有節(jié)點(diǎn)時(shí)直接標(biāo)記為首節(jié)點(diǎn) } else { newNode.next =
first;//新節(jié)點(diǎn)next指向舊的首節(jié)點(diǎn) first = newNode; } }
5、移除首節(jié)點(diǎn)

并非真正意義上的移除，而是將first指向first.next的內(nèi)存地址，而原來(lái)的first會(huì)被垃圾回收器回收。


public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first;
first = first.next; return tmp; }
6、查看鏈表

由于鏈表中的每個(gè)節(jié)點(diǎn)都有變量指向下一個(gè)節(jié)點(diǎn)，所有可以使用循環(huán)遞進(jìn)獲取下一個(gè)節(jié)點(diǎn)實(shí)現(xiàn)遍歷的效果。
public void display() { Node current = first;//先從首節(jié)點(diǎn)開(kāi)始 while (current != null)
{ current.display();//節(jié)點(diǎn)不為空，則打印該節(jié)點(diǎn)信息 current =
current.next;//獲取當(dāng)前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)重新放入current中 System.out.println(); } }
7、根據(jù)值查找鏈表中的節(jié)點(diǎn)

需要遍歷節(jié)點(diǎn)，將每個(gè)節(jié)點(diǎn)的值都與要查找的值進(jìn)行比對(duì)，如果值不相等就一直循環(huán)，直到最后一個(gè)節(jié)點(diǎn)為空時(shí)表示沒(méi)有查到。
public Node find(Object value) { if (isEmpty()) { return null; } Node current
= first; while (current.data != value) { if (current.next==null){ return null;
} current = current.next; } return current; }
8、根據(jù)值移除節(jié)點(diǎn)

移除時(shí)同樣遍歷所有節(jié)點(diǎn)，但要保存查到節(jié)點(diǎn)的之前節(jié)點(diǎn)(previous)，如果查到的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)，直接移除第一個(gè)，否則就將前一個(gè)節(jié)點(diǎn)指向要移除節(jié)點(diǎn)的下一個(gè)。


public Node remove(Object value){ if (isEmpty()) { return null; } Node current
= first; Node previous = first; while (current.data != value) { if
(current.next==null){ return null; } previous = current; current =
current.next; } if (current==first){ removeFirst(); }else{
previous.next=current.next; } return current; }
9、完整代碼
public class LinkList { private Node first;//第一個(gè)節(jié)點(diǎn) public void addFirst(Object
value) { Node newNode = new Node(value);//創(chuàng)建新節(jié)點(diǎn) if (isEmpty()) { first =
newNode;//沒(méi)有節(jié)點(diǎn)時(shí)直接標(biāo)記為首節(jié)點(diǎn) } else { newNode.next = first;//新節(jié)點(diǎn)next指向舊的首節(jié)點(diǎn) first =
newNode; } } public Node removeFirst() { if (isEmpty()) { return null; } Node
tmp = first; first = first.next; return tmp; } public void display() { Node
current = first;//先從首節(jié)點(diǎn)開(kāi)始 while (current != null) {
current.display();//節(jié)點(diǎn)不為空，則打印該節(jié)點(diǎn)信息 current =
current.next;//獲取當(dāng)前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)重新放入current中 System.out.println(); } } public Node
find(Object value) { if (isEmpty()) { return null; } Node current = first;
while (current.data != value) { if (current.next==null){ return null; } current
= current.next; } return current; } public Node remove(Object value){ if
(isEmpty()) { return null; } Node current = first; Node previous = first; while
(current.data != value) { if (current.next==null){ return null; } previous =
current; current = current.next; } if (current==first){ removeFirst(); }else{
previous.next=current.next; } return current; } public boolean isEmpty() {
return first == null; } public static void main(String[] args) { LinkList
linkList = new LinkList(); linkList.addFirst("a"); linkList.addFirst("b");
System.out.println("-0---"); linkList.remove("a"); linkList.display(); } public
class Node { public Object data;//存放的數(shù)據(jù) public Node next;//指向下一個(gè)節(jié)點(diǎn) public
Node(Object value) { this.data = value; } //展示節(jié)點(diǎn)數(shù)據(jù) public void display() {
System.out.print(data+" "); } } }
單端鏈表還是有一些不足，比如我們要操作最后一個(gè)節(jié)點(diǎn)需要遍歷整個(gè)鏈表，下一節(jié)咱們實(shí)現(xiàn)雙端鏈表，提高操作最后一個(gè)節(jié)點(diǎn)的效率。

中、操作更簡(jiǎn)單的雙端鏈表

上節(jié)文章中咱們了解了鏈表的結(jié)構(gòu)及原理，但是還有些美中不足的地方，就是無(wú)法快速的訪問(wèn)鏈表中的最后一個(gè)節(jié)點(diǎn)。
在這節(jié)文章中咱們來(lái)解決這個(gè)問(wèn)題，一起來(lái)吧。

首先先看如何快速訪問(wèn)尾節(jié)點(diǎn)，其實(shí)這個(gè)可以通過(guò)一個(gè)變量指向尾節(jié)點(diǎn)，在做插入、刪除時(shí)更新尾節(jié)點(diǎn)即可。



1、創(chuàng)建節(jié)點(diǎn)

節(jié)點(diǎn)用于存儲(chǔ)數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)相連
public class Node { public Object data;//存放的數(shù)據(jù) public Node next;//指向下一個(gè)節(jié)點(diǎn)
public Node(Object value) { this.data = value; } //展示節(jié)點(diǎn)數(shù)據(jù) public void display()
{ System.out.print(data + " "); } }
2、創(chuàng)建鏈表

操作節(jié)點(diǎn)和指向首尾兩個(gè)節(jié)點(diǎn)
public class DoubleEndLinkList { private Node first;//第一個(gè)節(jié)點(diǎn) private Node
last;//最后一個(gè)節(jié)點(diǎn) }
3、向前添加節(jié)點(diǎn)

如果加入的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)是首節(jié)點(diǎn)同時(shí)也是尾節(jié)點(diǎn)。如果已經(jīng)有節(jié)點(diǎn)則讓新節(jié)點(diǎn)指向原來(lái)的首節(jié)點(diǎn)，讓首節(jié)點(diǎn)指向新節(jié)點(diǎn)。


public void addFirst(Object value) { Node newNode = new Node(value); if
(isEmpty()) { //如果為空，尾節(jié)點(diǎn)指向此節(jié)點(diǎn) last = newNode; } //更替新節(jié)點(diǎn) newNode.next = first;
first = newNode; }
4、向后添加節(jié)點(diǎn)

和向前添加相反，因?yàn)殒湵碇衛(wèi)ast始終指向最后一個(gè)節(jié)點(diǎn)，所以操作last節(jié)點(diǎn)。
public void addLast(Object value) { Node newNode = new Node(value); if
(isEmpty()) { //如果為空，首節(jié)點(diǎn)和尾節(jié)點(diǎn)指向此節(jié)點(diǎn) first = newNode; last = newNode; return; }
//更替尾節(jié)點(diǎn) last.next = newNode; last = newNode; }
5、移除首節(jié)點(diǎn)

移除首節(jié)點(diǎn)時(shí)將首節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)標(biāo)記為首節(jié)點(diǎn)即可，直到首節(jié)點(diǎn)與尾節(jié)點(diǎn)相同時(shí)(這時(shí)也意味這只剩一個(gè)節(jié)點(diǎn))不再需要輪替，直接將首尾節(jié)點(diǎn)設(shè)置為null。
public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first;
//僅剩一個(gè)節(jié)點(diǎn)時(shí) if (first == last) { first = null; last = null; return tmp; }
//無(wú)論有多少個(gè)節(jié)點(diǎn)都會(huì)輪替到first==last first = first.next; return tmp; }
6、完整代碼
package com.jikedaquan.datastruct; public class DoubleEndLinkList { private
Node first;//第一個(gè)節(jié)點(diǎn) private Node last;//最后一個(gè)節(jié)點(diǎn) public void addFirst(Object
value) { Node newNode = new Node(value); if (isEmpty()) { //如果為空，尾節(jié)點(diǎn)指向此節(jié)點(diǎn) last
= newNode; } //更替新節(jié)點(diǎn) newNode.next = first; first = newNode; } public void
addLast(Object value) { Node newNode = new Node(value); if (isEmpty()) {
//如果為空，首節(jié)點(diǎn)和尾節(jié)點(diǎn)指向此節(jié)點(diǎn) first = newNode; last = newNode; return; } //更替尾節(jié)點(diǎn)
last.next = newNode; last = newNode; } public Node removeFirst() { if
(isEmpty()) { return null; } Node tmp = first; //僅剩一個(gè)節(jié)點(diǎn)時(shí) if (first == last) {
first = null; last = null; return tmp; } //無(wú)論有多少個(gè)節(jié)點(diǎn)都會(huì)輪替到first==last first =
first.next; return tmp; } public void display() { Node current =
first;//先從首節(jié)點(diǎn)開(kāi)始 while (current != null) { current.display();//節(jié)點(diǎn)不為空，則打印該節(jié)點(diǎn)信息
current = current.next;//獲取當(dāng)前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)重新放入current中 System.out.println(); } }
public boolean isEmpty() { return first == null; } public static void
main(String[] args) { DoubleEndLinkList linkList = new DoubleEndLinkList();
linkList.addLast("e"); linkList.addFirst("a"); linkList.addFirst("b");
linkList.removeFirst(); linkList.removeFirst(); linkList.removeFirst();
linkList.display(); System.out.println("-0---"); linkList.addLast("c");
linkList.addFirst("1"); linkList.display(); System.out.println("-0---");
linkList.removeFirst(); linkList.removeFirst(); linkList.addLast(9);
linkList.display(); System.out.println("-0---"); linkList.display(); } public
class Node { public Object data;//存放的數(shù)據(jù) public Node next;//指向下一個(gè)節(jié)點(diǎn) public
Node(Object value) { this.data = value; } //展示節(jié)點(diǎn)數(shù)據(jù) public void display() {
System.out.print(data + " "); } } }

雙端鏈表能同時(shí)向首尾添加新元素，用雙端鏈表實(shí)現(xiàn)隊(duì)列也成為了可能(比用數(shù)組實(shí)現(xiàn)效率更高)，但是如何快速移除最后一個(gè)元素(因?yàn)椴荒芸焖俚淖匪葜暗脑?成為了一個(gè)新難題，請(qǐng)看下一節(jié)
雙向鏈表！

下、方便高效的雙向鏈表

單向鏈表每個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)，而雙向鏈表是指每個(gè)節(jié)點(diǎn)還指向了前一個(gè)節(jié)點(diǎn)。這樣做的好處是可以快速的移除最后一個(gè)元素。



1、保存數(shù)據(jù)的節(jié)點(diǎn)

節(jié)點(diǎn)除了指向下一個(gè)節(jié)點(diǎn)還要指向前一個(gè)節(jié)點(diǎn)
public class Node { public Object data;//存放的數(shù)據(jù) public Node previous;//指向前一個(gè)節(jié)點(diǎn)
public Node next;//指向下一個(gè)節(jié)點(diǎn) public Node(Object value) { this.data = value; }
//展示節(jié)點(diǎn)數(shù)據(jù) public void display() { System.out.print(data + " "); } }
2、創(chuàng)建鏈表指向首元素和尾元素
public class TwoWayLinkList { private Node first; private Node last; }
3、向前添加元素

考慮到鏈表為空時(shí)，首元素和尾元素均指向新元素。
public void addFirst(Object value) { Node newNode = new Node(value); if
(isEmpty()) { last = newNode; first = newNode; return; } //新首元素指向舊首元素
newNode.next = first; //舊首元素的前一個(gè)指向新首元素 first.previous = newNode; //更替首元素 first
= newNode; }
4、向后添加元素

由于是雙向的，所以之前的引用和之后的引用都要更新
public void addLast(Object value) { Node newNode = new Node(value); if
(isEmpty()) { first = newNode; last = newNode; return; } //更替尾元素
newNode.previous = last; last.next = newNode; last = newNode; }
5、移除首元素

如果過(guò)已是最后一個(gè)元素，直接將首尾設(shè)置為null，其他情況進(jìn)行輪替。


public Node removeFirst() { Node removeNode = first; //如果當(dāng)前已是最后一個(gè)元素 if
(first.next == null) { first = null; last = null; return removeNode; }
//首元素指向下一個(gè)元素 first = first.next; //將新首元素指向的之前的元素設(shè)為null first.previous = null;
return removeNode; }
6、移除尾元素

和移除首元素類似


public Node removeLast() { Node removeNode = last; if (last.previous == null)
{ first = null; last = null; return null; } //尾元素指向舊尾元素之前的元素 last =
last.previous; //將新尾元素的下一個(gè)元素設(shè)為null last.next = null; return removeNode; }
7、根據(jù)值移除節(jié)點(diǎn)

從第一個(gè)元素開(kāi)始遍歷，如果值不相同就一直遍歷，沒(méi)有元素匹配返回null，有元素相同時(shí)將之前的元素指向當(dāng)前元素的下一個(gè)，將當(dāng)前元素下一個(gè)指向前一個(gè)。
public Node remove(Object value) { if (isEmpty()){ return null; } Node current
= first; while (current.data != value) { if (current.next == null) { return
null; } current = current.next; } current.previous.next = current.next;
current.next.previous = current.previous; return current; }
8、完整代碼
package com.jikedaquan.datastruct; public class TwoWayLinkList { private Node
first; private Node last; public void addFirst(Object value) { Node newNode =
new Node(value); if (isEmpty()) { last = newNode; first = newNode; return; }
//新首元素指向舊首元素 newNode.next = first; //舊首元素的前一個(gè)指向新首元素 first.previous = newNode;
//更替首元素 first = newNode; } public void addLast(Object value) { Node newNode =
new Node(value); if (isEmpty()) { first = newNode; last = newNode; return; }
//更替尾元素 newNode.previous = last; last.next = newNode; last = newNode; } public
Node removeFirst() { Node removeNode = first; //如果當(dāng)前已是最后一個(gè)元素 if (first.next ==
null) { first = null; last = null; return removeNode; } //首元素指向下一個(gè)元素 first =
first.next; //將新首元素指向的之前的元素設(shè)為null first.previous = null; return removeNode; }
public Node removeLast() { Node removeNode = last; if (last.previous == null) {
first = null; last = null; return null; } //尾元素指向舊尾元素之前的元素 last =
last.previous; //將新尾元素的下一個(gè)元素設(shè)為null last.next = null; return removeNode; }
public Node remove(Object value) { if (isEmpty()){ return null; } Node current
= first; while (current.data != value) { if (current.next == null) { return
null; } current = current.next; } current.previous.next = current.next;
current.next.previous = current.previous; return current; } public boolean
isEmpty() { return first == null; } public void display() { Node current =
first;//先從首節(jié)點(diǎn)開(kāi)始 while (current != null) { current.display();//節(jié)點(diǎn)不為空，則打印該節(jié)點(diǎn)信息
current = current.next;//獲取當(dāng)前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)重新放入current中 } System.out.println(); }
public static void main(String[] args) { TwoWayLinkList linkList = new
TwoWayLinkList(); linkList.addFirst("b"); linkList.addFirst("a");
linkList.display(); System.out.println("======"); while (!linkList.isEmpty()) {
linkList.removeFirst(); linkList.display(); } System.out.println("======");
linkList.addLast("c"); linkList.addLast("d"); linkList.display();
System.out.println("======"); while (!linkList.isEmpty()) {
linkList.removeLast(); linkList.display(); } System.out.println("======");
linkList.addFirst("e"); linkList.addLast("f"); linkList.addLast("g");
linkList.display(); System.out.println("======"); linkList.remove("f");
System.out.println("======"); linkList.display(); } public class Node { public
Object data;//存放的數(shù)據(jù) public Node previous;//指向前一個(gè)節(jié)點(diǎn) public Node next;//指向下一個(gè)節(jié)點(diǎn)
public Node(Object value) { this.data = value; } //展示節(jié)點(diǎn)數(shù)據(jù) public void display()
{ System.out.print(data + " "); } } }
9、總結(jié)


鏈表是節(jié)點(diǎn)中通過(guò)變量指向前一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)實(shí)現(xiàn)了相連，鏈表在移除節(jié)點(diǎn)、首尾添加節(jié)點(diǎn)有著優(yōu)越的性能，時(shí)間復(fù)雜度O(1)。數(shù)組在做同等操作需要O(n)，但在訪問(wèn)元素上優(yōu)于鏈表，空間復(fù)雜度也小于鏈表，應(yīng)在不同的場(chǎng)景選用不同的結(jié)構(gòu)。
當(dāng)然這些數(shù)據(jù)結(jié)構(gòu)也不需要我們?nèi)?shí)現(xiàn)的，java語(yǔ)言中已經(jīng)有對(duì)應(yīng)的實(shí)現(xiàn)。

• ? 上一篇： JavaScript基本數(shù)據(jù)類型分析
• ? 下一篇： 如何使用curl訪問(wèn)k8s的apiserver