SOURCE

// 链表并非保存在一段连续的存储空间内
// 链表的每一个元素都由一个储存元素和指向下一个元素的指针组成
// 链表的常见操作
// 1, 向链表中添加节点 append
// 2, 在链表的指定位置插入节点 insert
// 3, 删除链表中指定位置的元素,并返回这个元素的值 removeAt
// 4, 在链表中查找给定元素的索引 indexOf
// 5, 删除链表中对应的元素 remove
// 6, 返回链表中的索引所对应的元素 getElementAt
// 7, 判断链表是否为空 isEmpty
// 8, 返回链表的长度 size
// 9,返回链表的头元素 getHead
// 10, 清空链表 clear
// 11, 辅助方法,按指定格式输出链表中的所有元素,方便测试验证结果 toString

// 辅助类Node,用来描述链表中的节点,包括值和下一个节点的指针
function Node(element){
    this.element = element
    this.next = null
}
// 模拟链表 LinkedList 成员属性 长度和头指针
class LinkedList{
    constructor(){
        this.length = 0;
        this.head = null
    }
    // 1, 向链表中添加节点 append
    append(element){
        let node = new Node(element)
        // 如果头部为空,则将节点直接赋给head
        if(this.head === null){
            this.head = node
        }else{
            // 如果头部不为空,则插最后
            let current = this.getElementAt(this.length-1)
            current.next = node
        }
        this.length++
    }
    // 2, 在链表的指定位置插入节点 insert
    insert(position,element){
        if(position < 0 || position > this.length) return false
        let node = new Node(element)
        if(position === 0){
            node.next = this.head
            this.head = node
        }else{
            let previous = this.getElementAt(position - 1)
            node.next = previous.next
            previous.next = node
        }
        this.length++
        return true
    }
    // 3, 删除链表中指定位置的元素,并返回这个元素的值 removeAt
    removeAt(position){
        if(position < 0 || position >= this.length) return null
        // 保存当前节点 默认为第一个节点
        let current = this.head

        if(position === 0){
            this.head = current.next
        }else{
            let previous = this.getElementAt(position - 1)
            current = previous.next
            previous.next = current.next
        }

        this.length --
        return current
    }
    // 4, 在链表中查找给定元素的索引 indexOf
    indexOf(element){
        let current = this.head
        for(let i = 0; i < this.length; i++){
            if(current.element === element) return i
            current = current.next
        }
        return -1
    }
    // 5, 删除链表中对应的元素 remove
    remove(element){
        return this.removeAt(this.indexOf(element))
    }
    // 6, 返回链表中的索引所对应的元素 getElementAt
    getElementAt(position){
        if(position < 0 || position >= this.length) return null;
        let current = this.head
        for(let i = 0 ; i < position ; i++){
            current = current.next
        }
        return current
    }
    // 7, 判断链表是否为空 isEmpty
    isEmpty(){
        return this.length === 0 ? true: false
    }
    // 8, 返回链表的长度 size
    size(){
        return this.length
    }
    // 9,返回链表的头元素 getHead
    getHead(){
        return this.head
    }
    // 10, 清空链表 clear
    clear(){
        this.head = null
        this.length = 0
    }
    // 11, 辅助方法,按指定格式输出链表中的所有元素,方便测试验证结果 toString
    toString(){
        let current = this.head
        let arr = []
        for(let i = 0; i < this.length; i++){
            if(current.next !== null){
                arr.push([current.element,current.next.element])
                current = current.next
            }else{
                arr.push([current.element,'null'])
            }
            
        }
        return JSON.stringify(arr)
    }
}
let linkedList = new LinkedList();
linkedList.append(10);
linkedList.append(15);
linkedList.append(20);

console.log(linkedList.toString());

linkedList.insert(0, 9);
linkedList.insert(2, 11);
linkedList.insert(5, 25);
console.log(linkedList.toString());

console.log(linkedList.removeAt(0));
console.log(linkedList.removeAt(1));
console.log(linkedList.removeAt(3));
console.log(linkedList.toString());

console.log(linkedList.indexOf(20));

linkedList.remove(20);

console.log(linkedList.toString());

linkedList.clear();
console.log(linkedList.size());