高级前端之js数据结构之线性结构(下)

  • 时间:
  • 浏览:
  • 来源:互联网

双向链表

如果你把上面介绍的单向列表都看明白了,那么这里介绍的双向列表其实差不多,无外乎多了一个指针而已
在这里插入图片描述
从上面的图可以很清楚的看到双向链表和单向链表的区别。双向链表多了一个指向上一个节点的指针。

**

初始化节点

  • 指向前一个节点的指针
  • 指向后一个节点的指针
  • 节点数据
class ListNode {
    this.prev = null;
    this.next = null;
    this.key = key;
}

初始化双向链表

  • 头指针指向NULL
class List {
    constructor(){
        this.head = null;
    }
}

创建节点

static createNode(key){
    return new ListNode(key);
}

插入节点((插入到头节点之后)

  • 看上图中head后面的第一个节点可以知道,该节点的prev指向NULL 节点的next指针指向后一个节点,
    也就是当前头指针所指向的那个节点 如果head后有节点,那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)
  • 最后将head指向新的节点
insert(node) {
    node.prev = null;
    node.next = this.head;
    if(this.head){
        this.head.prev = node;
    }
    this.head = node;
}

搜索节点

  • 这里和单向节点一样,我直接上代码吧
  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

删除节点

  • 和之前单向链表一样,分三种情况去看

  • 删除的是第一个节点

  • head指向所要删除节点的下一个节点

  • 下一个节点的prev指针指向所要删除节点的上一个节点

  • 删除的是中间的某个节点

  • 所要删除的前一个节点的next指向所要删除的下一个节点

  • 所要删除的下一个节点的prev指向所要删除的前一个节点

  • 删除的是最后一个节点

要删除的节点的上一个节点的next指向null(也就是指向删除节点的next所指的地址)
在这里插入图片描述

delete(node) {
    const {prev,next} = node;
    delete node.prev;
    delete node.next;
    if(node === this.head){
        this.head = next;
    }
    if(next){
        next.prev = prev;
    }
    if(prev){
        prev.next = next;
    }
}

整合一下代码 具体如下:

  class Node {
        constructor(key) {
            this.key = key;
            this.pre = null;
            this.next = null;
        }
    }
    class List {
        constructor() {
            this.head = null;
        }
        static createNode(key) {
            return new Node(key)
        }
        // 在首插入
        insert(node) {
            node.pre = null;
            node.next = this.head;
            if (this.head) {
                this.head.pre = node.next;
            }
            this.head = node;
        }
        search(key) {
            let node = this.head;
            while (node != null && node.key != key) {
                node = node.next;
            }
            return node
        }
        delete(node) {
            const { pre, next } = node;
            delete node.pre;
            delete node.next;
            if (node == this.head) {
                this.head = next;
            }
            if (next) {
                next.pre = pre;
            }
            if (pre) {
                pre.next = next;
            }
        }
    }
    let list =new List();
    list.insert(List.createNode(2));
    list.insert(List.createNode(5));
    list.insert(List.createNode(8));
    console.log(list);
    console.log(list.search(8));

以上就是双向链表的大致一个总结,欢迎小伙伴指出问题所在!

本文链接http://www.dzjqx.cn/news/show-617174.html