单项链表（JavaScript实现）

_链表:是一种物理存储单元上非连续、非顺序的存储结构。由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表和数组相比优势在于：

1. 不需要事先知道存储数据的大小
2. 不需要连续的存储空间
3. 添加或删除一个新数据节点的效率很快

创建节点

class Node {
  constructor(val) {
    this.val = val; // 结点值
    this.next = null; // 结点下一项
  }
}

创建链表类

class LinkedList {
  constructor() {
    this.headNode = new Node('head'); // 初始化一个头结点
  }
    
  /** 在链表尾部插入 */
  insert(val) {
    let currentNode = this.headNode,
        lastNode = new Node(val);
    
    // 找到当前链表最后一项
    while(true) {
      if(currentNode.next == null) {
        break;
      } else {
        currentNode = currentNode.next;
      }
    }
    
    lastNode.next = currentNode.next;
    currentNode.next = lastNode;
  }
    
  /** 展示链表项 */
  display() {
    let currentNode = this.headNode;
    while(currentNode.next != null) {
      console.log(currentNode.next.val);
      currentNode = currentNode.next;
    }
  }
    
  /** 移除链表项 */
  remove(val) {
    let currentNode = this.headNode;
    
    while(true) {
      if(currentNode.next.val == val) {
        break;
      } else {
        currentNode = currentNode.next;
      }
    }
    
    currentNode.next = currentNode.next.next;
  }
}

测试用例

var nodes = new LinkedList();

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

nodes.display()

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

nodes.remove('apple');

nodes.display()

输出结果为

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

至此，我们就实现了一个基本的单向链表