一、前言
最近在回顧數據結構與算法，有部分的算法題用到了棧的思想，說起棧又不得不說鍊錶了。數組和鍊錶都是線性存儲結構的基礎，棧和隊列都是線性存儲結構的應用～
本文主要講解單鍊錶的基礎知識點，做一個簡單的入門～如果有錯的地方請指正
二、回顧與知新
說起鍊錶，我們先提一下數組吧，跟數組比較一下就很理解鍊錶這種存儲結構了。
2.1回顧數組
數組我們無論是C、Java都會學過：
數組的優點：
數組的缺點：
2.2鍊錶說明
看完了數組，回到我們的鍊錶：
n個節點離散分配，彼此通過指針相連，每個節點只有一個前驅節點，每個節點只有一個後續節點，首節點沒有前驅節點，尾節點沒有後續節點。
鍊錶優點：
鍊錶缺點：
鍊錶相關術語介紹，我還是通過上面那個圖來說明吧：
確定一個鍊錶我們只需要頭指針，通過頭指針就可以把整個鍊錶都能推導出來了～
鍊錶又分了好幾類：
1、單向鍊錶
2、雙向鍊錶
3、循環鍊錶
操作鍊錶要時刻記住的是：
節點中指針域指向的就是一個節點了！
三、Java實現鍊錶
演算法:
首先，我們定義一個類作為節點
為了操作方便我就直接定義成public了。
public class Node { //數據域public int data; //指針域，指向下一個節點public Node next; public Node() { } public Node(int data) { this.data = data; } public Node(int data, Node next) { this.data = data; this.next = next; }} 3.1創建鍊錶(增加節點)
向鍊錶中插入數據：
/** * 向鍊錶添加數據* * @param value 要添加的數據*/ public static void addData(int value) { //初始化要加入的節點Node newNode = new Node(value); //臨時節點Node temp = head; // 找到尾節點while (temp.next != null) { temp = temp.next; } // 已經包括了頭節點.next為null的情況了～ temp.next = newNode; } 3.2遍歷鍊錶
上面我們已經編寫了增加方法，現在遍歷一下看一下是否正確～～～
從首節點開始，不斷往後面找，直到後面的節點沒有數據：
/** * 遍歷鍊錶* * @param head 頭節點*/ public static void traverse(Node head) { //臨時節點，從首節點開始Node temp = head.next; while (temp != null) { System.out.println("關注公眾號Java3y：" + temp.data); //繼續下一個temp = temp.next; } }結果：
3.3插入節點
/** * 插入節點* * @param head 頭指針* @param index 要插入的位置* @param value 要插入的值*/ public static void insertNode(Node head, int index, int value) { //首先需要判斷指定位置是否合法， if (index < 1 || index > linkListLength(head) + 1) { System.out.println("插入位置不合法。"); return; } //臨時節點，從頭節點開始Node temp = head; //記錄遍歷的當前位置int currentPos = 0; //初始化要插入的節點Node insertNode = new Node(value); while (temp.next != null) { //找到上一個節點的位置了if ((index - 1) == currentPos) { //temp表示的是上一個節點//將原本由上一個節點的指向交由插入的節點來指向insertNode.next = temp.next; //將上一個節點的指針域指向要插入的節點temp.next = insertNode; return; } currentPos++; temp = temp.next; } } 3.4獲取鍊錶的長度
獲取鍊錶的長度就很簡單了，遍歷一下，每得到一個節點+1即可～
/** * 獲取鍊錶的長度* @param head 頭指針*/ public static int linkListLength(Node head) { int length = 0; //臨時節點，從首節點開始Node temp = head.next; // 找到尾節點while (temp != null) { length++; temp = temp.next; } return length; } 3.5刪除節點
刪除某個位置上的節點其實是和插入節點很像的， 同樣都要找到上一個節點。將上一個節點的指針域改變一下，就可以刪除了～
/** * 根據位置刪除節點* * @param head 頭指針* @param index 要刪除的位置*/ public static void deleteNode(Node head, int index) { //首先需要判斷指定位置是否合法， if (index < 1 || index > linkListLength(head) + 1) { System.out.println("刪除位置不合法。"); return; } //臨時節點，從頭節點開始Node temp = head; //記錄遍歷的當前位置int currentPos = 0; while (temp.next != null) { //找到上一個節點的位置了if ((index - 1) == currentPos) { //temp表示的是上一個節點//temp.next表示的是想要刪除的節點//將想要刪除的節點存儲一下Node deleteNode = temp.next; //想要刪除節點的下一個節點交由上一個節點來控制temp.next = deleteNode.next; //Java會回收它，設置不設置為null應該沒多大意義了(個人覺得,如果不對請指出哦～) deleteNode = null; return; } currentPos++; temp = temp.next; } } 3.6對鍊錶進行排序
前面已經講過了8種的排序算法了【八種排序算法總結】，這次挑簡單的冒泡排序吧(其實我是想寫快速排序的，嘗試了一下感覺有點難.....)
/** * 對鍊錶進行排序* * @param head * */ public static void sortLinkList(Node head) { Node currentNode; Node nextNode; for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) { for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) { if (nextNode.data > nextNode.next.data) { int temp = nextNode.data; nextNode.data = nextNode.next.data; nextNode.next.data = temp; } } } } 3.7找到鍊錶中倒數第k個節點
這個算法挺有趣的：設置兩個指針p1、p2，讓p2比p1快k個節點，同時向後遍歷，當p2為空，則p1為倒數第k個節點
/** * 找到鍊錶中倒數第k個節點(設置兩個指針p1、p2，讓p2比p1快k個節點，同時向後遍歷，當p2為空，則p1為倒數第k個節點* * @param head * @param k 倒數第k個節點*/ public static Node findKNode(Node head, int k) { if (k < 1 || k > linkListLength(head)) return null; Node p1 = head; Node p2 = head; // p2比怕p1快k個節點for (int i = 0; i < k - 1; i++) p2 = p2.next; // 只要p2為null，那麼p1就是倒數第k個節點了while (p2.next != null) { p2 = p2.next; p1 = p1.next; } return p1; } 3.8刪除鍊錶重複數據
跟冒泡排序差不多，只要它相等，就能刪除了～
/** * 刪除鍊錶重複數據(跟冒泡差不多，等於刪除就是了) * * @param head 頭節點*/ public static void deleteDuplecate(Node head) { //臨時節點，(從首節點開始-->真正有數據的節點) Node temp = head.next; //當前節點(首節點)的下一個節點Node nextNode = temp.next; while (temp.next != null) { while (nextNode.next != null) { if (nextNode.next.data == nextNode.data) { //將下一個節點刪除(當前節點指向下下個節點) nextNode.next = nextNode.next.next; } else { //繼續下一個nextNode = nextNode.next; } } //下一輪比較temp = temp.next; } } 3.9查詢鍊錶的中間節點
這個算法也挺有趣的：一個每次走1步，一個每次走兩步，走兩步的遍歷完，然後走一步的指針，那就是中間節點
/** * 查詢單鍊錶的中間節點*/ public static Node searchMid(Node head) { Node p1 = head; Node p2 = head; // 一個走一步，一個走兩步，直到為null，走一步的到達的就是中間節點while (p2 != null && p2.next != null && p2.next.next != null) { p1 = p1.next; p2 = p2.next.next; } return p1; }3.10通過遞歸從尾到頭輸出單鍊錶
/** * 通過遞歸從尾到頭輸出單鍊錶* * @param head 頭節點*/ public static void printListReversely(Node head) { if (head != null) { printListReversely(head.next); System.out.println(head.data); } } 3.11反轉鍊錶
/** * 實現鍊錶的反轉* * @param node 鍊錶的頭節點*/ public static Node reverseLinkList(Node node) { Node prev ; if (node == null || node.next == null) { prev = node; } else { Node tmp = reverseLinkList(node.next); node.next.next = node; node.next = null; prev = tmp; } return prev; }反轉鍊錶參考自：//www.VeVB.COm/article/136185.htm
四、最後
理解鍊錶本身並不難，但做相關的操作就弄得頭疼，head.next next next next ....(算法這方面我還是薄弱啊..腦子不夠用了.....)寫了兩天就寫了這麼點東西...
操作一個鍊錶只需要知道它的頭指針就可以做任何操作了
1、添加數據到鍊錶中
2、遍歷鍊錶
3、給定位置插入節點到鍊錶中
4、獲取鍊錶的長度
5、刪除給定位置的節點
6、對鍊錶進行排序
7、找到鍊錶中倒數第k個節點
8、刪除鍊錶重複數據
9、查詢鍊錶的中間節點
10、遞歸從尾到頭輸出單鍊錶
11、反轉鍊錶
PS：每個人的實現都會不一樣，所以一些小細節難免會有些變動，也沒有固定的寫法，能夠實現對應的功能即可～
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對武林網的支持。
參考資料：