?鏈表結構簡介
? ? ? ? 鏈表結構是一種用比較特殊的數據結構類型,它也是線性數據結構中的一種,但是與棧結構等線性數據結構不同,它的內部結構并不是一個簡單的存儲空間,而是一個帶有指向性質的單元。要理解鏈表結構要弄清楚兩個問題,第一個就是鏈表結構的存儲方式是怎樣的,第二個就是鏈表結構的模型該如何描述。
? ? ? ? 先說第一個問題,鏈表結構的存儲方式。鏈表結構對數據存儲的時候并不是簡單的將這個數據存放到一個指定的空間中,而是將數據存儲到一個屬于鏈表結構的節點當中。這個節點就是鏈表的一個組成部分,在這個節點中,不僅存儲了這個元素還存儲了下一個元素或者上一個元素的地址,通過這些儲存的地址就可以找到當前元素的上一個元素或者下一個元素。
? ? ? ? 了解完鏈表結構的存儲方式,那么鏈表結構的模型就比較好建立了。最簡單的模型就是鏈子,不論是鐵鏈還是狗鏈都能幫助我們理解鏈表結構。因為鏈表結構就相當于是用一根無形的繩子將內存中的數據串了起來,就像是一根鏈子一樣,所以稱之為鏈表結構。但是要注意的是,雖然我們可以將鏈表結構想象成一根鐵鏈,但是在實際內存中,鏈表結構中相鄰的兩個元素在內存中并不是相鄰的。只是通過上一個節點中存儲的地址能找到下一個節點中存儲的元素而已。
? ? ? ? 綜上,鏈表結構是由許多節點組成的,每一個節點中都應包含數據部分和地址部分兩個部分。其中數據部分用來存儲該節點的實際數據,而地址部分用來存儲上一個或者下一個節點的地址。
? ? ? ? 鏈表結構可以分為單向鏈表、雙向鏈表和雙向循環鏈表三種,其中單向鏈表和雙向鏈表是比較常見的鏈表結構,雙向循環鏈表不太常見,簡單了解即可。
單向鏈表
? ? ? ? 單向鏈表是鏈表結構中最為簡單的一類,它的特點是鏈表中節點的鏈接方向是單向的,也就是說訪問鏈表中的元素時只能從頭開始一個一個的尋找,不能直接鎖定指定元素的位置,也不能從尾向前訪問元素。故能夠判斷出單向鏈表的結構中節點存儲的內容應該為節點存儲的元素以及下一個節點的地址。
? ? ? ? 了解了單向鏈表的結構以及存儲模式,就可以創建單向鏈表的具體對象了。目前,在java中是找不到一個合適的結構來描述鏈表結構的,因此需要自行創建鏈表實現類。考慮到單向鏈表和雙向鏈表的除了在存儲結構上純在些許差異之外其余并無太多不同,并且它們都應該具有對內部儲存元素進行操作的方法,因此為了提高代碼的復用性,可以將鏈表結構中的方法抽象出來創建一個接口,這樣在實現單向鏈表或者雙向鏈表類的時候只需要實現接口中的方法就能夠實現對應的操作方法了。大大降低了代碼的復雜程度。根據鏈表結構中應該具備的操作元素的方法,創建了以下接口:
package com.data.demo;/*** 基于鏈表結構存取元素的API定義* @param <E>*/public interface MyList <E>{void add (E element);E get (int index);int size();E remove(int index);
}
此接口中定義了四個抽象方法,對應了添加元素、獲取元素、獲取元素個數以及刪除元素四個功能。
? ? ? ? 創建完鏈表結構的接口類,就可以創建一個單向鏈表類來實現這個接口類了。由于向單向鏈表中添加元素之前并不能確定添加的元素類型,因此定義的單向鏈表類應該是一個泛型類,它當中的需要參數的方法應該為泛型方法,這也說名了上面定義的接口為泛型接口的原因。
????????在單向鏈表結構中應該具備這樣一個部分,這個部分是用來描述節點內容的。而且很容易發現,節點功能只會在單向鏈表類中被使用,在其它類中不會被使用。這個描述符合內部類的特征,因此可以在單向鏈表類中定義一個內部類來存儲節點信息。將這個內部類定義為內部泛型類,它的名稱為Node,在Node類型中item變量用來存儲當前節點的元素,定義一個變量next用來指向下一個節點對象的地址,并且還要提供一個全參構造方法。具體實現如演示代碼所示。
? ? ? ? 以上定義了單向鏈表中的用于描述節點的結構,接下來就需要對單向鏈表中的具體方法做出實現了。
實現添加元素的方法
? ? ? ? 結合上文所說,單向鏈表訪問元素必須從頭節點開始,不能從尾節點或者鏈表當中的任意節點開始,因此在實現單向鏈表中的具體方法之前需要確定單向鏈表頭節點的位置。因此最簡單的方法就是定義一個私有的Node類型的成員變量來存儲單向鏈表中頭節點的位置。這里將這個變量定義為?head。此外,操作元素的方法中還涉及了元素個數的變動,也應該添加一個私有變量來記錄單向鏈表中的元素個數變動,此處為size。
? ? ? ? 隨后實現單行鏈表中添加元素的方法add。這個方法的作用是將指定元素添加到單向鏈表結構中,根據對單向鏈表結構的描述,這個方法可以分為三步實現。第一步,創建節點,將傳入方法的元素添加到創建的節點當中;第二步,找到尾節點;第三步,實現節點掛接。
????????這三步中比較難理解的是第二步和第三步。第二步找到尾節點的原因是添加元素是將元素添加到單向鏈表的尾節點之后,因此需要先找到尾節點。而在單向鏈表中,訪問元素是從頭節點開始的,所以要找到尾節點就得從頭節點開始不斷向下訪問節點,直到訪問的節點不再指向下一個元素為止,就找到了尾節點。也就是說,當next的地址為null時,尾節點就找到了。根據描述,第二步應該用一個死循環來實現,具體實現如演示代碼中的getTail方法所示。這里要注意,循環結構中的this.node = head;的意思是將head的值賦給一個新的變量node,這樣做的目的是因為真正頭節點的位置是不能改變的。其次循環實現是通過移動node指向的地址來實現的。如果不滿足要求,就像node.next也就是下一個節點的地址傳給node,直到node的地址為空。
????????第三步實現節點的掛接就稍微好理解點了,因為是在尾節點添加元素,所以新添加的元素成為了尾節點,原來的尾節點不再是尾節點,所以原來節點中指向下一個節點的地址不應為空,而應是新添加的節點。這就是節點掛接的簡單描述,具體實現為
???????????????if(tail == null){
? ? ? ? ? ? ????????this.head = node;
? ? ? ????????????}else{
? ? ? ? ? ????????? tail.next = node;
????????????????}
其中tail == null代表沒有尾節點,即整個單向鏈表均為空,這時添加的節點就是頭節點,即只需要將添加的節點賦給頭節點即可。在擁有尾節點的情況下用代碼tail.next = node;即可將尾節點指向的下一個節點指向添加的節點,節點掛接的操作就完成了。當然,添加有元素會使得單向鏈表中的元素個數發生變動,因此還需要對元素變動進行記錄。至此,添加元素的方法就完成了。
實現獲取元素的方法
? ? ? ? 獲取元素的方法是getNode,這個方法需要傳入一個int類型的參數作為元素索引,通過索引來獲取元素。這里可能會有人提出一個疑問,鏈表結構存在索引嗎?為什么能夠通過索引來過去元素?我們先暫時將這個問題擱淺,實現獲取元素的方法之后自然就清楚了。
? ? ? ? 由于getNode方法是通過索引來獲取指定位置的元素的,所以在獲取元素之前要先檢查給定的索引是否合法。因為編寫的單向鏈表類中的元素是從0這個索引開始的,所以索引的范圍為[0,size),即最小為0,最大為元素個數減1。通過單向鏈表實現的接口能發現,要實現的四個方法中不止getNaoe方法用到了元素索引,所以對索引合法性的判斷最好編寫成一個獨立的方法。在演示代碼中體現為checkIndex方法。在這個方法中,如果索引合法則會執行獲取索引所指向的元素,如果不合法則會拋出索引異常的的提示。
? ? ? ? 當給定的索引合法之后就可以獲取索引指向的元素了,那么其實可以發現,單向鏈表并沒有索引,那么這個索引哪兒來的呢?其實這里要聯系到添加元素到單向鏈表的操作,可以發現,添加元素時提供的方法時從尾節點添加的,也就是說這個單向鏈表中的元素有一個默認順序,這個順序就是添加元素的順序。那么,如果把元素添加的元素作為單向鏈表中元素的“虛假的索引”就可以通過這個“虛假的索引”來獲取單向鏈表中的元素了。這個想法在getNode這個方法得到了充分的體現。
????????????????????????????????private Node getNode(int index){
? ? ? ????????????????????????????????? Node node = this.head;
? ? ? ????????????????????????????????? for(int i = 0;i < index;i++){
? ? ? ? ? ? ????????????????????????????????node = node.next;
? ? ? ? ????????????????????????????????}
? ? ? ????????????????????????????????? return node;
? ????????????????????????????????? ? }
在方法getNode方法的代碼中,由于單向鏈表只能從頭節點開始訪問元素的限制,所以先將頭節點賦給一個新的變量node,隨后通過循環結構來訪問單向鏈表中的元素。根據上面描述的原理,獲取索引為index的元素等價于獲取第index個添加到單向鏈表中的元素,所以只要將索引index作為循環是否終止的判斷條件即可獲取到指定索引的元素。如此,先前擱淺的問題便得到了解決,同時獲取指定位置的元素的方法也得到了實現。
刪除指定索引位置的元素
? ? ? ? 刪除元素的方法為remove,這個方法仍然需要傳入一個索引,此外它還會返回刪除的元素的值。由于這個方法有一個索引,所以需要調用方法checkIndex來檢驗傳入索引的合法性。此外也要獲取到當前索引指向的節點,以方便后續操作以及返回當前節點中的元素。
? ? ? ? 接下來闡述單向鏈表中刪除元素的索引。通過上面的描述知道,單向鏈表中的元素是通過節點中存儲的地址值來鏈接在一起的,那么如果能夠將某個元素上的這個中鏈接關系刪除,就能將這個元素從這個單向鏈表中移除。所以這里涉及到三個操作,移除上一個節點指向當前節點的地址值,將上一個節點中存儲的地址值指向當前節點的下一個節點以及將當前節點存儲的地址值置空。以上的這三個操作就是在單項鏈表中刪除指定元素的具體操作,但是在具體操作時又可以分為刪除的元素是否為頭節點的情況,如果刪除的元素時頭節點,則只需要將下一個元素賦給頭節點,隨后將要刪除的節點存儲的地址置空即可。而當要刪除的元素不是頭節點時,上面的三個操作就缺一不可了。以上的描述體現在代碼中具體為:
? ? ? ??????????????????if(this.head == node){
? ? ? ? ? ? ????????????????this.head = node.next;
? ? ? ? ????????????????}else{
? ? ? ? ? ? ????????????????Node<E> temp = this.head;
? ? ? ? ? ? ????????????????for (int i = 0; i < index-1; i++) {
? ? ? ? ? ? ? ? ????????????????temp = temp.next;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ????????????????temp.next = node.next;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ????????????????node.next = null;
在這個代碼中要注意的是獲取前一個節點只需要索引減一即可。然后就是注意中間變量temp的合理運用。當然由于刪除了元素,所以記錄元素個數的變量也要發生相應的變化。
獲取元素個數的方法
? ? ? ? 獲取元素個數的方法極為簡單,因為在添加元素和刪除元素的操作中都實現了元素個數的變化,并且對元素個數的變化進行了相應記錄。所以在這個方法中只需要將記錄元素個數的變量size返回即可。
演示代碼
? ? ? ? 實現了上述的所有方法,接下來要對其進行驗證,所以開辟一個main方法,在main方法中實例化一個單向鏈表類并測試以上的四個方法。具體實現如下所示:
package com.data.demo;/***基于單項鏈表實現元素存取的容器類* @param <E>*/
public class MySinglyLinkedList<E> implements MyList<E> {//定義單向鏈表中的節點對象class Node<E>{private E item;//存儲元素private Node next;//存儲下一個節點對象的地址Node(E item,Node next){this.item = item;this.next = next;}}private Node head;//存放鏈表的頭節點private int size;//記錄元素個數//添加元素@Overridepublic void add(E element) {//創建節點Node<E> node = new Node<>(element,null);//找到尾節點Node tail = getTail();//節點掛接if(tail == null){this.head = node;}else{tail.next = node;}//記錄元素個數this.size++;}//尋找尾節點的方法private Node getTail(){//判斷頭節點是否存在if(this.head == null){return null;}Node node = this.head;while(true){if(node.next == null)break;node = node.next;}return node;}//獲取元素@Overridepublic E get(int index) {//校驗index的合法性this.checkIndex(index);//根據位置獲取節點元素Node<E> node = this.getNode(index);//返回節點中的元素return node.item;}/*** 校驗index合法性的方法* @return*/
private void checkIndex(int index){if(!(index < this.size && index >= 0)){throw new IndexOutOfBoundsException("Index:"+index+"Size:"+this.size);}
}/*** 根據位置獲取節點* @return*/private Node getNode(int index){Node node = this.head;for(int i = 0;i < index;i++){node = node.next;}return node;}//獲取元素個數@Overridepublic int size() {return this.size;}//刪除元素@Overridepublic E remove(int index) {//校驗index的合法性this.checkIndex(index);//根據位置找到節點對象Node<E> node = getNode(index);//獲取該節點對象中的元素E item = node.item;//將該節點對象從單向鏈表中刪除//判斷該節點是否為頭節點if(this.head == node){this.head = node.next;}else{Node<E> temp = this.head;for (int i = 0; i < index-1; i++) {temp = temp.next;}temp.next = node.next;}node.next = null;//記錄元素個數this.size--;//返回該元素return item;}public static void main(String[] args) {MySinglyLinkedList<String> mySinglyLinkedList = new MySinglyLinkedList<>();mySinglyLinkedList.add("a");mySinglyLinkedList.add("b");mySinglyLinkedList.add("c");mySinglyLinkedList.add("d");mySinglyLinkedList.add("e");System.out.println(mySinglyLinkedList.size());System.out.println(mySinglyLinkedList.remove(2));for (int i = 0; i < mySinglyLinkedList.size; i++) {System.out.println(mySinglyLinkedList.get(i));}}
}