在上个笔记中，我们分享了JavaScript中的数组，了解到数组的一些特点，比如顺序存储数据，以及一些常用的操作的复杂度，比如数组的访问，arr[i]是O(1)的复杂度，但是如果是插入和删除的话，就需要O(n)的时间复杂度了，接下来，我们要分享的数据结构--链表，它的插入、删除的时间复杂度为O(1)，相比数组的话，好了很多。

先来张图，了解一下链表的数据结构

链表的数据结构

从图中我们可以看到，链表存储不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。

在Javascript中，数组已经是内部实现的，可以直接用，但是链表是没有的，所以需要我们自己来实现。

对于链表，我们需要声明一个Node的类，Node类表示我们想要添加到链表中的项。它包含一个 val属性，该属性表示要加入链表元素的值;以及一个next属性，该属性是指向链表中下一个元素的指针。

class Node {	constructor(val) {  	this.val = val;    this.next = null;  }}

然后是我们的链表，在数组中，我们可以直接访问任何位置 的任何元素，而要想访问链表中间的一个元素，则需要从起点(表头)开始迭代链表直到找到所需的元素。

所以我们的链表的实现如下

class LinkedList {	constructor(compareFun) {  	this.compareFun = compareFun; // 辅助函数，主要用来对节点的val做对比，来构造链表结构    this.head = null; // t    this.size = 0; // 记录链表长度  }}

然后我们需要一步一步实现链表操作，需要的一些api方法，

1.向链表末尾添加元素（push）

class LinkedList {	// .... 其他的一些方法  push(val) {    const node = new Node(val);    let current;    if (this.head == null) {    	this.head = node;    } else {    	current = this.head;      while(current.next != null) {        current = current.next;      }      // 从头遍历到最后，找到node.next == null的节点，然后将节点赋值       current.next = node;    }  }  this.size++;}

图示：链表插入一个元素

插入一个元素

2.移除链表中的某个元素（remove）

class LinkedList {	remove(index) {    let current = this.head;  	if (index >= 0 && index < this.size) {    	if (index === 0) {        // 特殊情况，要移除head，需要特别处理        this.head = current.next;      } else {      	let prev = null;        for (let i = 0; i < index; i++) {        	prev = current;          current = current.next;        }        prev.next = current.next;      }      this.size--;    	return current.element;    }    return null;  }}

图示：链表删除一个元素

链表删除head

链表删除其他的元素

3.链表仁义位置插入元素

class LinkedList {	insert(index, val) {  	if (index >= 0 && index <= this.size) {      const node = new Node(val);      const current = this.head;      if (index === 0) { // 如果要插入的位置实在头部        node.next = current.next;        this.head = node;      } else {      	let prev;        for (let i = 0; i < index; i++) {          pre = current;          current = urrent.nextl        }      }    }  }}

图示：链表任意位置插入一个元素

插入位置在头部

任意位置插入一个元素

总之，链表的操作就是从头部遍历，找到需要操作的元素，然后对指针做响应的调整。手敲一遍加深理解，下篇用一个简单的力扣题，加以练习。