JavaScript -- 双链表的JavaScript描述

淡淡的烟草味﹌ 2022-04-17 00:55 143阅读 0赞

尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时向链表插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后继。但是在从链表中删除节点时，效率提高了，不需要再查找待删除节点的前驱节点了。

![20181110204818449.png][]

我们可以定义个数据结构用来表示每一个节点。

let Node = function (element) {
        this.element = element;//数据域
        this.next = null;//下一个节点
        this.previous = null;//上一个节点
    }

下面介绍增删查三种操作。

增操作：（规定我们每一次在链表尾部添加数据）

this.insert = function (data) {
            let newData = new Node(data);//新生成一个节点
            let cur = this.head;
            while ( cur.next != null) {//找到尾节点
                cur = cur.next;
            };
            cur.next = newData;//后连
            newData.previous = cur;//前连
        };

删操作：（给定我们一个数据，如果数据在链表中出现，那么删除第一次出现的时候）

![20181110205155414.png][]

this.remove = function (data) {
            let cur = this.head;
            while ( cur.next != null) {
                cur = cur.next;
                if (cur.element == data ) {//找到目标节点
                    let pre = cur.previous;//目标节点前一个节点
                    pre.next = cur.next;//向后连
                    cur.next.previous = pre;//向前连
                    cur.next = cur.previous = null;//置null
                    break;
                }
            }
        };

如果你需要删除所有的相关值，那么你只需要一个循环即可。

查操作：

this.find = function (data) {
            let cur = this.head;
            while ( cur.next != null ) {
                cur = cur.next;
                if ( cur.element == data ) {
                    return true;
                }
            }
            return false;
        };

双链表

验证代码：

let app = new DoublyList();
    app.insert(5);
    app.insert(6);
    app.insert(6);
    app.insert(9);
    app.insert(9);
    
    app.remove(6);
    app.show();
    app.reverseShow();

![20181110205735284.png][]

删除了一个6，所以少一个6。一个正输出（根据next)，一个逆输出(根据previous)，结果是符合要求的上下对称。

[20181110204818449.png]: /images/20220417/34bb8831192e4a6891c992c9f9a82d5d.png
[20181110205155414.png]: /images/20220417/904c2e8e7cd042b18cb9c2143937ab12.png
[20181110205735284.png]: /images/20220417/e100b8cd3b2047439e27d312fbc99052.png