前面博客我們在講解數組中，知道數組作為數據存儲結構有一定的缺陷。在無序數組中，搜索性能差，在有序數組中，插入效率又很低，而且這兩種數組的刪除效率都很低，并且數組在創(chuàng)建后，其大小是固定了，設置的過大會造成內存的浪費，過小又不能滿足數據量的存儲。

本篇博客我們將講解一種新型的數據結構——鏈表。我們知道數組是一種通用的數據結構，能用來實現棧、隊列等很多數據結構。而鏈表也是一種使用廣泛的通用數據結構，它也可以用來作為實現棧、隊列等數據結構的基礎，基本上除非需要頻繁的通過下標來隨機訪問各個數據，否則很多使用數組的地方都可以用鏈表來代替。

但是我們需要說明的是，鏈表是不能解決數據存儲的所有問題的，它也有它的優(yōu)點和缺點。本篇博客我們介紹幾種常見的鏈表，分別是單向鏈表、雙端鏈表、有序鏈表、雙向鏈表以及有迭代器的鏈表。并且會講解一下抽象數據類型(ADT)的思想，如何用 ADT 描述棧和隊列，如何用鏈表代替數組來實現棧和隊列。

1、鏈表(Linked List)

鏈表通常由一連串節(jié)點組成，每個節(jié)點包含任意的實例數據(data fields)和一或兩個用來指向上一個/或下一個節(jié)點的位置的鏈接("links")

鏈表(Linked list)是一種常見的基礎數據結構，是一種線性表，但是并不會按線性的順序存儲數據，而是在每一個節(jié)點里存到下一個節(jié)點的指針(Pointer)。

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

2、單向鏈表(Single-Linked List)

單鏈表是鏈表中結構最簡單的。一個單鏈表的節(jié)點(Node)分為兩個部分，第一個部分(data)保存或者顯示關于節(jié)點的信息，另一個部分存儲下一個節(jié)點的地址。最后一個節(jié)點存儲地址的部分指向空值。

單向鏈表只可向一個方向遍歷，一般查找一個節(jié)點的時候需要從第一個節(jié)點開始每次訪問下一個節(jié)點，一直訪問到需要的位置。而插入一個節(jié)點，對于單向鏈表，我們只提供在鏈表頭插入，只需要將當前插入的節(jié)點設置為頭節(jié)點，next指向原頭節(jié)點即可。刪除一個節(jié)點，我們將該節(jié)點的上一個節(jié)點的next指向該節(jié)點的下一個節(jié)點。

在表頭增加節(jié)點：

刪除節(jié)點：

①、單向鏈表的具體實現

1 packagecom.ys.datastructure;2

3 public classSingleLinkedList {4 private int size;//鏈表節(jié)點的個數

5 private Node head;//頭節(jié)點

6

7 publicSingleLinkedList(){8 size = 0;9 head = null;10 }11

12 //鏈表的每個節(jié)點類

13 private classNode{14 private Object data;//每個節(jié)點的數據

15 private Node next;//每個節(jié)點指向下一個節(jié)點的連接

16

17 publicNode(Object data){18 this.data =data;19 }20 }21

22 //在鏈表頭添加元素

23 publicObject addHead(Object obj){24 Node newHead = newNode(obj);25 if(size == 0){26 head =newHead;27 }else{28 newHead.next =head;29 head =newHead;30 }31 size++;32 returnobj;33 }34

35 //在鏈表頭刪除元素

36 publicObject deleteHead(){37 Object obj =head.data;38 head =head.next;39 size--;40 returnobj;41 }42

43 //查找指定元素，找到了返回節(jié)點Node，找不到返回null

44 publicNode find(Object obj){45 Node current =head;46 int tempSize =size;47 while(tempSize > 0){48 if(obj.equals(current.data)){49 returncurrent;50 }else{51 current =current.next;52 }53 tempSize--;54 }55 return null;56 }57

58 //刪除指定的元素，刪除成功返回true

59 public booleandelete(Object value){60 if(size == 0){61 return false;62 }63 Node current =head;64 Node previous =head;65 while(current.data !=value){66 if(current.next == null){67 return false;68 }else{69 previous =current;70 current =current.next;71 }72 }73 //如果刪除的節(jié)點是第一個節(jié)點

74 if(current ==head){75 head =current.next;76 size--;77 }else{//刪除的節(jié)點不是第一個節(jié)點

78 previous.next =current.next;79 size--;80 }81 return true;82 }83

84 //判斷鏈表是否為空

85 public booleanisEmpty(){86 return (size == 0);87 }88

89 //顯示節(jié)點信息

90 public voiddisplay(){91 if(size >0){92 Node node =head;93 int tempSize =size;94 if(tempSize == 1){//當前鏈表只有一個節(jié)點

95 System.out.println("["+node.data+"]");96 return;97 }98 while(tempSize>0){99 if(node.equals(head)){100 System.out.print("["+node.data+"->");101 }else if(node.next == null){102 System.out.print(node.data+"]");103 }else{104 System.out.print(node.data+"->");105 }106 node =node.next;107 tempSize--;108 }109 System.out.println();110 }else{//如果鏈表一個節(jié)點都沒有，直接打印[]

111 System.out.println("[]");112 }113

114 }115

116 }

