Java如何實(shí)現(xiàn)單向鏈表

這篇文章將為大家詳細(xì)講解有關(guān)Java如何實(shí)現(xiàn)單向鏈表，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

一、前言

最近在回顧數(shù)據(jù)結(jié)構(gòu)與算法，有部分的算法題用到了棧的思想，說(shuō)起棧又不得不說(shuō)鏈表了。數(shù)組和鏈表都是線性存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)，棧和隊(duì)列都是線性存儲(chǔ)結(jié)構(gòu)的應(yīng)用～

二、回顧與知新

說(shuō)起鏈表，我們先提一下數(shù)組吧，跟數(shù)組比較一下就很理解鏈表這種存儲(chǔ)結(jié)構(gòu)了。

2.1回顧數(shù)組

數(shù)組我們無(wú)論是C、Java都會(huì)學(xué)過(guò)：

• 數(shù)組是一種連續(xù)存儲(chǔ)線性結(jié)構(gòu)，元素類型相同，大小相等

數(shù)組的優(yōu)點(diǎn)：

• 存取速度快

數(shù)組的缺點(diǎn)：

• 事先必須知道數(shù)組的長(zhǎng)度

• 插入刪除元素很慢

• 空間通常是有限制的

• 需要大塊連續(xù)的內(nèi)存塊

• 插入刪除元素的效率很低

2.2鏈表說(shuō)明

看完了數(shù)組，回到我們的鏈表：

• 鏈表是離散存儲(chǔ)線性結(jié)構(gòu)

n個(gè)節(jié)點(diǎn)離散分配，彼此通過(guò)指針相連，每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)只有一個(gè)后續(xù)節(jié)點(diǎn)，首節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒(méi)有后續(xù)節(jié)點(diǎn)。

鏈表優(yōu)點(diǎn)：

• 空間沒(méi)有限制

• 插入刪除元素很快

鏈表缺點(diǎn)：

• 存取速度很慢

鏈表相關(guān)術(shù)語(yǔ)介紹，我還是通過(guò)上面那個(gè)圖來(lái)說(shuō)明吧：

確定一個(gè)鏈表我們只需要頭指針，通過(guò)頭指針就可以把整個(gè)鏈表都能推導(dǎo)出來(lái)了～

鏈表又分了好幾類：

1、單向鏈表

• 一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)

2、雙向鏈表

• 一個(gè)節(jié)點(diǎn)有兩個(gè)指針域

3、循環(huán)鏈表

• 能通過(guò)任何一個(gè)節(jié)點(diǎn)找到其他所有的節(jié)點(diǎn)，將兩種(雙向/單向)鏈表的最后一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)從而實(shí)現(xiàn)循環(huán)

操作鏈表要時(shí)刻記住的是：

節(jié)點(diǎn)中指針域指向的就是一個(gè)節(jié)點(diǎn)了！

三、Java實(shí)現(xiàn)鏈表

算法：

• 遍歷

• 查找

• 清空

• 銷毀

• 求長(zhǎng)度

• 排序

• 刪除節(jié)點(diǎn)

• 插入節(jié)點(diǎn)

首先，我們定義一個(gè)類作為節(jié)點(diǎn)

• 數(shù)據(jù)域

• 指針域

為了操作方便我就直接定義成public了。

public class Node {

 //數(shù)據(jù)域
 public int data;
 //指針域，指向下一個(gè)節(jié)點(diǎn)
 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é)點(diǎn))

向鏈表中插入數(shù)據(jù)：

• 找到尾節(jié)點(diǎn)進(jìn)行插入

• 即使頭節(jié)點(diǎn).next為null，不走while循環(huán)，也是將頭節(jié)點(diǎn)與新節(jié)點(diǎn)連接的(我已經(jīng)將head節(jié)點(diǎn)初始化過(guò)了，因此沒(méi)必要判斷頭節(jié)點(diǎn)是否為null)～

 /**
 * 向鏈表添加數(shù)據(jù)
 *
 * @param value 要添加的數(shù)據(jù)
 */
 public static void addData(int value) {
 //初始化要加入的節(jié)點(diǎn)
 Node newNode = new Node(value);
 //臨時(shí)節(jié)點(diǎn)
 Node temp = head;
 // 找到尾節(jié)點(diǎn)
 while (temp.next != null) {
 temp = temp.next;
 }
 // 已經(jīng)包括了頭節(jié)點(diǎn).next為null的情況了～
 temp.next = newNode;
 }

