高级前端之js数据结构之线性结构（下）

阳光穿透心脏的1/2处 2022-11-11 14:46 133阅读 0赞

## **双向链表** ##

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

\*\*

## 初始化节点 ##

*  指向前一个节点的指针
 *  指向后一个节点的指针
 *  节点数据

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所指的地址）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5Nzk0NA_size_16_color_FFFFFF_t_70]

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

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

[20210321005625546.png]: /images/20221022/5491b3ac465f4dfea49de4f0110fdeaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5Nzk0NA_size_16_color_FFFFFF_t_70]: /images/20221022/d55be874de8a405d8f5d38058329129b.png