摘要：一個單向鏈表包含兩個值當(dāng)前節(jié)點(diǎn)的值和一個指向下一個節(jié)點(diǎn)的鏈接。為退出循環(huán)即已到了最后一個節(jié)點(diǎn)那么它的為加入節(jié)點(diǎn)后，要把單鏈表長度加一。第個節(jié)點(diǎn)是運(yùn)行結(jié)果個人源碼地址單鏈表就寫到這里咯，接下來還會寫其他的數(shù)據(jù)結(jié)構(gòu)本人也在學(xué)習(xí)當(dāng)中。

維基百科

鏈表是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點(diǎn)里存到下一個節(jié)點(diǎn)的指針。

鏈表中最簡單的一種是單向鏈表，它包含兩個域，一個信息域和一個指針域。這個鏈接指向列表中的下一個節(jié)點(diǎn)，而最后一個節(jié)點(diǎn)則指向一個空值。

一個單向鏈表包含兩個值: 當(dāng)前節(jié)點(diǎn)的值和一個指向下一個節(jié)點(diǎn)的鏈接。

一般查找一個節(jié)點(diǎn)的時候需要從第一個節(jié)點(diǎn)開始每次訪問下一個節(jié)點(diǎn)，一直訪問到需要的位置。

從上面可以得知：

單鏈表的每一個節(jié)點(diǎn)里面有一個信息域（element）和一個指向下一個節(jié)點(diǎn)的指針（next）。

查找一個節(jié)點(diǎn)是從第一個節(jié)點(diǎn)（head）找起。

那先創(chuàng)建節(jié)點(diǎn)的類吧：

class Node {
  constructor (element) { //傳入數(shù)據(jù)
    this.element = element;
    this.next = null; //next是指向下一個節(jié)點(diǎn)的指針。
  }
}

接著創(chuàng)建單鏈表的類：

class SingleLinkedList {
  constructor () {
    this.head = null; // head指向第一個節(jié)點(diǎn)的指針。
    this.length = 0;
  }
｝

給單鏈表增加一些方法（以下的方法都是寫在單鏈表類里面的）

Append (加入一個節(jié)點(diǎn))

/**
   * @param element 一個數(shù)據(jù)，可以是任何的數(shù)據(jù)類型.
   */
append (element) {
    let node = new Node(element), // 實例化一個節(jié)點(diǎn)。
        current;                 

    if (!this.head) {             // 如果為空則為空鏈表
      this.head = node;           // 鏈表頭（head）指向第一個節(jié)點(diǎn)node。
    } else { // 不是空鏈表
      current = this.head;       // current也指向了第一個節(jié)點(diǎn)（用來從頭部開始進(jìn)行操作，且為了不改變head的指向）
      while (current.next) {     // 循環(huán)，直到某個節(jié)點(diǎn)的next為null
        current = current.next;  // 如果當(dāng)前節(jié)點(diǎn)（current）的next不為null，那么current.next這個指針就給了current。
      }
      current.next = node;       //current.next為null退出循環(huán)（即已到了最后一個節(jié)點(diǎn)）,那么它的next為node
    }
    this.length++;               //加入節(jié)點(diǎn)后，要把單鏈表長度加一。
    console.log("Append successfully");
}

InsertNode（在某位置加入一個節(jié)點(diǎn)）

/**
   * @param element 一個數(shù)據(jù)，可以是任何的數(shù)據(jù)類型.
   * @param {Number} position 要插入的某個位置. 
   */
  insertNode (element, position) {
    if (position >= 0 && position <= this.length) { // 判斷插入的位置。
      let node = new Node(element),
        current = this.head,          // current是指向第一個借點(diǎn)咯。
        previous,                     // 指向前一個節(jié)點(diǎn)的指針。
        index = 0;

      if (position === 0) {
        node.next = current;         //此時head的指向的節(jié)點(diǎn)，變?yōu)榱薾ode指向的節(jié)點(diǎn)
        this.head = node;            // 而head當(dāng)然指向node咯
      } else {
        while (index++ < position) { // index是否是要插入的位置，不是就+1。
          previous = current;        // 不是當(dāng)前位置，那么current這個指針就交給previous。
          current = current.next;    // 這個跟append方法一樣的。
        }                            // 是當(dāng)前位置啦，就退出循環(huán)。
        previous.next = node;        // 前一個節(jié)點(diǎn)的next指向node（插入的節(jié)點(diǎn)）
        node.next = current;         // node.next就是current啦。
      }
      this.length++;
      console.log("Insert successfully");
    } else {
      throw new Error("這個單鏈表中不能從這個位置加入節(jié)點(diǎn)");
    }
  }

RemoveNode （刪除一個節(jié)點(diǎn)）

/** 
   * @param {Number} position 要刪除節(jié)點(diǎn)的位置
   */
  removeNode (position) {
    if (position > -1 && position < this.length) { //判斷是否存在這position。
      let current = this.head,         // 同上面一樣，用current來循環(huán)。
        previous,
        index = 0;

      if (position === 0) {
        this.head = current.next;     //head變?yōu)橹赶蛳乱粋€節(jié)點(diǎn)。
      } else {
        while (index++ < position) {  //判斷是否為當(dāng)前的位置。
          previous = current;         // current就變?yōu)榍耙粋€節(jié)點(diǎn) （指針變化）。
          current = current.next;     
        }                             // 確定要刪除節(jié)點(diǎn)的位置，退出循環(huán)。
        previous.next = current.next; // 當(dāng)前節(jié)點(diǎn)為current，那么移除它，這時前一個的節(jié)點(diǎn)就和后一個節(jié)點(diǎn)連在一起咯。
      }
      this.length--;                  // 長度減一。
      console.log("Remove successfully");
    } else {
      throw new Error("單鏈表沒這個節(jié)點(diǎn)哦。");
    }
}

Print (輸出單鏈表的每個節(jié)點(diǎn))

print () {
    let arr = [this.head];  // 我用了數(shù)組包住了每個節(jié)點(diǎn)。
    let node = this.head;
    while (node.next) {     // 下一個節(jié)點(diǎn)是否存在。
      node = node.next;
      arr.push(node);
    }
    arr.map( (x, index) => {
      console.log(`第${index + 1}個節(jié)點(diǎn)是:`);
      console.log(x);
    });
}

運(yùn)行結(jié)果：

個人源碼地址

單鏈表就寫到這里咯，接下來還會寫其他的數(shù)據(jù)結(jié)構(gòu)（本人也在學(xué)習(xí)當(dāng)中）。第一次寫文章，有錯漏之處，希望指出。代碼也有可以精簡的地方，不過這樣我覺讓人看得明白些（大神輕噴）。不過也總算踏出了寫文章的第一步，還是很開心的。^_^