鏈表

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

每個數(shù)據(jù)元素單元里有date域和next指針域。next指針指向下一個數(shù)據(jù)元素的date域，這樣把整個鏈表像像一個鏈一樣連起來。要注意保證next域指向的元素唯一。

寫了一個Node類，定義數(shù)據(jù)類型：

class Node {int data;//data域Node next;//next指針域public Node(int paraValue) {data = paraValue;next = null;}}

在鏈表中設(shè)置一個頭節(jié)點(diǎn)（不存儲任何數(shù)據(jù)），便于對鏈表的統(tǒng)一操作（增刪改查），否則還得對第一個節(jié)點(diǎn)專門設(shè)置操作。

Node header;//頭節(jié)點(diǎn)

?對toString方法進(jìn)行重寫，（具體在DAY4）

當(dāng)對對象打印輸出的時候，可以發(fā)現(xiàn)，直接輸出對象與調(diào)用對象的toString()方法產(chǎn)生的效果是一致的。因?yàn)楫?dāng)輸出對象的時候，調(diào)用的也是對象的toString()方法，只不過其不可見而已。

當(dāng)使用toString()方法對象進(jìn)行描述時，輸出格式為：類名+@+哈希碼。hashCode的值在JAVA中不同對象輸出不同的值，hashCode是通過將對象的地址轉(zhuǎn)換成一個整數(shù)來實(shí)現(xiàn)。

一般是方法希望獲得一個對象的詳細(xì)信息，可以對toSting方法進(jìn)行重寫。此處對其進(jìn)行了重寫。

//重寫方法，這個在DAY3中寫過public String toString() {String resultString = "";if (header.next == null) {return "empty";} Node tempNode = header.next;while (tempNode != null) {resultString += tempNode.data + ", ";tempNode = tempNode.next;} return resultString;}

?查找操作在插入和刪除操作里面都要用，在鏈表上的操作都是利用指針來進(jìn)行。

1.查找操作

寫locate方法，設(shè)置兩個指針：tempPosition（遍歷指針，用來向后查找）和tempCurrentPosition（指向當(dāng)前的元素位置）,利用while循環(huán)進(jìn)行查找。找到了用tempCurrentPosition指針賦值給tempPosition，再返回。

//查找public int locate(int paraValue) {int tempPosition = -1;//查找的指針Node tempNode = header.next;//從頭節(jié)點(diǎn)后一個節(jié)點(diǎn)開始查找int tempCurrentPosition = 0;//指向當(dāng)前位置的指針while (tempNode != null) {if (tempNode.data == paraValue) {tempPosition = tempCurrentPosition;//找到查找元素，將當(dāng)前指針覆蓋查找指針break;} //判空//沒找到，繼續(xù)向后查找tempNode = tempNode.next;tempCurrentPosition++;}return tempPosition;//返回}

2.插入操作

輸入待插入元素和待插入元素的位置。

關(guān)鍵是找到待插入元素的前一個位置，將新元素插入鏈表。

//插入元素public boolean insert(int paraPosition, int paraValue) {Node tempNode = header;//指針Node tempNewNode;for (int i = 0; i < paraPosition; i++) {if (tempNode.next == null) {System.out.println("The position " + paraPosition + " is illegal.");return false;} // 報錯tempNode = tempNode.next;//指針指向下一個元素} // 查找待插入位置tempNewNode = new Node(paraValue);//創(chuàng)建新節(jié)點(diǎn)tempNewNode.next = tempNode.next;tempNode.next = tempNewNode;//將新節(jié)點(diǎn)插入鏈中return true;}

3.刪除操作

本操作為按存儲位置刪除，先查找到待刪除的元素位置。設(shè)置一個指針，用指針的元素的指針指向下下個元素的data域，完成刪除。

//刪除public boolean delete(int paraPosition) {if (header.next == null) {System.out.println("Cannot delete element from an empty list.");return false;}//報錯Node tempNode = header;//指針指向頭節(jié)點(diǎn)for (int i = 0; i < paraPosition; i++) {if (tempNode.next.next == null) {System.out.println("The position " + paraPosition + " is illegal.");return false;} //當(dāng)指針指向節(jié)點(diǎn)的后兩個節(jié)點(diǎn)的指針與為空時報錯tempNode = tempNode.next;//指針指向下一個元素} tempNode.next = tempNode.next.next;//刪除元素return true;}

也可以輸入值來進(jìn)行刪除，按值查找再進(jìn)行刪除。

下面為測試代碼：

public static void main(String args[]) {linklist tempFirstList = new linklist();System.out.println("Initialized, the list is: " + tempFirstList.toString());for (int i = 0; i < 5; i++) {tempFirstList.insert(0, i);} System.out.println("Inserted, the list is: " + tempFirstList.toString());tempFirstList.insert(6, 9);tempFirstList.delete(4);tempFirstList.delete(2);System.out.println("Deleted, the list is: " + tempFirstList.toString());tempFirstList.delete(0);System.out.println("Deleted, the list is: " + tempFirstList.toString());for (int i = 0; i < 5; i++) {tempFirstList.delete(0);System.out.println("Looped delete, the list is: " + tempFirstList.toString());} }

結(jié)果為

?總結(jié)：下面比較一下順序表和鏈表，在增刪改查這些操作上，順序表需要大量移動元素，而鏈表效率高，大大減小了時間復(fù)雜度。但是順序表又可以隨機(jī)訪問。所以說，選擇哪種數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲要具體問題具體分析。

總結(jié)

以上是生活随笔為你收集整理的抄代码DAY6的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。