实现链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。在数组中，我们可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，则需要从起点(表头)开始迭代链表直到找到所 需的元素。

单链表

class Node {
    constructor(element) {
        this.element = element
        this.next = undefined
    }
}

const defaultEquals = (a, b) => a === b

class LinkedList {
    constructor(equalsFn = defaultEquals) {
        this.count = 0;
        this.head = undefined
        this.equalsFn = equalsFn
    }

    /**
     * 向链表尾部添加一个新元素
     * @param {*} element 
     */
    push(element) {
        const node = new Node(element)
        let current
        if (this.head == null) {
            this.head = node
        } else {
            current = this.head
            // 获得最后一项
            while (current.next != null) {
                current = current.next
            }
            // 将其 next作为新元素,建立链接
            current.next = node
        }
        this.count++
    }

    /**
     * 向链表的特定位置插入一个新元素
     * @param {*} element 
     * @param {*} index 
     */
    insert(element, index) {
        if (index >= 0 && index <= this.count) {
            const node = new Node(element)
            if (index === 0) {
                const current = this.head
                node.next = current
                this.head = node
            } else {
                const previous = this.getElementAt(index - 1)
                const current = previous.next
                node.next = current
                previous.next = node
            }
            this.count++
            return true
        }
        return false
    }

    /**
     * 返回链表中特定位置的元素
     * @param {*} index 
     */
    getElementAt(index) {
        if (index >= 0 && index <= this.count) {
            let node = this.head
            for (let i = 0; i < index && node != null; i++) {
                node = node.next
            }
            return node
        }
        return undefined
    }

    /**
     * 从链表中移除一个元素。
     * @param {*} element 
     */
    remove(element) {
        const index = this.indexOf(element)
        return this.removeAt(index)
    }

    /**
     * 返回元素在链表中的索引。如果链表中没有该元素则返回-1
     * @param {*} element 
     */
    indexOf(element) {
        let current = this.head
        for (let i = 0; i < this.count && current != null; i++) {
            if (this.equalsFn(element, current.element)) {
                return i
            }
            current = current.next
        }
        return -1
    }

    /**
     * 从链表的特定位置移除一个元素
     * @param {*} index 
     */
    removeAt(index) {
        // 检查越界值
        if (index >= 0 && index < this.count) {
            let current = this.head

            // 移除第一项
            if (index === 0) {
                this.head = current.next
            } else {
                let previous = this.getElementAt(index - 1)
                current = previous.next
                // 将 previous 与 current 的下一项链接起来：跳过 current，从而移除它
                previous.next = current.next
            }
            this.count--
            return current.element
        }
        return undefined
    }

    /**
     * 如果链表中不包含任何元素，返回 true，如果链表长度大于 0则返回 false。
     */
    isEmpty() {
        return this.size() === 0
    }

    /**
     * 返回链表包含的元素个数
     */
    size() {
        return this.count
    }

    /**
     * 返回链表
     */
    getHead() {
        return this.head
    }

    /**
     * ：返回表示整个链表的字符串。
     */
    toString() {
        if (this.head == null) {
            return ''
        }
        let objString = `${this.head.element}`;
        let current = this.head.next
        for (let i = 1; i < this.size() && current != null; i++) {
            objString = `${objString},${current.element}`;
            current = current.next;
        }
        return objString;
    }
}

双向链表

在链表中， 一个节点只有链向下一个节点的链接;而在双向链表中，链接是双向的:一个链向下一个元素， 另一个链向前一个元素

class DoublyNode extends Node {
    constructor(element, next, prev) {
        super(element, next)
        this.prev = prev;
    }
}

class DoublyLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals) {
        super(equalsFn);
        this.tail = undefined;
    }

    insert(element, index) {
        if (index >= 0 && index <= this.count) {
            let node = new DoublyLinkedList(element);
            let current = this.head;
            if (index == 0) {
                if (this.head == null) {
                    this.head = node;
                    this.tail = node
                } else {
                    node.next = this.head;
                    current.prev = node;
                    this.head = node;
                }
            } else if (index == this.count) {
                current = this.tail;
                current.next = node;
                node.prev = current;
                this.tail = node;
            } else {
                const previous = this.getElementAt(index - 1);
                current = previous.next;
                node.next = current;
                previous.next = node;
                current.prev = node;
                node.prev = previous;
            }
            this.count++;
            return false
        }
        return false
    }

    removeAt(index) {
        if (index >= 0 && index < this.count) {
            let current = this.head;
            if (index == 0) {
                this.head = current.next;
                // 如果只有一项，更新 tail
                if (this.count == 1) {
                    this.tail = undefined
                } else {
                    this.head.prev = undefined
                }
            } else if (index == this.count - 1) { //最后一项
                current = this.tail;
                this.tail = current.prev;
                this.tail.next = undefined;
            } else {
                current = this.getElementAt(index);
                const previous = current.prev;
                // 将previous与current的下一项链接起来——跳过current
                previous.next = current.next;
                current.next.prev = previous;
            }
            this.count--;
            return current.element
        }
        return undefined
    }
}

循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针(tail.next)不是引用 undefined，而是指向第一个元素(head)

class CircularLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals) {
        super(equalsFn)
    }

    insert(element, index) {
        if (index >= 0 && index < this.count) {
            const node = new Node(element);
            let current = this.head;
            if (index == 0) {
                if (this.head == null) {
                    this.head == node;
                    node.next = this.head;
                } else {
                    node.next = current;
                    current = this.getElementAt(this.size());
                    this.head = node;
                    // 最后一个节点(current) 指向新的头部节点
                    current.next = this.head;
                }
            } else {
                const previous = this.getElementAt(index - 1);
                node.next = previous.next;
                previous.next = node;
            }
            this.count++;
            return true;
        }
        return false
    }

    removeAt(index) {
        if (index >= 0 && index < this.count) {
            let current = this.head;
            if (index == 0) {
                if (this.size() == 1) {
                    this.head == undefined
                } else {
                    const removed = this.head;
                    current = this.getElementAt(this.size());
                    this.head = this.head.next;
                    current.next = this.head;
                    // 作为返回项
                    current = removed;
                }
            } else {
                // 不需要修改循环链表最后一个元素
                const previous = this.getElementAt(index - 1);
                current = previous.next;
                previous.next = current.next;
            }

            this.count--;
            return current.element;
        }
        return undefined;
    } 
}