_链表:是一种物理存储单元上非连续、非顺序的存储结构。由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表和数组相比优势在于：
- 不需要事先知道存储数据的大小
- 不需要连续的存储空间
- 添加或删除一个新数据节点的效率很快
创建节点
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