3.2遍歷鏈表

上面我們已經(jīng)編寫了增加方法，現(xiàn)在遍歷一下看一下是否正確～～～

從首節(jié)點(diǎn)開(kāi)始，不斷往后面找，直到后面的節(jié)點(diǎn)沒(méi)有數(shù)據(jù)：

 /**
 * 遍歷鏈表
 *
 * @param head 頭節(jié)點(diǎn)
 */
 public static void traverse(Node head) {
 //臨時(shí)節(jié)點(diǎn)，從首節(jié)點(diǎn)開(kāi)始
 Node temp = head.next;
 while (temp != null) {
 System.out.println("關(guān)注公眾號(hào)Java3y：" + temp.data);
 //繼續(xù)下一個(gè)
 temp = temp.next;
 }
 }

結(jié)果：

3.3插入節(jié)點(diǎn)

• 插入一個(gè)節(jié)點(diǎn)到鏈表中，首先得判斷這個(gè)位置是否是合法的，才能進(jìn)行插入～

• 找到想要插入的位置的上一個(gè)節(jié)點(diǎn)就可以了～

 /**
 * 插入節(jié)點(diǎn)
 *
 * @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;
 }
 //臨時(shí)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開(kāi)始
 Node temp = head;
 //記錄遍歷的當(dāng)前位置
 int currentPos = 0;
 //初始化要插入的節(jié)點(diǎn)
 Node insertNode = new Node(value);
 while (temp.next != null) {
 //找到上一個(gè)節(jié)點(diǎn)的位置了
 if ((index - 1) == currentPos) {
 //temp表示的是上一個(gè)節(jié)點(diǎn)
 //將原本由上一個(gè)節(jié)點(diǎn)的指向交由插入的節(jié)點(diǎn)來(lái)指向
 insertNode.next = temp.next;
 //將上一個(gè)節(jié)點(diǎn)的指針域指向要插入的節(jié)點(diǎn)
 temp.next = insertNode;
 return;
 }
 currentPos++;
 temp = temp.next;
 }
 }

3.4獲取鏈表的長(zhǎng)度

獲取鏈表的長(zhǎng)度就很簡(jiǎn)單了，遍歷一下，每得到一個(gè)節(jié)點(diǎn)+1即可～

 /**
 * 獲取鏈表的長(zhǎng)度
 * @param head 頭指針
 */
 public static int linkListLength(Node head) {
 int length = 0;
 //臨時(shí)節(jié)點(diǎn)，從首節(jié)點(diǎn)開(kāi)始
 Node temp = head.next;
 // 找到尾節(jié)點(diǎn)
 while (temp != null) {
 length++;
 temp = temp.next;
 }
 return length;
 }

3.5刪除節(jié)點(diǎn)

刪除某個(gè)位置上的節(jié)點(diǎn)其實(shí)是和插入節(jié)點(diǎn)很像的， 同樣都要找到上一個(gè)節(jié)點(diǎn)。將上一個(gè)節(jié)點(diǎn)的指針域改變一下，就可以刪除了～

 /**
 * 根據(jù)位置刪除節(jié)點(diǎn)
 *
 * @param head 頭指針
 * @param index 要?jiǎng)h除的位置
 */
 public static void deleteNode(Node head, int index) {
 //首先需要判斷指定位置是否合法，
 if (index < 1 || index > linkListLength(head) + 1) {
  System.out.println("刪除位置不合法。");
  return;
 }

 //臨時(shí)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開(kāi)始
 Node temp = head;
 //記錄遍歷的當(dāng)前位置
 int currentPos = 0;
 while (temp.next != null) {
  //找到上一個(gè)節(jié)點(diǎn)的位置了
  if ((index - 1) == currentPos) {
  //temp表示的是上一個(gè)節(jié)點(diǎn)
  //temp.next表示的是想要?jiǎng)h除的節(jié)點(diǎn)
  //將想要?jiǎng)h除的節(jié)點(diǎn)存儲(chǔ)一下
  Node deleteNode = temp.next;
  //想要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)交由上一個(gè)節(jié)點(diǎn)來(lái)控制
  temp.next = deleteNode.next;
  //Java會(huì)回收它，設(shè)置不設(shè)置為null應(yīng)該沒(méi)多大意義了(個(gè)人覺(jué)得,如果不對(duì)請(qǐng)指出哦～)
  deleteNode = null;
  return;
  }
  currentPos++;
  temp = temp.next;
 }
 }

