数据结构篇——双向链表

双向链表给链上的每个节点增加了一个指向前驱节点的链接，使得从后向前遍历链表时变得简单；同时删除节点时，也不用像单向链表那样寻找待删除节点的前驱节点。

// 基于链表都是由节点组成的，我们需要定义一个节点类
function Node(element){
    this.element = element; // 保存节点上的数据
    this.next = null; // 保存指向下一个节点的链接
    this.prev = null; // 保存指向上一个节点的链接
}

// 实现链表类
function LList(){
    this.head = new Node('head');
    this.find = find;
    this.findLast = findLast;
    this.insert = insert;
    this.display = display;
    this.remove = remove;
    this.reverse = reverse;
}

// 插入新节点，需要知道在哪个节点前面或后面插入
// 因此首先要找到一个已知节点
function find(item){
    let currNode = this.head;
    while (currNode.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

// 找到最后一个节点
function findLast(){
    let currNode = this.head;
    while (currNode.next != null) {
        currNode = currNode.next;
    }
    return currNode;
}

// 找到插入的相对点后，设置新节点的前后指向
function insert(newElement, item){
    let newNode = new Node(newElement);
    let current = this.find(item);
    newNode.next = current.next;
    newNode.prev = current;
    current.next = newNode;
}

// 展示链表所有节点(不显示头节点)
function display(){
    let currNode = this.head;
    while (currNode.next != null){
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

// 直接找到待删除节点，更改前后指向
function remove(item){
    let currNode = this.find(item);
    if(currNode.next != null){
        currNode.prev.next = currNode.next;
        currNode.next.prev = currNode.prev;
        currNode.prev = null;
        currNode.next = null;
    }
}

function reverse(){
    let currNode = this.findLast();
    while(currNode.prev != null){
        console.log(currNode.element);
        currNode = currNode.prev;
    }
}

// 测试代码
let llist = new LList()
llist.insert("a", "head")
llist.insert("b", "a")
llist.insert("c", "b")
llist.insert("d", "c")
console.log(llist.findLast())
llist.display()
console.log('------')
llist.reverse()
console.log('------')
llist.remove("c")
llist.display()