关于javascript:双向链表我不再是单向行驶啦啦啦

29次阅读

共计 6751 个字符，预计需要花费 17 分钟才能阅读完成。

不同于单链表，双向链表每个节点除了蕴含数据以外，还包含了别离指向其前节点和后节点的指针

其实双链表与比单链表相比，就是节点上新增了一个指向上一个节点的指针而已

上面我来手写一下双链表，实现一些办法：

<img src=”https://pic4.zhimg.com/80/v2-1aa41e01531c94ab3e843da7e831049b_720w.png” alt=”img” style=”zoom:80%;” />

咱们先实现一个节点构造函数：

class Node {constructor(element) {
        this.element = element;  // 节点数据值
        this.next = null;  // 前指针
        this.prev = null;  // 后指针
    }
}

双向链表整体构造 

class DoubleLinkedList {constructor() {
        this.count = 0; // 记录节点数
        this.head = null; // 双向链表头部
        this.tail = null; // 双向链表尾部
    }

    // 链表尾部增加节点
    add(element) {}

    // 链表指定地位增加一个节点
    addAt(index, element) {}

    // 移除链表指定地位的节点
    removeAt(index) {}

    // 移除链表指定节点
    remove(element) {}

    // 翻转链表
    reverse() {}

    // 替换两个节点的地位
    swap() {}

    // 遍历链表
    traverse() {}

    // 查找某个节点的索引
    find() {}

    // 查问链表是否为空
    isEmpty() {}

    // 查问链表的长度
    length() {}
}

接下来就是实现这一个个的办法了

依据地位（索引）查找节点，接下来的办法会始终用到这个办法，索性将其封装成一个办法，以便调用 

getElement(index) {if (index >= 0 && index < this.count) {
        let node = this.head;
        // 循环遍历到该节点
        for (let i = 0; i < index; i++) {node = node.next;}
        return node;
    }
    return undefined;
}

1、增加节点

<img src=”https://pic4.zhimg.com/80/v2-d71171007ed06c66e076048e51184694_720w.png” alt=”img” style=”zoom:80%;” />

1.1 在尾部增加节点 

// 传入一个节点
add(element) {
    // 先创立一个节点
    const node = new Node(element);
    // 如果链表为空，那就是头部节点和尾部节点都是 node 了
    if (this.head === null && this.tail === null) {
        this.head = node;
        this.tail = node
    }
    // 如果链表已有头部，则在其尾部增加节点即可
    else {
        node.prev = this.tail;
        this.tail.next = node;
        this.tail = node;
    }
    // 节点总数 +1
    this.count++;
}

1.2 链表指定地位增加一个节点 

addAt(index, element) {if (index >= 0 && index <= this.count) {const node = new Node(element);
        // 当在头部插入时
        if (index === 0) {
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        } 
        // 在尾部插入节点
        else if (index === this.count) {this.add(element)
            this.count--;
        }
        // 在两头插入节点
        else {let current = this.getElement(index);
            // 先设置新增节点与前一个节点的关系
            node.prev = current.prev;
            current.prev.next = node;
            // 再设置新增与后一个节点的关系
            node.next = current;
            current.prev = node
        }
        this.count++;
        return true
    }
    return false;
}

2、移除节点

<img src=”https://pic1.zhimg.com/80/v2-90d433c7a304d9614996bc26eafea438_720w.png” alt=”img” style=”zoom:80%;” />

2.1、移除链表指定地位的节点 

removeAt(index) {if (index >= 0 && index < this.count) {
        // 移除头节点
        if (index === 0) {
            this.head = this.head.next;
            this.head.prev = null;
        }
        // 移除尾部节点
        else if (index === this.count - 1) {
            this.tail = this.tail.prev;
            this.tail.next = null;
        }
        // 移除两头节点
        else {let current = this.getElement(index);
            current.next.prev = current.prev
            current.prev.next = current.next
        }
        this.count--;
        return true
    }
    return undefined;
}

2.2、移除链表指定节点

移除指定节点，首先就是要找到该节点 

