数据结构之LinkedList | 让我们一块来学习数据结构

简介: 数据结构之LinkedList | 让我们一块来学习数据结构

上一篇文章中使用列表(List)对数据排序,当时底层储存数据的数据结构是数组。本文将讨论另外一种列表:链表。我们会解释为什么有时链表优于数组,还会实现一个基于对象的链表。下面让我们一起来学习LinkedList

数组的缺点

在很多编程语言中,数组的长度是固定的,所以当数组已被数据填满时,再要加入新的元素就会非常困难。在数组中,添加和删除元素也很麻烦,因为需要将数组中的其他元素向前或向后平移,以反映数组刚刚进行了添加或删除操作。然而,JavaScript 的数组并不存在上述问题,因为使用 split() 方法不需要再访问数组中的其他元素了。

avaScript 中数组的主要问题是,它们被实现成了对象,与其他语言(比如 C++ 和 Java)的数组相比,效率很低。

定义链表

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。下图展示了一个链表。

数组元素靠它们的位置进行引用,链表元素则是靠相互之间的关系进行引用。在上图中,我们说 李四 跟在 张三 后面,而不说 李四 是链表中的第二个元素。遍历链表,就是跟着链接,从链表的首元素一直走到尾元素(但这不包含链表的头节点,头节点常常用来作为链表的接入点)。图中另外一个值得注意的地方是,链表的尾元素指向一个 null 节点。

然而要标识出链表的起始节点却有点麻烦,许多链表的实现都在链表最前面有一个特殊节点,叫做头节点。经过改造之后,上图中的链表成了下面的样子。

设计一个基于对象的链表

Node类

Node 类包含两个属性:element 用来保存节点上的数据,next 用来保存指向下一个节点的

链接。我们使用一个class来创建节点:

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}

LinkedList类

LList 类提供了对链表进行操作的方法。该类的功能包括插入删除节点、在列表中查找给

定的值。该类也有一个构造函数,链表只有一个属性,那就是使用一个 Node 对象来保存该

链表的头节点。

该类如下所示

class LinkedList {
    constructor() {
        this.head = new Node("head");
    }
    find() { }
    insert() { }
    findPrevious() { }
    remove() { }
    display() { }
}

head 节点的 next 属性被初始化为 null,当有新元素插入时,next 会指向新的元素,所以在这里我们没有修改 next 的值。

插入新节点

该方法向链表中插入一个节点。向链表中插入新节点时,需要明确指出要在哪个节点前面或后面插入。首先介绍如何在一个已知节点后面插入元素。

在一个已知节点后面插入元素时,先要找到“后面”的节点。为此,创建一个辅助方法find(),该方法遍历链表,查找给定数据。如果找到数据,该方法就返回保存该数据的节点。find() 方法的实现代码如下所示:

find(element) {
    let current = this.head;
    while (current.element !== element) {
        current = current.next;
    }
    return current;
}

find() 方法演示了如何在链表上进行移动。首先,创建一个新节点,并将链表的头节点赋给这个新创建的节点。然后在链表上进行循环,如果当前节点的 element 属性和我们要找的信息不符,就从当前节点移动到下一个节点。如果查找成功,该方法返回包含该数据的节点;否则,返回 null

一旦找到“后面”的节点,就可以将新节点插入链表了。首先,将新节点的 next 属性设置为“后面”节点的 next 属性对应的值。然后设置“后面”节点的 next 属性指向新节点。

insert() 方法的定义如下:

insert(element) {
    const newNode = new Node(element);
    const curNode = this.find(element);
    newNode.next = cur.next;
    curNode.next = newNode;
}

移除节点

在之前我们已经可以实现插入节点了,有添加自然就有移除。现在让我们来实现remove()方法。

从链表中删除节点时,需要先找到待删除节点前面的节点。找到这个节点后,修改它的

next 属性,使其不再指向待删除节点,而是指向待删除节点的下一个节点。我们可以定义

一个方法 findPrevious(),来做这件事。该方法遍历链表中的元素,检查每一个节点的下

一个节点中是否存储着待删除数据。如果找到,返回该节点(即“前一个”节点),这样

就可以修改它的 next 属性了。findPrevious() 方法的定义如下:

findPrevious(item) {
    let curNode = this.head;
    while (curNode.next !== null && curNode.next.element !== item) {
        curNode = curNode.next;
    }
    return curNode;
}

现在就可以开始写 remove() 方法了:

remove(item) {
    const prevNode = this.findPrevious(item);
    if (prevNode.next !== null) {
        prevNode.next = prevNode.next.next;
    }
}

查看链表内的元素

现在已经可以开始测试我们的链表实现了。然而在测试之前,先来定义一个 display() 方法,该方法用来显示链表中的元素:

display() {
    let target = [];
    let curNode = this.head;
    while (curNode.next !== null) {
        target.push(curNode.next.element);
        curNode = curNode.next;
    }
    return target.join();
}

测试代码

双向链表

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

修改Node类

首当其冲的是要为 Node 类增加一个 previous 属性:

class Node {
    constructor(element) {
        this.element = element;
        this.previous = null;
        this.next = null;
    }
}

修改insert()方法

双向链表的 insert() 方法和单向链表的类似,但是需要设置新节点的 previous 属性,使其指向该节点的前驱。该方法的定义如下:

insert(element, item) {
    const newNode = new Node(element);
    const curNode = this.find(item);
    newNode.next = curNode.next;
    newNode.previous = curNode; // 令新节点的previous指向当前节点
    curNode.next = newNode;
}

双向链表的 remove() 方法比单向链表的效率更高,因为不需要再查找前驱节点了。首先需要在链表中找出存储待删除数据的节点,然后设置该节点前驱的 next 属性,使其指向待删除节点的后继;设置该节点后继的 previous 属性,使其指向待删除节点的前驱。下图直观地展示了该过程。

