数据结构 - 双向链表

image.png

const ELEMENT_NOT_FOUND = -1;

class Node {
    constructor(ele, prev, next) {
        this.element = ele;
        this.prev = prev;
        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');
        }
    }
}

class doublyLinkedList extends BaseList {
    constructor() {
        super();
        this.first = null;
        this.last = null;
    }

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

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

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

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

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

        // 要区分向尾部添加和其他位置添加的情况
        if (index === this.size) {
            // 创建node，与前后相连
            let node = new Node(ele, this.last, null);
            // 如果last为null，说明此时链表中还没有元素
            if (this.last === null) {
                // 需要将first连接到node
                this.first = node;
            } else {
                // 如果有元素，需要前一个元素的next连接到node
                this.last.next = node;
            }
            // 再将last连接到node
            this.last = node;
        } else {
            let currentNode = this.node(index);
            let prevNode = currentNode.prev;
            // 创建节点时与前后相连
            let node = new Node(ele, prevNode, currentNode);
            // 先连后面的线，prev和插入的node相连
            currentNode.prev = node;
            // 如果前一个节点是null 说明是头部插入
            if (prevNode === null) {
                // 需要改变first的指向
                this.first = node;
            } else {
                // 最后连接前面的线，next与插入的节点相连
                prevNode.next = node;
            }
        }

        this.size++;
    }

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

        let node = this.node(index);
        let prevNode = node.prev;
        let nextNode = node.next;

        // if (prevNode === null) {
        //     this.first = nextNode;
        //     if (nextNode === null) {
        //         this.last = prevNode
        //     } else {
        //         nextNode.prev = prevNode;
        //     }
        // } else if (nextNode === null) {
        //     this.last = prevNode;
        //     if (prevNode === null) {
        //         this.first = nextNode;
        //     } else {
        //         prevNode.next = nextNode;
        //     }
        // } else {
        //     prevNode.next = nextNode;
        //     nextNode.prev = prevNode;
        // }

        if (prevNode == null) { // index == 0
            this.first = nextNode;
        } else {
            prevNode.next = nextNode;
        }

        if (nextNode == null) { // index == size - 1
            this.last = prevNode;
        } else {
            nextNode.prev = prevNode;
        }

        this.size--;
        return node.element;
    }

    // 获取当前下标的元素 复杂度： O(n/2)
    // 单向链表所有的复杂度都是O(n)，主要就在于node函数，只需要优化了node函数就可以降低复杂度
    node(index) {
        this.rangeCheck(index);
        let node;
        // 判断index和头尾哪个相近
        if (index < (this.size >> 1)) {
            // 从头部开始
            node = this.first;
            for (let i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            // 从尾部开始
            node = this.last;
            for (let i = this.size - 1; i > index; i--) {
                node = node.prev;
            }
        }

        return node;
    }

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

        while (!!node) {
            if (ele === node.element) return index;

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

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

        while (!!node) {
            str += `${node.prev}_${node.element}_${node.next}-->`;
            node = node.next;
        }
        str += `size = ${this.size}`
        return str;
    }
}

双向链表删除、添加的复杂度都会降到O(n/2).

1. 如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择
2. 如果频繁在头部进行添加、删除操作，建议选择使用双向链表
3. 如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表
4. 如果有频繁的查询操作（随机访问操作），建议选择使用动态数组