链表

在计算机科学中, 一个 链表 是数据元素的线性集合, 元素的线性顺序不是由它们在内存中的物理位置给出的。 相反, 每个元素指向下一个元素。它是由一组节点组成的数据结构,这些节点一起,表示序列。

简单的说， 链表由无数个节点组成，而节点=当前节点内容+下一个节点，当到了结尾，下一个节点指向null空指针。

分类

单向链表

一般为了标识链表的头部，会在第一个节点加上head标识：

双向链表

在计算机科学中, 一个 双向链表(doubly linked list) 是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段，称为链接，它们是对节点序列中上一个节点和下一个节点的引用。开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点，通常是前哨节点或null，以方便遍历列表。如果只有一个前哨节点，则列表通过前哨节点循环链接。它可以被概念化为两个由相同数据项组成的单链表，但顺序相反。

循环链表

循环链表同时又可以区分为 单向循环链表、双向循环链表

优缺点

• 优点：适合动态插入和删除的应用场景

• 缺点：不能快速的定位和随机访问数据

应用场景（非前端）

从网上搜索来的几种应用场景：

• LRU 缓存淘汰算法。
• 各类缓冲池 和 栈 的实现。
• 使用链接来解决哈希冲突的哈希表。
• 简单的内存分配器。
• FAT文件系统中大文件的元数据。

基本上，前端都没有场景可以应用到链表数据结构，所以很多时候前端开发者学习链表

代码实现

在JavaScript，并没有直接以链表为结构的数据类型，所以如果我们要在JavaScript实现一个链表，需要自己去实现。

一个完整链表结构LinkNode 包括几块：

1. 属性：节点内容+下一个节点指向next
2. 方法：新增、删除等方法

单向链表

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

    toString() {
        return this.value;
    }
}

class LinkList {
    // 构造函数
    constructor() {
        this.head = null;
        this.length = 0;
    }

    // 追加
    append(value) {
        const node = new LinkNode(value);
        if (this.head === null) {
            this.head = node;
        } else {
            let current = this.head;
            // 将当前节点挪到最后
            while (current.next) {
                current = current.next;
            }
            current.next = node;

        }
        this.length++;
        return this;
    }

    // 在指定对象插入链表节点
    insert(existValue, insertValue) {
        const node = new LinkNode(insertValue);
        const existNode = this.find(existValue);
        if (existNode === null) {
            throw new Error("插入的节点值不存在");
        }
        const nextNode = existNode.next;
        existNode.next = node;
        node.next = nextNode;
        this.length++;
        return this;
    }

    // 删除指定对象 返回删除节点
    remove(value) {
        if (this.head === null) {
            throw new Error("链表为空，无法删除");
        }
        // 第一个删除
        if (this.head.value === value) {
            const current = this.head;
            this.head = this.head.next;
            current.next = null;
            this.length--;
            return current;
        }

        // 查找前一个
        const preNode = this.findPre(value)
        if (preNode !== null) {
            const removeNode = preNode.next;
            const nextNode = removeNode.next;
            preNode.next = nextNode;
            removeNode.next = null;
            this.length--;
            return removeNode;
        }
    }

    // 查询
    find(value) {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        while (current.next && current.value !== value) {
            current = current.next
        }
        if (current.value === value) {
            return current;
        }
        return null;
    }

    // 查询值的前一个
    findPre(value) {
        let current = this.head;
        let prevNode = null;
        while (current.next && current.next.value !== value) {
            current = current.next;
        }
        if (current.next && current.next.value === value) {
            prevNode = current;
        }

        return prevNode
    }

    toString() {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        const array = [];
        while (current.next) {
            array.push(current.value);
            current = current.next;
        }
        array.push(current.value);
        return array.join('->');
    }
}

// 测试案例
const linkList = new LinkList();

linkList.append("1");
linkList.append("2");
linkList.append("3");

// 预期输出1->2->3
console.log(linkList.toString());

linkList.insert("2", "4");
// 预期输出1->2->4->3
console.log(linkList.toString());

linkList.remove("2");
// 预期输出1->4->3
console.log(linkList.toString());

双向链表

相比较单向链表，多了一个指向前者对象 prev。

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

    toString() {
        return this.value;
    }
}

class LinkList {
    // 构造函数
    constructor() {
        this.head = null;
        this.length = 0;
    }

    // 追加
    append(value) {
        const node = new LinkNode(value);
        if (this.head === null) {
            this.head = node;
        } else {
            let current = this.head;
            // 将当前节点挪到最后
            while (current.next) {
                current = current.next;
            }
            current.next = node;
            node.prev = current;

        }
        this.length++;
        return this;
    }

    // 在指定对象插入链表节点
    insert(existValue, insertValue) {
        const node = new LinkNode(insertValue);
        const existNode = this.find(existValue);
        if (existNode === null) {
            throw new Error("插入的节点值不存在");
        }
        const nextNode = existNode.next;
        existNode.next = node;
        node.next = nextNode;

        node.prev = existNode;
        nextNode.prev = node;

        this.length++;
        return this;
    }

