免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

鏈表下面其實(shí)又細(xì)分了3種：單鏈表、雙向鏈表和循環(huán)鏈表。今天我們先講單鏈表。

二、單鏈表介紹

什么是單鏈表呢？單鏈表就是每一個節(jié)點(diǎn)只有一個指針域的鏈表。如下圖所示，就是一個帶頭節(jié)點(diǎn)的單鏈表。下面我們需要知道什么是頭指針，頭節(jié)點(diǎn)和首元節(jié)點(diǎn)。

頭指針：指向鏈表節(jié)點(diǎn)的第一個節(jié)點(diǎn)的指針

頭節(jié)點(diǎn)：指在鏈表的首元節(jié)點(diǎn)之前附設(shè)的一個節(jié)點(diǎn)

首元節(jié)點(diǎn)：指在鏈表中存儲第一個實(shí)際數(shù)據(jù)元素的節(jié)點(diǎn)（比如上圖的 a1 節(jié)點(diǎn)）

三、單鏈表的創(chuàng)建

單鏈表的創(chuàng)建有兩種方式，分別是頭插法和尾插法。

1、頭插法

頭插法，顧名思義就是把新元素插入到頭部的位置，每次新加的元素都作為鏈表的第一個節(jié)點(diǎn)。那么頭插入法在Java中怎么實(shí)現(xiàn)呢。首先我們需要定義一個節(jié)點(diǎn)，如下

public class ListNode {
  public int val; //數(shù)據(jù)域
  public ListNode next;//指針域
}

然后我們就創(chuàng)建一個頭指針（不帶頭節(jié)點(diǎn)）

//元素個數(shù)
int n = 5;
//創(chuàng)建一個頭指針
ListNode headNode = new ListNode();
//頭插入法
headNode= createHead(headNode, n);

然后創(chuàng)建一個私有方法去實(shí)現(xiàn)頭插法，這里我們插入5個新元素，頭插入的核心是要先斷開首元節(jié)點(diǎn)和頭指針的連接，也就是需要先將原來首元節(jié)點(diǎn)的地址存放到新節(jié)點(diǎn)的指針域里，也就是 newNode.next = headNode.next，然后再讓頭指針指向新的節(jié)點(diǎn) headNode.next = newNode，這兩步是頭插入的核心，一定要理解。

/**
 * 頭插法
 * 新的節(jié)點(diǎn)放在頭節(jié)點(diǎn)的后面，之前的就放在新節(jié)點(diǎn)的后面
 * @param headNode 頭指針
 * @return
 */
private static ListNode createHead(ListNode headNode, int n) {
  //插入5個新節(jié)點(diǎn)
  for (int i = 1; i <= n; i++) {
    ListNode newNode = new ListNode();
    newNode.val = i;
    //將之前的所有節(jié)點(diǎn)指向新的節(jié)點(diǎn)（也就是新節(jié)點(diǎn)指向之前的所有節(jié)點(diǎn)）
    newNode.next = headNode.next;
    //將頭指針指向新的節(jié)點(diǎn)
    headNode.next = newNode;
  }
  return headNode;
}

最后我把鏈表打印輸出一下（其實(shí)也是單鏈表的遍歷），判斷條件就是只有當(dāng)指針域?yàn)榭盏臅r(shí)候才是最后一個節(jié)點(diǎn)。

private static void printLinkedList(ListNode headNode) {
  int countNode = 0;
  while (headNode.next != null){
    countNode++;
    System.out.println(headNode.next.val);
    headNode = headNode.next;
  }
  System.out.println("該單鏈表的節(jié)點(diǎn)總數(shù)：" +countNode);
}

最后的輸出結(jié)果顯然是逆序，因?yàn)闆]一個新的元素都是從頭部插入的，自然第一個就是最后一個，最后一個就是第一個：

2、尾插法

尾插法，顧名思義就是把新元素插入到尾部的位置（也就是最后一個位置），每次新加的元素都作為鏈表的第最后節(jié)點(diǎn)。那么尾插法在 Java 中怎么實(shí)現(xiàn)呢，這里還是采用不帶頭節(jié)點(diǎn)的實(shí)現(xiàn)方式，頭節(jié)點(diǎn)和頭指針和頭插入的實(shí)現(xiàn)方式一樣，這里我就直接將如何實(shí)現(xiàn)：

/**
 * 尾插法
 * 找到鏈表的末尾結(jié)點(diǎn)，把新添加的數(shù)據(jù)作為末尾結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)
 * @param headNode
 */
private static ListNode createByTail(ListNode headNode, int n) {
  //讓尾指針也指向頭指針
  ListNode tailNode = headNode;
  for (int i = 1; i <= n; i++) {
    ListNode newNode = new ListNode();
    newNode.val = i;
    newNode.next = null;

    //插入到鏈表尾部
    tailNode.next = newNode;
    //指向新的尾節(jié)點(diǎn)，tailer永遠(yuǎn)存儲最后一個節(jié)點(diǎn)的地址
    tailNode = newNode;

  }
  return headNode;
}

和頭插入不同的是，我們需要聲明一個尾指針來輔助我們實(shí)現(xiàn)，最開始，尾指針指向頭指針，每插入一個元素，尾指針就后移一下，這里我們來講一下原理：每次往末尾新加一個節(jié)點(diǎn)，我們就需要把原來的連接斷開，那怎么斷開呢，我們首先需要讓尾指針指向新的節(jié)點(diǎn)，也就是 tailNode.next = newNode; 然后再讓尾指針后移一個位置，讓尾指針指向最后一個節(jié)點(diǎn)。也就是尾指針始終指向最后一個節(jié)點(diǎn)，最后將頭指針返回，輸出最后結(jié)果：

四、單鏈表的刪除

