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

維基百科

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

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

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

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

從上面可以得知：

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

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

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

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

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

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

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

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

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

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

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

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

      if (position === 0) {
        node.next = current;         //此時(shí)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這個(gè)指針就交給previous。
          current = current.next;    // 這個(gè)跟append方法一樣的。
        }                            // 是當(dāng)前位置啦，就退出循環(huán)。
        previous.next = node;        // 前一個(gè)節(jié)點(diǎn)的next指向node（插入的節(jié)點(diǎn)）
        node.next = current;         // node.next就是current啦。
      }
      this.length++;
      console.log("Insert successfully");
    } else {
      throw new Error("這個(gè)單鏈表中不能從這個(gè)位置加入節(jié)點(diǎn)");
    }
  }

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

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

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

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

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

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

個(gè)人源碼地址

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