1. 什么是链表

• 链表类似于火车：有一个火车头，一堆车厢。火车头会通过节点连接车厢，车厢间也会使用节点依次串联起来。
  
• 链表的数据结构
  

2. 链表与数组对比

共同点

• 都是用于存储一系列元素

不同点

• 数组
  • 优点：
    • 编程语言基本都会内置数组结构，使用简单方便
    • 用[]访问对应的元素，访问的时间复杂度为O(1)
  • 缺点：
    • 固定大小：大多数编程语言定义数组时，需要先声明大小。（js不需要，js底层会根据数组大小，自动伸缩管理容量）
    • 连续空间：在开辟内存时，需要申请连续的空间
    • 数组越往前增删元素时，时间复杂度越高。（js底层为保证连续性，需要移动增删位置之后的元素）
• 链表
  • 优点：
    • 申请空间时不需要事先确定大小
    • 不需要申请连续的内存空间，内存利用率更高
    • 越往前对链表增删，时间复杂度越低，增删开头时间复杂度为O(1)
  • 缺点
    • 访问任意位置元素时，需要从头开始遍历，时间复杂度为O(N)

3. 链表代码的实现

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

class LinkedList {
    constructor() {
        this.count = 0;
        this.head = null;
    }
    // 链表尾部追加元素
    append(value) {
        let newNode = new Node(value);
        if (this.head === null) {
            this.head = newNode;
        } else {
            let currentNode = this.getElementAt(this.count - 1);
            currentNode.next = newNode;
        }
        this.count++;
    }
    // 在指定位置插入元素，越界返回false，表示插入失败
    insert(index, value) {
        if (index < 0 || index > this.count) {
            return false;
        }
        let newNode = new Node(value);

        if (this.head === null) {
            this.head = newNode;
        } else if (index === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let lastNode = this.getElementAt(index - 1);
            newNode.next = lastNode.next;
            lastNode.next = newNode;
        }
        this.count++;
        return true;
    }
    // 移除指定元素。若找不到该元素，则返回false，表示移除失败
    remove(value) {
        let lastNode = null;
        let currentNode = this.head;
        while (currentNode) {
            if (currentNode.value === value) {
                if (lastNode === null) {
                    this.head = this.head.next;
                } else {
                    lastNode.next = currentNode.next;
                }
                this.count--;
                return true;
            }
            lastNode = currentNode;
            currentNode = currentNode.next;
        }
        return false;
    }
    // 移除指定位置上的元素。若找不到该位置，则返回false，表示移除失败
    removeAt(index) {
        if (index < 0 || index > this.count - 1) {
            return false;
        }
        if (index === 0) {
            this.head = this.head.next;
        } else {
            let lastNode = this.getElementAt(index - 1);
            lastNode.next = lastNode.next.next;
        }
        this.count--;
        return true;
    }
    // 返回指定位置的节点，越界返回undefined
    getElementAt(index) {
        if (index < 0 || index >= this.count) {
            return undefined;
        }
        let currentNode = this.head;
        for (let i = 0; i < index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode;
    }
    // 返回元素的索引值，若没改元素则返回-1
    indexOf(value) {
        let currentNode = this.head;
        let index = 0;
        while (currentNode) {
            if (currentNode.value === value) {
                return index;
            }
            currentNode = currentNode.next;
            index++;
        }
        return -1;
    }
    // 返回链表元素个数
    size() {
        return this.count;
    }
    // 返回当前是否为空链表
    isEmpty() {
        return this.count === 0
    }
    // 清空链表
    clear() {
        this.count = 0;
        this.head = null;
    }
    // 输出链表每项元素
    toString() {
        let arr = [];
        let currentNode = this.head;
        while (currentNode) {
            arr.push(currentNode.value);
            currentNode = currentNode.next;
        }
        return arr.join(",")
    }
}

4. 线上代码

戳我查看，含测试代码

5. 应用场景

• 结合数组缺点、链表优点，可得出当频繁对数据增删的话，用链表效率更高；若是频繁读取数据，则数组更优。
• 队列数据结构，之前是基于数组，在出栈时效率没有基于链表的效率高，后面基于双向链表再实现队列。

6. 相关文章

• 上一篇：前端es6实现优先级队列
• 下一篇：双向链表（暂未更新）
• 相关篇：es6实现队列数据结构（基于数组）