View Code

測試：

1 @Test2 public voidtestSingleLinkedList(){3 SingleLinkedList singleList = newSingleLinkedList();4 singleList.addHead("A");5 singleList.addHead("B");6 singleList.addHead("C");7 singleList.addHead("D");8 //打印當前鏈表信息

9 singleList.display();10 //刪除C

11 singleList.delete("C");12 singleList.display();13 //查找B

14 System.out.println(singleList.find("B"));15 }

View Code

打印結果：

②、用單向鏈表實現棧

棧的pop()方法和push()方法，對應于鏈表的在頭部刪除元素deleteHead()以及在頭部增加元素addHead()。

1 packagecom.ys.datastructure;2

3 public classStackSingleLink {4 privateSingleLinkedList link;5

6 publicStackSingleLink(){7 link = newSingleLinkedList();8 }9

10 //添加元素

11 public voidpush(Object obj){12 link.addHead(obj);13 }14

15 //移除棧頂元素

16 publicObject pop(){17 Object obj =link.deleteHead();18 returnobj;19 }20

21 //判斷是否為空

22 public booleanisEmpty(){23 returnlink.isEmpty();24 }25

26 //打印棧內元素信息

27 public voiddisplay(){28 link.display();29 }30

31 }

View Code

4、雙端鏈表

對于單項鏈表，我們如果想在尾部添加一個節(jié)點，那么必須從頭部一直遍歷到尾部，找到尾節(jié)點，然后在尾節(jié)點后面插入一個節(jié)點。這樣操作很麻煩，如果我們在設計鏈表的時候多個對尾節(jié)點的引用，那么會簡單很多。

注意和后面將的雙向鏈表的區(qū)別！！！

①、雙端鏈表的具體實現

1 packagecom.ys.link;2

3 public classDoublePointLinkedList {4 private Node head;//頭節(jié)點

5 private Node tail;//尾節(jié)點

6 private int size;//節(jié)點的個數

7

8 private classNode{9 privateObject data;10 privateNode next;11

12 publicNode(Object data){13 this.data =data;14 }15 }16

17 publicDoublePointLinkedList(){18 size = 0;19 head = null;20 tail = null;21 }22

23 //鏈表頭新增節(jié)點

24 public voidaddHead(Object data){25 Node node = newNode(data);26 if(size == 0){//如果鏈表為空，那么頭節(jié)點和尾節(jié)點都是該新增節(jié)點

27 head =node;28 tail =node;29 size++;30 }else{31 node.next =head;32 head =node;33 size++;34 }35 }36

37 //鏈表尾新增節(jié)點

38 public voidaddTail(Object data){39 Node node = newNode(data);40 if(size == 0){//如果鏈表為空，那么頭節(jié)點和尾節(jié)點都是該新增節(jié)點

41 head =node;42 tail =node;43 size++;44 }else{45 tail.next =node;46 tail =node;47 size++;48 }49 }50

51 //刪除頭部節(jié)點，成功返回true，失敗返回false

52 public booleandeleteHead(){53 if(size == 0){//當前鏈表節(jié)點數為0

54 return false;55 }56 if(head.next == null){//當前鏈表節(jié)點數為1

57 head = null;58 tail = null;59 }else{60 head =head.next;61 }62 size--;63 return true;64 }65 //判斷是否為空

66 public booleanisEmpty(){67 return (size ==0);68 }69 //獲得鏈表的節(jié)點個數

70 public intgetSize(){71 returnsize;72 }73

74 //顯示節(jié)點信息

75 public voiddisplay(){76 if(size >0){77 Node node =head;78 int tempSize =size;79 if(tempSize == 1){//當前鏈表只有一個節(jié)點

80 System.out.println("["+node.data+"]");81 return;82 }83 while(tempSize>0){84 if(node.equals(head)){85 System.out.print("["+node.data+"->");86 }else if(node.next == null){87 System.out.print(node.data+"]");88 }else{89 System.out.print(node.data+"->");90 }91 node =node.next;92 tempSize--;93 }94 System.out.println();95 }else{//如果鏈表一個節(jié)點都沒有，直接打印[]

96 System.out.println("[]");97 }98 }99

100 }

View Code

②、用雙端鏈表實現隊列

1 packagecom.ys.link;2

