鏈表與數(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著