新的remove() 方法的定义

remove(item) {
    const curNode = this.find(item);
    if (curNode.next !== null) {
        curNode.previous.next = curNode.next;
        curNode.next.previous = curNode.previous;
        curNode.previous = null;
        curNode.next = null;
    }
}

反向显示链表中的元素

为了完成以反序显示链表中元素这类任务,需要给双向链表增加一个工具方法,用来查找最后的节点。findLast() 方法找出了链表中的最后一个节点,同时免除了从前往后遍历链表之苦:

findLast() {
    let curNode = this.head;
    while (curNode.next !== null) {
        curNode = curNode.next;
    }
    return curNode;
}

有了这个工具方法,就可以写一个方法,反序显示双向链表中的元素。dispReverse() 方法如下所示:

displayReverse() {
    let target = [];
    let currNode = this.findLast();
    while (currNode.previous !== null) {
        target.push(currNode.element);
        currNode = currNode.previous;
    }
    return target.join();
}

完整的双向链表实现及测试代码

class Node {
    constructor(element) {
        this.element = element;
        this.previous = null;
        this.next = null;
    }
}
class LinkedList {
    constructor() {
        this.head = new Node("head");
    }
    find(item) {
        let current = this.head;
        while (current.element !== item) {
            current = current.next;
        }
        return current;
    }
    insert(element, item) {
        const newNode = new Node(element);
        const curNode = this.find(item);
        newNode.next = curNode.next;
        newNode.previous = curNode;
        curNode.next = newNode;
    }
    findLast() {
        let curNode = this.head;
        while (curNode.next !== null) {
            curNode = curNode.next;
        }
        return curNode;
    }
    remove(item) {
        const curNode = this.find(item);
        if (curNode.next !== null) {
            curNode.previous.next = curNode.next;
            curNode.next.previous = curNode.previous;
            curNode.previous = null;
            curNode.next = null;
        }
    }
    display() {
        let target = [];
        let curNode = this.head;
        while (curNode.next !== null) {
            target.push(curNode.next.element);
            curNode = curNode.next;
        }
        return target.join();
    }
    displayReverse() {
        let target = [];
        let currNode = this.findLast();
        while (currNode.previous !== null) {
            target.push(currNode.element);
            currNode = currNode.previous;
        }
        return target.join();
    }
}
// test code
const linkedList = new LinkedList();
linkedList.insert("张三", "head");
console.log(linkedList.display()); // 张三
linkedList.insert("李四", "张三");
console.log(linkedList.display()); // 张三,李四
linkedList.insert("王五", "李四");
console.log(linkedList.display()); // 张三,李四,王五
linkedList.remove("李四");
console.log(linkedList.display()); // 张三,王五
console.log(linkedList.displayReverse()); // 王五,张三

循环链表

循环链表和单向链表相似,节点类型都是一样的。唯一的区别是,在创建循环链表时,让其头节点的 next 属性指向它本身,即:

head.next = head

这种行为会传导至链表中的每个节点,使得每个节点的 next 属性都指向链表的头节点。换句话说,链表的尾节点指向头节点,形成了一个循环链表,如图 6-7 所示。

创建循环链表,只需要修改 LinkedList 类的构造方法(constructor):

class LinkedList {
    constructor() {
        this.head = new Node("head");
        this.head.next = this.head;
    }
    find() { }
    insert() { }
    findPrevious() { }
    remove() { }
    display() { }
}

只需要修改一处,就将单向链表变成了循环链表。但是其他一些方法需要修改才能工作正常。比如,display() 就需要修改,原来的方式在循环链表里会陷入死循环。while 循环的循环条件需要修改,需要检查head节点,当循环到head节点时退出循环。

循环链表的display()方法如下:

display() {
    let target = [];
    let curNode = this.head;
    while (curNode.next !== null && curNode.next.element !== "head") {
        target.push(curNode.next.element);
        curNode = curNode.next;
    }
    return target.join();
}

完整的循环链表实现及测试代码

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}
class LinkedList {
    constructor() {
        this.head = new Node("head");
        this.head.next = this.head;
    }
    find(item) {
        let current = this.head;
        while (current.element !== item) {
            current = current.next;
        }
        return current;
    }
    insert(element, item) {
        const newNode = new Node(element);
        const curNode = this.find(item);
        newNode.next = curNode.next;
        curNode.next = newNode;
    }
    findPrevious(item) {
        let curNode = this.head;
        while (curNode.next !== null && curNode.next.element !== item) {
            curNode = curNode.next;
        }
        return curNode;
    }
    remove(item) {
        const prevNode = this.findPrevious(item);
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next;
        }
    }
    display() {
        let target = [];
        let curNode = this.head;
        while (curNode.next !== null && curNode.next.element !== "head") {
            target.push(curNode.next.element);
            curNode = curNode.next;
        }
        return target.join();
    }
}
// test code
const linkedList = new LinkedList();
linkedList.insert("张三", "head");
console.log(linkedList.display()); // 张三
linkedList.insert("李四", "张三");
console.log(linkedList.display()); // 张三,李四
linkedList.insert("王五", "李四");
console.log(linkedList.display()); // 张三,李四,王五
linkedList.remove("李四");
console.log(linkedList.display()); // 张三,王五

参考资料

  • 数据结构与算法JavaScript描述
  • 学习JavaScript数据结构与算法 第3版

如果觉得对您有帮助,动动小手点个赞;您的点赞就是对我最大的认可。


相关文章
|
2月前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
61 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
2月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
57 0
数据结构与算法学习十五:哈希表
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明