_鏈表:是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)。由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

鏈表和數(shù)組相比優(yōu)勢(shì)在于：

1. 不需要事先知道存儲(chǔ)數(shù)據(jù)的大小
2. 不需要連續(xù)的存儲(chǔ)空間
3. 添加或刪除一個(gè)新數(shù)據(jù)節(jié)點(diǎn)的效率很快

創(chuàng)建節(jié)點(diǎn)

class Node {
  constructor(val) {
    this.val = val; // 結(jié)點(diǎn)值
    this.next = null; // 結(jié)點(diǎn)下一項(xiàng)
  }
}

創(chuàng)建鏈表類

class LinkedList {
  constructor() {
    this.headNode = new Node('head'); // 初始化一個(gè)頭結(jié)點(diǎn)
  }
    
  /** 在鏈表尾部插入 */
  insert(val) {
    let currentNode = this.headNode,
        lastNode = new Node(val);
    
    // 找到當(dāng)前鏈表最后一項(xiàng)
    while(true) {
      if(currentNode.next == null) {
        break;
      } else {
        currentNode = currentNode.next;
      }
    }
    
    lastNode.next = currentNode.next;
    currentNode.next = lastNode;
  }
    
  /** 展示鏈表項(xiàng) */
  display() {
    let currentNode = this.headNode;
    while(currentNode.next != null) {
      console.log(currentNode.next.val);
      currentNode = currentNode.next;
    }
  }
    
  /** 移除鏈表項(xiàng) */
  remove(val) {
    let currentNode = this.headNode;
    
    while(true) {
      if(currentNode.next.val == val) {
        break;
      } else {
        currentNode = currentNode.next;
      }
    }
    
    currentNode.next = currentNode.next.next;
  }
}

測(cè)試用例

var nodes = new LinkedList();

nodes.insert('apple');
nodes.insert('banana');
nodes.insert('orange');

nodes.display()

console.log('----------')

nodes.remove('apple');

nodes.display()

輸出結(jié)果為

apple
banana
orange
----------
banana 
orange

至此，我們就實(shí)現(xiàn)了一個(gè)基本的單向鏈表