3.6對(duì)鏈表進(jìn)行排序

前面已經(jīng)講過(guò)了8種的排序算法了【八種排序算法總結(jié)】，這次挑簡(jiǎn)單的冒泡排序吧(其實(shí)我是想寫快速排序的，嘗試了一下感覺(jué)有點(diǎn)難.....)

 /**
 * 對(duì)鏈表進(jìn)行排序
 *
 * @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找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

這個(gè)算法挺有趣的：設(shè)置兩個(gè)指針p1、p2，讓p2比p1快k個(gè)節(jié)點(diǎn)，同時(shí)向后遍歷，當(dāng)p2為空，則p1為倒數(shù)第k個(gè)節(jié)點(diǎn)

 /**
 * 找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)(設(shè)置兩個(gè)指針p1、p2，讓p2比p1快k個(gè)節(jié)點(diǎn)，同時(shí)向后遍歷，當(dāng)p2為空，則p1為倒數(shù)第k個(gè)節(jié)點(diǎn)
 *
 * @param head
 * @param k 倒數(shù)第k個(gè)節(jié)點(diǎn)
 */
 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個(gè)節(jié)點(diǎn)
 for (int i = 0; i < k - 1; i++)
  p2 = p2.next;
 // 只要p2為null，那么p1就是倒數(shù)第k個(gè)節(jié)點(diǎn)了
 while (p2.next != null) {

  p2 = p2.next;
  p1 = p1.next;
 }
 return p1;
 }

3.8刪除鏈表重復(fù)數(shù)據(jù)

跟冒泡排序差不多，只要它相等，就能刪除了～

 /**
 * 刪除鏈表重復(fù)數(shù)據(jù)(跟冒泡差不多，等于刪除就是了)
 *
 * @param head 頭節(jié)點(diǎn)
 */
 public static void deleteDuplecate(Node head) {
 //臨時(shí)節(jié)點(diǎn)，(從首節(jié)點(diǎn)開(kāi)始-->真正有數(shù)據(jù)的節(jié)點(diǎn))
 Node temp = head.next;

 //當(dāng)前節(jié)點(diǎn)(首節(jié)點(diǎn))的下一個(gè)節(jié)點(diǎn)
 Node nextNode = temp.next;
 while (temp.next != null) {
  while (nextNode.next != null) {
  if (nextNode.next.data == nextNode.data) {
   //將下一個(gè)節(jié)點(diǎn)刪除(當(dāng)前節(jié)點(diǎn)指向下下個(gè)節(jié)點(diǎn))
   nextNode.next = nextNode.next.next;
  } else {

   //繼續(xù)下一個(gè)
   nextNode = nextNode.next;
  }
  }
  //下一輪比較
  temp = temp.next;
 }
 }

3.9查詢鏈表的中間節(jié)點(diǎn)

這個(gè)算法也挺有趣的：一個(gè)每次走1步，一個(gè)每次走兩步，走兩步的遍歷完，然后走一步的指針，那就是中間節(jié)點(diǎn)

 /**
 * 查詢單鏈表的中間節(jié)點(diǎn)
 */
 public static Node searchMid(Node head) {
 Node p1 = head;
 Node p2 = head;
 // 一個(gè)走一步，一個(gè)走兩步，直到為null，走一步的到達(dá)的就是中間節(jié)點(diǎn)
 while (p2 != null && p2.next != null && p2.next.next != null) {
  p1 = p1.next;
  p2 = p2.next.next;
 }
 return p1;
 }