既然單鏈表創(chuàng)建好了，怎么在鏈表里面刪除元素呢，單鏈表的刪除，我分為了兩種情況刪除，分別是刪除第i個節(jié)點(diǎn)和刪除指定元素的節(jié)點(diǎn)。

1、刪除第i個節(jié)點(diǎn)

我們可以先來理一下思路：在單鏈表里，節(jié)點(diǎn)與節(jié)點(diǎn)之間都是通過指針域鏈接起來的，所以如果我們想實(shí)現(xiàn)刪除的操作，實(shí)際上是需要我們?nèi)ジ淖兿鄳?yīng)指針域?qū)?yīng)得地址的。當(dāng)想去刪除第i個元素的時(shí)候，比如要刪除上圖的第3個元素（也就是3），實(shí)際上我們要做的就是要讓2號元素指向4號元素（其實(shí)就是需要修改2號元素的指針域，讓2號元素的指針域存儲4號元素）。那么怎么做才能實(shí)現(xiàn)這一步呢？很顯然，要實(shí)現(xiàn)這個步驟，我們必須要找到4號元素和2號元素，但是再仔細(xì)想一下，其實(shí)我們只需要找到2號元素就可以了，因?yàn)?號元素的地址存儲再2號的下一個元素的指針域里面。

所以綜上所述分析我們可以得出刪除的兩個核心步驟：

1.刪除第i個節(jié)點(diǎn)，需要先找到第 i-1 個個節(jié)點(diǎn)，也就是第i個節(jié)點(diǎn)的前一個節(jié)點(diǎn)；

2.然后讓第 i-1 個節(jié)點(diǎn)指向第 i-1 個節(jié)點(diǎn)的下下個節(jié)點(diǎn)

下面的代碼具體實(shí)現(xiàn)了怎么刪除第i個元素。

/**
 * 刪除第i個節(jié)點(diǎn)
 * 1,2 4,4,5
 * 刪除之后應(yīng)該是1,2,4,5
 * @param headNode
 * @param index
 * @return
 */
public static ListNode deleteNodeByIndex(ListNode headNode, int index) {
  int count = 1;
  //將引用給它
  ListNode preNode = headNode;
  //看計(jì)數(shù)器是不是到了i-1，如果到了i-1,就找到了第i-1個節(jié)點(diǎn)
  while (preNode.next != null && count <= index -1){
    //尋找要刪除的當(dāng)前節(jié)點(diǎn)的前一個節(jié)點(diǎn)
    count++;
    preNode = preNode.next;
  }
  if (preNode != null){
    preNode.next = preNode.next.next;
  }
  return headNode;
}

2、刪除指定元素的那個節(jié)點(diǎn)

刪除指定元素節(jié)點(diǎn)的實(shí)現(xiàn)方法有兩種，第一種就是先找到指定元素對應(yīng)的鏈表的位置（ index ），然后再按照刪除第 i 個節(jié)點(diǎn)的思路刪除即可。實(shí)現(xiàn)方法如下圖所示：

/**
 * 刪除鏈表指定數(shù)值的節(jié)點(diǎn)
 * @param headNode
 * @param val
 * @return
 */
private static ListNode deleteNodeByNum(ListNode headNode, int val) {
  ListNode deleteOne = headNode;
  int countByDeleteOne = 1;
  while (deleteOne.next != null){
    if (deleteOne.next.val == val){
      deleteOne = deleteOne.next;
      break;
    }
    countByDeleteOne ++;
    deleteOne = deleteOne.next;
  }
  return deleteNodeByIndex(headNode, countByDeleteOne);
}

第二種方法的實(shí)現(xiàn)就很精妙（前提是此節(jié)點(diǎn)不是尾節(jié)點(diǎn)）

public void deleteNode(ListNode node) {
  //刪除node即通過將后面的值賦給node，然后更改node的指針指向下下一個結(jié)點(diǎn)即可
  node.val = node.next.val;
  node.next = node.next.next;
}

五、單鏈表的查詢（及修改）

單鏈表的查詢實(shí)現(xiàn)很簡單，就是遍歷當(dāng)前單鏈表，然后用一個計(jì)數(shù)器累加到當(dāng)前下標(biāo)，那么當(dāng)前的這個節(jié)點(diǎn)就是要查詢的那個節(jié)點(diǎn)，然后再返回即可，當(dāng)然需要判斷傳過來的這個下標(biāo)是否合法。當(dāng)然如果需要修改，就需要把當(dāng)前找到的節(jié)點(diǎn)的數(shù)據(jù)域重新賦上需要修改的值即可，這里就不上代碼了。具體實(shí)現(xiàn)如下：

private static ListNode searchLinkedList(ListNode headNode, int index) {
  //如果下標(biāo)是不合法的下標(biāo)就表示找不到
  if (index < 1 || index > getLinkedListLength(headNode)){
      return null;
  }
  for (int i = 0; i < index; i++) {
    headNode = headNode.next;
  }
  return headNode;
}

獲取單鏈表的長度（注意我這里定義的 headNode 是頭指針不是頭節(jié)點(diǎn)）

/**
 * 求單鏈表長度
 * @param headNode
 * @return
 */
private static int getLinkedListLength(ListNode headNode) {
  int countNode = 0;
  while (headNode.next != null){
    countNode++;
    headNode = headNode.next;
  }
 return countNode;
}

六、小結(jié)

單鏈表的相關(guān)操作就講解完了，其實(shí)通過上面對單鏈表的相關(guān)操作，我們不難發(fā)現(xiàn)，單鏈表的刪除和插入其實(shí)很方便，只需要改變指針的指向就可以完成，但是查找元素的時(shí)候就比較麻煩，因?yàn)樵诓檎业臅r(shí)候，需要把整個鏈表從頭到尾遍歷一次。