数据结构 - 循环链表

单向循环链表

image.png

const ELEMENT_NOT_FOUND = -1;

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

class BaseList {
    constructor() {
        this.size = 0;
    }

    // 获取size
    getSize() {
        return this.size;
    }

    // list是否为空
    isEmpty() {
        return this.size === 0;
    }

    // 是否包含一个元素
    contains(ele) {
        return this.indexof(ele) !== ELEMENT_NOT_FOUND;
    }

    // 检查是否超出范围
    rangeCheck(index, isadd) {
        if (isadd) {
            if (index > this.size || index < 0) throw new RangeError('index is out of range');
        } else {
            if (index >= this.size || index < 0) throw new RangeError('index is out of range');
        }
    }
}

// 循环链表是一个环形，与普通的链表只是在add和remove上有不同，而且只是在向头部添加时不同
class CircleLinkedList extends BaseList {
    constructor() {
        super();
        this.first = null;
    }

    // 清空
    clear() {
        this.first = null;
        this.size = 0;
    }

    // 获取固定下标的值 复杂度： O(n)
    get(index) {
        return this.node(index).element;
    }

    // 设置固定下标的值 复杂度： O(n)
    set(index, ele) {
        let node = this.node(index);
        let old = node.element;
        node.element = ele;
        return old;
    }

    // 向末尾增加 复杂度： O(n)
    push(ele) {
        this.add(ele, this.size);
    }

    // 添加元素 复杂度： O(n)
    add(ele, index) {
        this.rangeCheck();

        // 要区分向头部添加和其他位置添加的情况
        if (index === 0) {
            // 先创建一个元素
            let node = new Node(ele, this.first);
            // 如果当前没有元素时，last就为创建的元素
            let last = this.size === 0 ? node : this.node(this.size - 1);
            // 讲last的next指向第一个新创建的第一个元素
            last.next = node;
            this.first = node;
        } else {
            let prevNode = this.node(index - 1);
            prevNode.next = new Node(ele, prevNode.next);
        }
        this.size++;
    }

    // 删除元素 复杂度： O(n)
    remove(index) {
        this.rangeCheck();

        if (index === 0) {
            if (this.size === 1) {
                // 如果只剩一个元素需要直接置为null
                this.first = null;
            } else {
                // 如果剩多个元素时，先删除元素
                this.first = this.first.next;
                // 再将最后一个元素的next指向first第一个元素
                let last = this.node(this.size - 1);
                last.next = this.first;
            }
        } else {
            // 将前一个next指向下一个即可
            let prevNode = this.node(index - 1);
            let currentNode = prevNode.next;
            prevNode.next = currentNode.next;
        }
        this.size--;

        return currentNode.element;
    }

    // 获取当前下标的元素 复杂度： O(n)
    node(index) {
        this.rangeCheck(index);

        let node = this.first;
        for (let i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    // 获取元素的下标 复杂度： O(n)
    indexof(ele) {
        let node = this.first,
            index = 0;

        //TODO 循环链表中不可以使用这种循环，需要使用for循环
        while (!!node) {
            if (ele === node.element) return index;

            node = node.next;
            index++
        }
        return ELEMENT_NOT_FOUND;
    }

    toString() {
        let node = this.first,
            str = '';

        //TODO 循环链表中不可以使用这种循环，需要使用for循环
        while (!!node) {
            str += `${node.element}-->`;
            node = node.next;
        }
        str += `size = ${this.size}`
        return str;
    }
}