第2章 链表

单向链表

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

class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }

    //1.向列表尾部添加一个新的项
    append(element) {
        //创建节点
        const node = new Node(element);

        //判断是否是第一个节点
        if (this.head === null) {
            this.head = node;
        } else {
            let current = this.head;
            while (current.next !== null) {
                current = current.next;
            }
            current.next = node;
        }
        this.length++;
    }

    //2.向链表某个位置插入一个元素
    insert(element, position) {
        //判断插入位置是否合法
        if (position < 0 || position > this.length) {
            return false;
        }

        //创建节点
        const node = new Node(element);

        if (position === 0) {
            node.next = this.head;
            this.head = node;
        } else {
            let index = 0;
            let previous = null;
            let current = this.head;
            //查找插入位置
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }

            previous.next = node;
            node.next = current;
            this.length++;
        }
        return true;
    }

    //3.获取对应位置的元素
    get(position) {
        if (position < 0 || position > this.length - 1) {
            return false;
        }

        let index = 0;
        let current = this.head;
        while (index < position) {
            current = current.next;
            index++;
        }

        return current.element;
    }

    //4.查找元素在链表中的索引
    indexOf(element) {
        let index = 0;
        let current = this.head;
        while (current) {
            if (current.element === element) {
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }

    //5.删除链表中对应位置的元素
    removeAt(position) {
        if (position < 0 || position > this.length - 1) {
            return null;
        }
        let index = 0;
        let previous = null;
        let current = this.head;
        if (position === 0) {
            this.head = current.next;
        } else {
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            previous.next = current.next;
        }
        this.length--;
        return current.element;
    }

    //6.删除指定元素
    remove(element) {
        const index = this.indexOf(element);
        if (index === -1) {
            return false;
        }
        this.removeAt(index);
        return true;
    }

    //7.修改某个位置的元素
    updata(element, position) {
        if (position < 0 || position > this.length - 1) {
            return false;
        }

        let index = 0;
        let current = this.head;
        while (index < position) {
            current = current.next;
            index++;
        }
        let oldElement = current.element;
        current.element = element;

        return oldElement;
    }

    //8.判空
    isEmpty() {
        return this.length === 0;
    }

    //9.长度
    size() {
        return this.length;
    }
}

双向链表

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

class DoublyLinkedList extends LinkedList {
    constructor() {
        super();
        this.tail = null;
    }

    //1.向列表尾部添加一个新的项
    append(element) {
        //创建节点
        const node = new DoublyNode(element);

        //判断是否是第一个节点
        if (this.head === null) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        this.length++;
    }

    //2.向链表某个位置插入一个元素
    insert(element, position) {
        //判断插入位置是否合法
        if (position < 0 || position > this.length) {
            return false;
        }

        //创建节点
        const node = new DoublyNode(element);

        if (position === 0) {
            //插入到第一个
            if (this.head === null) {
                this.head = node;
                this.tail = node;
            } else {
                this.head.prev = node;
                node.next = this.head;
                this.head = node;
            }
        } else if(position === this.length) {
            //插入到最后一个
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        } else {
            let index = 0;
            let current = this.head;
            let previous = null;
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            previous.next = node;
            node.next = current;
            node.prev = previous;
            current.prev = node;
        }

        this.length++;

        return true;
    }

    //3.获取对应位置的元素
    // get(position) {} 继承父类 无需重写

    //4.查找元素在链表中的索引
    // indexOf(element) {} 继承父类 无需重写

    //5.删除链表中对应位置的元素
    removeAt(position) {
        if (position < 0 || position > this.length - 1) {
            return null;
        }
        let current = this.head;

        if (position === 0) {
            if (this.length === 1) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = this.head.next;
                this.head.prev = null;
            }
        } else if (position === this.length - 1) {
            current = this.tail;
            this.tail.prev.next = null;
            this.tail = this.tail.prev;
        } else {
            let index = 0;
            let previous = null;
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }

            previous.next = current.next;
            current.next.prev = previous;
        }
        this.length--;
        return current.element;
    }

    //6.删除指定元素
    // remove(element) {} 继承父类 无需重写

    //7.修改某个位置的元素
    // updata(element, position) {} 继承父类 无需重写

    //8.判空
    // isEmpty() {} 继承父类 无需重写

    //9.长度
    // size() {} 继承父类 无需重写
}