一、前言
最近在回顧數據結構與算法占哟，有部分的算法題用到了棧的思想捶箱，說起棧又不得不說鏈表了。數組和鏈表都是線性存儲結構的基礎膘流，棧和隊列都是線性存儲結構的應用～
本文主要講解單鏈表的基礎知識點絮缅，做一個簡單的入門～如果有錯的地方請指正
二鲁沥、回顧與知新
說起鏈表，我們先提一下數組吧耕魄，跟數組比較一下就很理解鏈表這種存儲結構了画恰。
2.1回顧數組
數組我們無論是C、Java都會學過：
- 數組是一種連續(xù)存儲線性結構吸奴，元素類型相同允扇，大小相等
image
數組的優(yōu)點：
- 存取速度快
數組的缺點：
- 事先必須知道數組的長度
- 插入刪除元素很慢
- 空間通常是有限制的
- 需要大塊連續(xù)的內存塊
- 插入刪除元素的效率很低
2.2鏈表說明
看完了數組，回到我們的鏈表：
- 鏈表是離散存儲線性結構
n個節(jié)點離散分配则奥，彼此通過指針相連考润，每個節(jié)點只有一個前驅節(jié)點，每個節(jié)點只有一個后續(xù)節(jié)點读处，首節(jié)點沒有前驅節(jié)點糊治，尾節(jié)點沒有后續(xù)節(jié)點。
image
鏈表優(yōu)點：
- 空間沒有限制
- 插入刪除元素很快
鏈表缺點：
- 存取速度很慢
鏈表相關術語介紹罚舱，我還是通過上面那個圖來說明吧：
image
確定一個鏈表我們只需要頭指針井辜，通過頭指針就可以把整個鏈表都能推導出來了～
鏈表又分了好幾類：
- 單向鏈表
- 一個節(jié)點指向下一個節(jié)點
- 雙向鏈表
- 一個節(jié)點有兩個指針域
- 循環(huán)鏈表
- 能通過任何一個節(jié)點找到其他所有的節(jié)點，將兩種(雙向/單向)鏈表的最后一個結點指向第一個結點從而實現(xiàn)循環(huán)
操作鏈表要時刻記住的是：
- 節(jié)點中指針域指向的就是一個節(jié)點了馆匿！
三抑胎、Java實現(xiàn)鏈表
算法：
- 遍歷
- 查找
- 清空
- 銷毀
- 求長度
- 排序
- 刪除節(jié)點
- 插入節(jié)點
首先，我們定義一個類作為節(jié)點
- 數據域
- 指針域
為了操作方便我就直接定義成public了渐北。
public class Node {
//數據域
public int data;
//指針域阿逃，指向下一個節(jié)點
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創(chuàng)建鏈表(增加節(jié)點)
向鏈表中插入數據：
- 找到尾節(jié)點進行插入
- 即使頭節(jié)點.next為null，不走while循環(huán)赃蛛，也是將頭節(jié)點與新節(jié)點連接的(我已經將head節(jié)點初始化過了恃锉，因此沒必要判斷頭節(jié)點是否為null)～
/**
* 向鏈表添加數據
*
* @param value 要添加的數據
*/
public static void addData(int value) {
//初始化要加入的節(jié)點
Node newNode = new Node(value);
//臨時節(jié)點
Node temp = head;
// 找到尾節(jié)點
while (temp.next != null) {
temp = temp.next;
}
// 已經包括了頭節(jié)點.next為null的情況了～
temp.next = newNode;
}
3.2遍歷鏈表
上面我們已經編寫了增加方法，現(xiàn)在遍歷一下看一下是否正確～～～
從首節(jié)點開始呕臂，不斷往后面找破托，直到后面的節(jié)點沒有數據：
/**
* 遍歷鏈表
*
* @param head 頭節(jié)點
*/
public static void traverse(Node head) {
//臨時節(jié)點，從首節(jié)點開始
Node temp = head.next;
while (temp != null) {
System.out.println("關注公眾號Java3y：" + temp.data);
//繼續(xù)下一個
temp = temp.next;
}
}
結果：
image
3.3插入節(jié)點
- 插入一個節(jié)點到鏈表中歧蒋，首先得判斷這個位置是否是合法的土砂，才能進行插入～
- 找到想要插入的位置的上一個節(jié)點就可以了～
/**
* 插入節(jié)點
*
* @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;
}
//臨時節(jié)點萝映，從頭節(jié)點開始
Node temp = head;
//記錄遍歷的當前位置
int currentPos = 0;
//初始化要插入的節(jié)點
Node insertNode = new Node(value);
while (temp.next != null) {
//找到上一個節(jié)點的位置了
if ((index - 1) == currentPos) {
//temp表示的是上一個節(jié)點
//將原本由上一個節(jié)點的指向交由插入的節(jié)點來指向
insertNode.next = temp.next;
//將上一個節(jié)點的指針域指向要插入的節(jié)點
temp.next = insertNode;
return;
}
currentPos++;
temp = temp.next;
}
}
3.4獲取鏈表的長度
獲取鏈表的長度就很簡單了，遍歷一下阐虚，每得到一個節(jié)點+1即可～
/**
* 獲取鏈表的長度
* @param head 頭指針
*/
public static int linkListLength(Node head) {
int length = 0;
//臨時節(jié)點序臂，從首節(jié)點開始
Node temp = head.next;
// 找到尾節(jié)點
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
3.5刪除節(jié)點
刪除某個位置上的節(jié)點其實是和插入節(jié)點很像的， 同樣都要找到上一個節(jié)點实束。將上一個節(jié)點的指針域改變一下奥秆，就可以刪除了～
/**
* 根據位置刪除節(jié)點
*
* @param head 頭指針
* @param index 要刪除的位置
*/
public static void deleteNode(Node head, int index) {
//首先需要判斷指定位置是否合法逊彭，
if (index < 1 || index > linkListLength(head) + 1) {
System.out.println("刪除位置不合法。");
return;
}
//臨時節(jié)點构订，從頭節(jié)點開始
Node temp = head;
//記錄遍歷的當前位置
int currentPos = 0;
while (temp.next != null) {
//找到上一個節(jié)點的位置了
if ((index - 1) == currentPos) {
//temp表示的是上一個節(jié)點
//temp.next表示的是想要刪除的節(jié)點
//將想要刪除的節(jié)點存儲一下
Node deleteNode = temp.next;
//想要刪除節(jié)點的下一個節(jié)點交由上一個節(jié)點來控制
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個節(jié)點
這個算法挺有趣的：設置兩個指針p1签赃、p2，讓p2比p1快k個節(jié)點分尸，同時向后遍歷，當p2為空歹嘹，則p1為倒數第k個節(jié)點
/**
* 找到鏈表中倒數第k個節(jié)點(設置兩個指針p1箩绍、p2，讓p2比p1快k個節(jié)點尺上，同時向后遍歷材蛛，當p2為空，則p1為倒數第k個節(jié)點
*
* @param head
* @param k 倒數第k個節(jié)點
*/
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個節(jié)點
for (int i = 0; i < k - 1; i++)
p2 = p2.next;
// 只要p2為null怎抛，那么p1就是倒數第k個節(jié)點了
while (p2.next != null) {
p2 = p2.next;
p1 = p1.next;
}
return p1;
}
經過評論去提醒：也可以使用(-k+1+LinkList.length)%LinkList.length來獲取倒數的節(jié)點位置~
3.8刪除鏈表重復數據
跟冒泡排序差不多卑吭，只要它相等，就能刪除了～
/**
* 刪除鏈表重復數據(跟冒泡差不多马绝，等于刪除就是了)
*
* @param head 頭節(jié)點
*/
public static void deleteDuplecate(Node head) {
//臨時節(jié)點豆赏，(從首節(jié)點開始-->真正有數據的節(jié)點)
Node temp = head.next;
//當前節(jié)點(首節(jié)點)的下一個節(jié)點
Node nextNode = temp.next;
while (temp.next != null) {
while (nextNode.next != null) {
if (nextNode.next.data == nextNode.data) {
//將下一個節(jié)點刪除(當前節(jié)點指向下下個節(jié)點)
nextNode.next = nextNode.next.next;
} else {
//繼續(xù)下一個
nextNode = nextNode.next;
}
}
//下一輪比較
temp = temp.next;
}
}
3.9查詢鏈表的中間節(jié)點
這個算法也挺有趣的：一個每次走1步，一個每次走兩步富稻，走兩步的遍歷完掷邦，然后走一步的指針，那就是中間節(jié)點
/**
* 查詢單鏈表的中間節(jié)點
*/
public static Node searchMid(Node head) {
Node p1 = head;
Node p2 = head;
// 一個走一步椭赋，一個走兩步抚岗，直到為null，走一步的到達的就是中間節(jié)點
while (p2 != null && p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}
3.10通過遞歸從尾到頭輸出單鏈表
/**
* 通過遞歸從尾到頭輸出單鏈表
*
* @param head 頭節(jié)點
*/
public static void printListReversely(Node head) {
if (head != null) {
printListReversely(head.next);
System.out.println(head.data);
}
}
3.11反轉鏈表
/**
* 實現(xiàn)鏈表的反轉
*
* @param node 鏈表的頭節(jié)點
*/
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;
}
image
反轉鏈表參考自：
四哪怔、最后
理解鏈表本身并不難宣蔚，但做相關的操作就弄得頭疼，
head.next next next next ....(算法這方面我還是薄弱啊..腦子不夠用了.....)寫了兩天就寫了這么點東西...
操作一個鏈表只需要知道它的頭指針就可以做任何操作了
-
添加數據到鏈表中
- 遍歷找到尾節(jié)點认境，插入即可(只要
while(temp.next != null)胚委，退出循環(huán)就會找到尾節(jié)點)
- 遍歷找到尾節(jié)點认境，插入即可(只要
-
遍歷鏈表
- 從首節(jié)點(有效節(jié)點)開始，只要不為null元暴，就輸出
-
給定位置插入節(jié)點到鏈表中
- 首先判斷該位置是否有效(在鏈表長度的范圍內)
-
找到想要插入位置的上一個節(jié)點
- 將原本由上一個節(jié)點的指向交由插入的節(jié)點來指向
- 上一個節(jié)點指針域指向想要插入的節(jié)點
- image
-
獲取鏈表的長度
- 每訪問一次節(jié)點篷扩，變量++操作即可
-
刪除給定位置的節(jié)點
- 首先判斷該位置是否有效(在鏈表長度的范圍內)
-
找到想要插入位置的上一個節(jié)點
- 將原本由上一個節(jié)點的指向后面一個節(jié)點
- image
-
對鏈表進行排序
- 使用冒泡算法對其進行排序
-
找到鏈表中倒數第k個節(jié)點
- 設置兩個指針p1、p2茉盏，讓p2比p1快k個節(jié)點鉴未，同時向后遍歷枢冤，當p2為空，則p1為倒數第k個節(jié)點
-
刪除鏈表重復數據
- 操作跟冒泡排序差不多铜秆，只要它相等淹真，就能刪除了～
-
查詢鏈表的中間節(jié)點
- 這個算法也挺有趣的：一個每次走1步，一個每次走兩步连茧，走兩步的遍歷完核蘸，然后走一步的指針，那就是中間節(jié)點
-
遞歸從尾到頭輸出單鏈表
- 只要下面還有數據啸驯，那就往下找客扎，遞歸是從最后往前翻。
-
反轉鏈表
- 有遞歸和非遞歸兩種方式罚斗，我覺得是挺難的徙鱼。可以到我給出的鏈接上查閱～
PS：每個人的實現(xiàn)都會不一樣针姿，所以一些小細節(jié)難免會有些變動袱吆，也沒有固定的寫法，能夠實現(xiàn)對應的功能即可～
參考資料：
如果文章有錯的地方歡迎指正距淫，大家互相交流绞绒。習慣在微信看技術文章，想要獲取更多的Java資源的同學榕暇，可以關注微信公眾號:Java3y
