双向链表

date

Mar 18, 2023

slug

js-stack-doublyLinked

status

Published

双向链表

双向链表一个链向下一个元素，另一个链向前一个元素。双向链表提供了两种迭代的方法：从头到尾，或者从尾到头。我们也可以访问一个特定节点的下一个或前一个元素。

使用DoublyLinkedList 类继承LinkedList 类中所有的属性和方法。，在 DoublyLinkedList 的构造函数中，我们要调用 LinkedList 的构造函数，它会初始化 equalsFn、count 和 head 属性。另外，我们也会保存对链表最后一个元素的引用（ tail ）

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; 
 } 
}

继承自单链表中的类

class Node{
    constructor(element){
        this.element = element;
        this.next = undefined;
    }
}
function defaultEquals(a,b){
    return a === b;
}
class LinkedList{
    constructor(equalsFn = defaultEquals){
        this.count = 0;
        this.head = undefined;
        this.equalsFn = equalsFn;
    }
}

在任意位置添加新元素

insert(element,index){
    if(index >= 0 && index <= this.count){
        const node = new DoublyNode(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 true;
    }
    return false;
}

在双向链表起点插入（不为空）

在双向链表末尾

在双向链表中间