3.10通過(guò)遞歸從尾到頭輸出單鏈表

 /**
 * 通過(guò)遞歸從尾到頭輸出單鏈表
 *
 * @param head 頭節(jié)點(diǎn)
 */
 public static void printListReversely(Node head) {
 if (head != null) {
  printListReversely(head.next);
  System.out.println(head.data);
 }
 }

3.11反轉(zhuǎn)鏈表

 /**
 * 實(shí)現(xiàn)鏈表的反轉(zhuǎn)
 *
 * @param node 鏈表的頭節(jié)點(diǎn)
 */
 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;
 }

反轉(zhuǎn)鏈表參考自：https://www.jb51.net/article/136185.htm

四、最后

理解鏈表本身并不難，但做相關(guān)的操作就弄得頭疼，head.next next next next ....(算法這方面我還是薄弱啊..腦子不夠用了.....)寫了兩天就寫了這么點(diǎn)東西...

操作一個(gè)鏈表只需要知道它的頭指針就可以做任何操作了

1、添加數(shù)據(jù)到鏈表中

• 遍歷找到尾節(jié)點(diǎn)，插入即可(只要while(temp.next != null)，退出循環(huán)就會(huì)找到尾節(jié)點(diǎn))

2、遍歷鏈表

• 從首節(jié)點(diǎn)(有效節(jié)點(diǎn))開(kāi)始，只要不為null，就輸出

3、給定位置插入節(jié)點(diǎn)到鏈表中

• 首先判斷該位置是否有效(在鏈表長(zhǎng)度的范圍內(nèi))

• 找到想要插入位置的上一個(gè)節(jié)點(diǎn)
   將原本由上一個(gè)節(jié)點(diǎn)的指向交由插入的節(jié)點(diǎn)來(lái)指向
   上一個(gè)節(jié)點(diǎn)指針域指向想要插入的節(jié)點(diǎn)

• 

4、獲取鏈表的長(zhǎng)度

• 每訪問(wèn)一次節(jié)點(diǎn)，變量++操作即可

5、刪除給定位置的節(jié)點(diǎn)

• 首先判斷該位置是否有效(在鏈表長(zhǎng)度的范圍內(nèi))

• 找到想要插入位置的上一個(gè)節(jié)點(diǎn)
   將原本由上一個(gè)節(jié)點(diǎn)的指向后面一個(gè)節(jié)點(diǎn)

• 

6、對(duì)鏈表進(jìn)行排序

• 使用冒泡算法對(duì)其進(jìn)行排序

7、找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

• 設(shè)置兩個(gè)指針p1、p2，讓p2比p1快k個(gè)節(jié)點(diǎn)，同時(shí)向后遍歷，當(dāng)p2為空，則p1為倒數(shù)第k個(gè)節(jié)點(diǎn)

8、刪除鏈表重復(fù)數(shù)據(jù)

• 操作跟冒泡排序差不多，只要它相等，就能刪除了～

9、查詢鏈表的中間節(jié)點(diǎn)

• 這個(gè)算法也挺有趣的：一個(gè)每次走1步，一個(gè)每次走兩步，走兩步的遍歷完，然后走一步的指針，那就是中間節(jié)點(diǎn)

10、遞歸從尾到頭輸出單鏈表

• 只要下面還有數(shù)據(jù)，那就往下找，遞歸是從最后往前翻。

11、反轉(zhuǎn)鏈表

• 有遞歸和非遞歸兩種方式，我覺(jué)得是挺難的?？梢缘轿医o出的鏈接上查閱～

PS：每個(gè)人的實(shí)現(xiàn)都會(huì)不一樣，所以一些小細(xì)節(jié)難免會(huì)有些變動(dòng)，也沒(méi)有固定的寫法，能夠?qū)崿F(xiàn)對(duì)應(yīng)的功能即可～

關(guān)于“Java如何實(shí)現(xiàn)單向鏈表”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。