3 public classQueueLinkedList {4

5 privateDoublePointLinkedList dp;6

7 publicQueueLinkedList(){8 dp = newDoublePointLinkedList();9 }10 public voidinsert(Object data){11 dp.addTail(data);12 }13

14 public voiddelete(){15 dp.deleteHead();16 }17

18 public booleanisEmpty(){19 returndp.isEmpty();20 }21

22 public intgetSize(){23 returndp.getSize();24 }25

26 public voiddisplay(){27 dp.display();28 }29

30 }

View Code

5、抽象數據類型(ADT)

在介紹抽象數據類型的時候，我們先看看什么是數據類型，聽到這個詞，在Java中我們可能首先會想到像 int,double這樣的詞，這是Java中的基本數據類型，一個數據類型會涉及到兩件事：

①、擁有特定特征的數據項

②、在數據上允許的操作

比如Java中的int數據類型，它表示整數，取值范圍為：-2147483648~2147483647，還能使用各種操作符，+、-、*、/ 等對其操作。數據類型允許的操作是它本身不可分離的部分，理解類型包括理解什么樣的操作可以應用在該類型上。

那么當年設計計算機語言的人，為什么會考慮到數據類型？

我們先看這樣一個例子，比如，大家都需要住房子，也都希望房子越大越好。但顯然，沒有錢，考慮房子沒有意義。于是就出現了各種各樣的商品房，有別墅的、復式的、錯層的、單間的……甚至只有兩平米的膠囊房間。這樣做的意義是滿足不同人的需要。

同樣，在計算機中，也存在相同的問題。計算1+1這樣的表達式不需要開辟很大的存儲空間，不需要適合小數甚至字符運算的內存空間。于是計算機的研究者們就考慮，要對數據進行分類，分出來多種數據類型。比如int，比如float。

雖然不同的計算機有不同的硬件系統(tǒng)，但實際上高級語言編寫者才不管程序運行在什么計算機上，他們的目的就是為了實現整形數字的運算，比如a+b等。他們才不關心整數在計算機內部是如何表示的，也不管CPU是如何計算的。于是我們就考慮，無論什么計算機、什么語言都會面臨類似的整數運算，我們可以考慮將其抽象出來。抽象是抽取出事物具有的普遍性本質，是對事物的一個概括，是一種思考問題的方式。

抽象數據類型(ADT)是指一個數學模型及定義在該模型上的一組操作。它僅取決于其邏輯特征，而與計算機內部如何表示和實現無關。比如剛才說得整型，各個計算機，不管大型機、小型機、PC、平板電腦甚至智能手機，都有“整型”類型，也需要整形運算，那么整型其實就是一個抽象數據類型。

更廣泛一點的，比如我們剛講解的棧和隊列這兩種數據結構，我們分別使用了數組和鏈表來實現，比如棧，對于使用者只需要知道pop()和push()方法或其它方法的存在以及如何使用即可，使用者不需要知道我們是使用的數組或是鏈表來實現的。

ADT的思想可以作為我們設計工具的理念，比如我們需要存儲數據，那么就從考慮需要在數據上實現的操作開始，需要存取最后一個數據項嗎？還是第一個？還是特定值的項？還是特定位置的項？回答這些問題會引出ADT的定義，只有完整的定義了ADT后，才應該考慮實現的細節(jié)。

這在我們Java語言中的接口設計理念是想通的。

6、有序鏈表

前面的鏈表實現插入數據都是無序的，在有些應用中需要鏈表中的數據有序，這稱為有序鏈表。

在有序鏈表中，數據是按照關鍵值有序排列的。一般在大多數需要使用有序數組的場合也可以使用有序鏈表。有序鏈表優(yōu)于有序數組的地方是插入的速度(因為元素不需要移動)，另外鏈表可以擴展到全部有效的使用內存，而數組只能局限于一個固定的大小中。

1 packagecom.ys.datastructure;2

3 public classOrderLinkedList {4 privateNode head;5

6 private classNode{7 private intdata;8 privateNode next;9

10 public Node(intdata){11 this.data =data;12 }13 }14

15 publicOrderLinkedList(){16 head = null;17 }18

19 //插入節(jié)點，并按照從小打到的順序排列

20 public void insert(intvalue){21 Node node = newNode(value);22 Node pre = null;23 Node current =head;24 while(current != null && value >current.data){25 pre =current;26 current =current.next;27 }28 if(pre == null){29 head =node;30 head.next =current;31 }else{32 pre.next =node;33 node.next =current;34 }35 }36

37 //刪除頭節(jié)點

38 public voiddeleteHead(){39 head =head.next;40 }41

42 public voiddisplay(){43 Node current =head;44 while(current != null){45 System.out.print(current.data+" ");46 current =current.next;47 }48 System.out.println("");49 }50

51 }

View Code

