java链表模型_Java数据结构和算法(七)——链表
前面博客我們在講解數組中,知道數組作為數據存儲結構有一定的缺陷。在無序數組中,搜索性能差,在有序數組中,插入效率又很低,而且這兩種數組的刪除效率都很低,并且數組在創(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数据结构和算法(七)——链表的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 三元组最小距离
- 下一篇: vue引入音乐播放器插件