    // 删除指定对象 返回删除节点
    remove(value) {
        if (this.head === null) {
            throw new Error("链表为空，无法删除");
        }
        // 第一个删除
        if (this.head.value === value) {
            const current = this.head;
            this.head = this.head.next;
            current.next = null;
            this.length--;
            return current;
        }

        // 查找前一个
        const preNode = this.findPre(value)
        if (preNode !== null) {
            const removeNode = preNode.next;
            const nextNode = removeNode.next;
            const prevNode = removeNode.prev;
            preNode.next = nextNode;
            nextNode.prev = preNode;

            removeNode.next = null;
            removeNode.prev = null;
            this.length--;
            return removeNode;
        }
    }

    // 查询
    find(value) {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        while (current.next && current.value !== value) {
            current = current.next
        }
        if (current.value === value) {
            return current;
        }
        return null;
    }

    // 查询值的前一个
    findPre(value) {
        let current = this.head;
        let prevNode = null;
        while (current.next && current.next.value !== value) {
            current = current.next;
        }
        if (current.next && current.next.value === value) {
            prevNode = current;
        }

        return prevNode
    }

    toString() {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        const array = [];
        while (current.next) {
            array.push(current.value);
            current = current.next;
        }
        array.push(current.value);
        return array.join('<->');
    }
}

// 测试案例
const linkList = new LinkList();

linkList.append("1");
linkList.append("2");
linkList.append("3");

// 预期输出 1<->2<->3
console.log(linkList.toString());

linkList.insert("2", "4");
// 预期输出 1<->2<->4<->3
console.log(linkList.toString());

linkList.remove("2");
// 预期输出 1<->2<->3
console.log(linkList.toString());

循环链表

循环链表对比之前，会把最后一个节点的netx指向第一个节点， 第一个节点的prev指向最后一个节点

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

    toString() {
        return this.value;
    }
}

class LinkList {
    // 构造函数
    constructor() {
        this.head = null;
        this.length = 0;
    }

    // 追加
    append(value) {
        const node = new LinkNode(value);
        if (this.head === null) {
            this.head = node;
        } else {
            let current = this.head;
            // 将当前节点挪到最后 由于循环 这里需要多判断一个是否指向头部
            while (current.next && current.next !== this.head) {
                current = current.next;
            }
            current.next = node;
            node.prev = current;

            // 将最后一个指针指向第一个
            node.next = this.head;
            this.head.prev = node;
        }
        this.length++;
        return this;
    }

    // 在指定对象插入链表节点
    insert(existValue, insertValue) {
        const node = new LinkNode(insertValue);
        const existNode = this.find(existValue);
        if (existNode === null) {
            throw new Error("插入的节点值不存在");
        }
        const nextNode = existNode.next;
        existNode.next = node;
        node.next = nextNode;

        node.prev = existNode;
        nextNode.prev = node;

        this.length++;
        return this;
    }

    // 删除指定对象 返回删除节点
    remove(value) {
        if (this.head === null) {
            throw new Error("链表为空，无法删除");
        }
        // 第一个删除
        if (this.head.value === value) {
            const current = this.head;
            this.head = current.next;
            this.head.prev = current.prev;

            current.next = null;
            current.prev = null;
            this.length--;
            return current;
        }

        // 查找前一个
        const preNode = this.findPre(value)
        if (preNode !== null) {
            const removeNode = preNode.next;
            const nextNode = removeNode.next;
            const prevNode = removeNode.prev;
            prevNode.next = nextNode;
            nextNode.prev = preNode;

            removeNode.next = null;
            removeNode.prev = null;
            this.length--;
            return removeNode;
        }
    }

    // 查询
    find(value) {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        while (current.next != this.head && current.value !== value) {
            current = current.next
        }
        if (current.value === value) {
            return current;
        }
        return null;
    }

    // 查询值的前一个
    findPre(value) {
        let current = this.head;
        let prevNode = null;
        while (current.next != this.head && current.next.value !== value) {
            current = current.next;
        }
        if (current.next && current.next.value === value) {
            prevNode = current;
        }

        return prevNode
    }

    toString() {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        const array = [];
        while (current.next != this.head) {
            array.push(current.value);
            current = current.next;
        }
        array.push(current.value);
        return array.join('<->');
    }
}

// 测试案例
const linkList = new LinkList();

linkList.append("1");
linkList.append("2");
linkList.append("3");

// 预期输出 1<->2<->3
console.log(linkList.toString());

linkList.insert("2", "4");
// 预期输出 1<->2<->4<->3
console.log(linkList.toString());

linkList.remove("2");
// 预期输出 1<->2<->3
console.log(linkList.toString());

// 第一个的prev 指向最后 输出3
console.log(linkList.head.prev.toString());

// 最后一个 next指向第一个 输出1
console.log(linkList.head.prev.next.toString());