remove(element) {
    let current = this.head;
    while (current) {if (current === element) {
            // 链表只有一个节点
            if (current === this.head && current === this.prev) {
                this.head = null;
                this.tail = null;
            }
            // 移除头节点
            else if (current === this.head) {
                this.head = this.head.next;
                this.head.prev = null;
            }
            // 移除尾部节点
            else if (current === this.tail) {
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
            // 移除两头节点
            else {
                current.next.prev = current.prev;
                current.prev.next = current.next;
            }
            this.count--;
        }
        current = current.next;
    }
}

5、翻转链表 

reverse() {
    let current = this.head;
    let prev = null;
    // 先将两头的
    while (current) {
        let next = current.next;

        // 前后倒置
        current.next = prev;
        current.prev = next;

        prev = current;
        current = next
    }
    this.tail = this.head;
    this.head = prev
}

6、替换两个节点的地位 

swap(index1, index2) {if (index1 >= 0 && index1 < this.count && index2 >= 0 && index2 < this.count) {let node1 = this.getElement(index1)
        let node2 = this.getElement(index2)
        // 让 index1 始终小于 index2，不便前面的查找替换
        if (index1 > index2) {return this.swap(index2, index1)
        }
        // 替换两个节点的数值
        [node1.element, node2.element] = [node2.element, node1.element]
        return true
    }
    return undefined;
}

7、遍历链表 

display() {if (!this.isEmpty()) {
        let current = this.head;
        let result = '';
        while (current) {
            result += current.element
            current = current.next
            if (current) {result += '->';}
        }
        return result;
    }
    return undefined;
}

8、查找某个节点的索引 

find(element) {
    let current = this.head;
    let index = 0
    while (current) {if (current === element) {return index;}
        current = current.next;
        index++;
    }
    return undefined
}

9、查问链表是否为空 

isEmpty() {return this.count === 0}

10、查问链表的长度 

length() {return this.count;}

整合一下：

// 实现一个节点构造函数
class Node {constructor(element) {
        this.element = element;
        this.next = null;
        this.prev = null;
    }
}

// 双向链表
class DoubleLinkedList {constructor() {
        this.count = 0; // 记录节点数
        this.head = null; // 双向链表头部
        this.tail = null; // 双向链表尾部
    }

    // 遍历一个办法，循环到指标地位
    getElement(index) {if (index >= 0 && index < this.count) {
            let node = this.head;
            for (let i = 0; i < index; i++) {node = node.next;}
            return node;
        }
        return undefined;
    }

    // 链表尾部增加节点
    add(element) {
        // 先创立一个节点
        const node = new Node(element);
        // 如果链表为空
        if (this.head === null && this.tail === null) {
            this.head = node;
            this.tail = node
        }
        // 如果链表已有头部，则在其尾部增加节点即可
        else {
            node.prev = this.tail;
            this.tail.next = node;
            this.tail = node;
        }
        this.count++;
    }

    // 链表指定地位增加一个节点
    addAt(index, element) {if (index >= 0 && index <= this.count) {const node = new Node(element);
            // 当在头部插入时
            if (index === 0) {
                this.head.prev = node;
                node.next = this.head;
                this.head = node;
            } else if (index === this.count) {this.add(element)
                this.count--;
            }
            // 非头部插入时
            else {let current = this.getElement(index);
                // 先设置新增节点与前一个节点的关系
                node.prev = current.prev;
                current.prev.next = node;
                // 再设置新增与后一个节点的关系
                node.next = current;
                current.prev = node
            }
            this.count++;
            return true
        }
        return false;
    }

    // 移除链表指定地位的节点
    removeAt(index) {if (index >= 0 && index < this.count) {
            // 移除头节点
            if (index === 0) {
                this.head = this.head.next;
                this.head.prev = null;
            }
            // 移除尾部节点
            else if (index === this.count - 1) {
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
            // 移除两头节点
            else {let current = this.getElement(index);
                current.next.prev = current.prev
                current.prev.next = current.next
            }
            this.count--;
            return true
        }
        return undefined;
    }

    // 移除链表指定节点
    remove(element) {
        let current = this.head;
        while (current) {if (current === element) {
                // 链表只有一个节点
                if (current === this.head && current === this.prev) {
                    this.head = null;
                    this.tail = null;
                }
                // 移除头节点
                else if (current === this.head) {
                    this.head = this.head.next;
                    this.head.prev = null;
                }
                // 移除尾部节点
                else if (current === this.tail) {
                    this.tail = this.tail.prev;
                    this.tail.next = null;
                }
                // 移除两头节点
                else {
                    current.next.prev = current.prev;
                    current.prev.next = current.next;
                }
                this.count--;
            }
            current = current.next;
        }
    }

    // 翻转链表
    reverse() {
        let current = this.head;
        let prev = null;

        while (current) {
            let next = current.next;

            // 前后倒置
            current.next = prev;
            current.prev = next;

            prev = current;
            current = next
        }
        this.tail = this.head;
        this.head = prev
    }

    // 替换两个节点的地位
    swap(index1, index2) {if (index1 >= 0 && index1 < this.count && index2 >= 0 && index2 < this.count) {let node1 = this.getElement(index1)
            let node2 = this.getElement(index2)
                // 让 index1 始终小于 index2，不便前面的查找替换
            if (index1 > index2) {return this.swap(index2, index1)
            }
            // 替换两个节点的数值
            [node1.element, node2.element] = [node2.element, node1.element]
            return true
        }
        return undefined;
    }

    // 遍历链表
    display() {if (!this.isEmpty()) {
            let current = this.head;
            let result = '';
            while (current) {
                result += current.element
                current = current.next
                if (current) {result += '->';}
            }
            return result;
        }
        return undefined;
    }

    // 查找某个节点的索引
    find(element) {
        let current = this.head;
        let index = 0
        while (current) {if (current === element) {return index;}
            current = current.next;
            index++;
        }
        return undefined
    }

    // 查问链表是否为空
    isEmpty() {return this.count === 0}

    // 查问链表的长度
    length() {return this.count;}
}

咱们来调用一下：

// 先实例化一个双向链表对象
let DLL = new DoubleLinkedList();

// 尾部增加
DLL.add(1);
DLL.add(2);
// 任意地位增加
DLL.addAt(0, 3);
DLL.addAt(3, 6);
// 遍历
console.log(DLL.display()); // 3->1->2->6
// 依据地位删除
DLL.removeAt(3);

// 替换两个节点
DLL.swap(0, 2)
console.log(DLL.display()); // 2->1->3
// 翻转
DLL.reverse();
// 链表是否为空
console.log(DLL.isEmpty()); // false
// 链表长度
console.log(DLL.length()); // 3

总结：

  • 所以你会发现实现一个链表无非也就是增（增加节点）删（删除节点）改（替换）查（遍历）
  • 增加和删除节点无非就是批改节点的指针指向而已

正文完
javascript
发表至： javascript
2021-05-03
 0
2020年如何写一个现代的JavaScript库
关于javascript:dfdfdf
关于javascript:vue3viteelementplus打包后element的icon路径报错
前端黑科技：美团网页首帧优化实践