在有序鏈表中插入和刪除某一項最多需要O(N)次比較，平均需要O(N/2)次，因為必須沿著鏈表上一步一步走才能找到正確的插入位置，然而可以最快速度刪除最值，因為只需要刪除表頭即可，如果一個應用需要頻繁的存取最小值，且不需要快速的插入，那么有序鏈表是一個比較好的選擇方案。比如優(yōu)先級隊列可以使用有序鏈表來實現。

7、有序鏈表和無序數組組合排序

比如有一個無序數組需要排序，前面我們在講解冒泡排序、選擇排序、插入排序這三種簡單的排序時，需要的時間級別都是O(N2)。

現在我們講解了有序鏈表之后，對于一個無序數組，我們先將數組元素取出，一個一個的插入到有序鏈表中，然后將他們從有序鏈表中一個一個刪除，重新放入數組，那么數組就會排好序了。和插入排序一樣，如果插入了N個新數據，那么進行大概N2/4次比較。但是相對于插入排序，每個元素只進行了兩次排序，一次從數組到鏈表，一次從鏈表到數組，大概需要2*N次移動，而插入排序則需要N2次移動，

效率肯定是比前面講的簡單排序要高，但是缺點就是需要開辟差不多兩倍的空間，而且數組和鏈表必須在內存中同時存在，如果有現成的鏈表可以用，那么這種方法還是挺好的。

8、雙向鏈表

我們知道單向鏈表只能從一個方向遍歷，那么雙向鏈表它可以從兩個方向遍歷。

具體代碼實現：

1 packagecom.ys.datastructure;2

3 public classTwoWayLinkedList {4 private Node head;//表示鏈表頭

5 private Node tail;//表示鏈表尾

6 private int size;//表示鏈表的節(jié)點個數

7

8 private classNode{9 privateObject data;10 privateNode next;11 privateNode prev;12

13 publicNode(Object data){14 this.data =data;15 }16 }17

18 publicTwoWayLinkedList(){19 size = 0;20 head = null;21 tail = null;22 }23

24 //在鏈表頭增加節(jié)點

25 public voidaddHead(Object value){26 Node newNode = newNode(value);27 if(size == 0){28 head =newNode;29 tail =newNode;30 size++;31 }else{32 head.prev =newNode;33 newNode.next =head;34 head =newNode;35 size++;36 }37 }38

39 //在鏈表尾增加節(jié)點

40 public voidaddTail(Object value){41 Node newNode = newNode(value);42 if(size == 0){43 head =newNode;44 tail =newNode;45 size++;46 }else{47 newNode.prev =tail;48 tail.next =newNode;49 tail =newNode;50 size++;51 }52 }53

54 //刪除鏈表頭

55 publicNode deleteHead(){56 Node temp =head;57 if(size != 0){58 head =head.next;59 head.prev = null;60 size--;61 }62 returntemp;63 }64

65 //刪除鏈表尾

66 publicNode deleteTail(){67 Node temp =tail;68 if(size != 0){69 tail =tail.prev;70 tail.next = null;71 size--;72 }73 returntemp;74 }75

76 //獲得鏈表的節(jié)點個數

77 public intgetSize(){78 returnsize;79 }80 //判斷鏈表是否為空

81 public booleanisEmpty(){82 return (size == 0);83 }84

85 //顯示節(jié)點信息

86 public voiddisplay(){87 if(size >0){88 Node node =head;89 int tempSize =size;90 if(tempSize == 1){//當前鏈表只有一個節(jié)點

91 System.out.println("["+node.data+"]");92 return;93 }94 while(tempSize>0){95 if(node.equals(head)){96 System.out.print("["+node.data+"->");97 }else if(node.next == null){98 System.out.print(node.data+"]");99 }else{100 System.out.print(node.data+"->");101 }102 node =node.next;103 tempSize--;104 }105 System.out.println();106 }else{//如果鏈表一個節(jié)點都沒有，直接打印[]

107 System.out.println("[]");108 }109

110 }111 }

View Code

我們也可以用雙向鏈表來實現雙端隊列，這里就不做具體代碼演示了。

9、總結

上面我們講了各種鏈表，每個鏈表都包括一個LinikedList對象和許多Node對象，LinkedList對象通常包含頭和尾節(jié)點的引用，分別指向鏈表的第一個節(jié)點和最后一個節(jié)點。而每個節(jié)點對象通常包含數據部分data，以及對上一個節(jié)點的引用prev和下一個節(jié)點的引用next，只有下一個節(jié)點的引用稱為單向鏈表，兩個都有的稱為雙向鏈表。next值為null則說明是鏈表的結尾，如果想找到某個節(jié)點，我們必須從第一個節(jié)點開始遍歷，不斷通過next找到下一個節(jié)點，直到找到所需要的。棧和隊列都是ADT，可以用數組來實現，也可以用鏈表實現。

總結

以上是生活随笔為你收集整理的java链表模型_Java数据结构和算法（七）——链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。