526互联

如何在JavaScript中实现链表

发布时间 2023-09-19 12:49:26作者: 漫漫长路

 

 

转载来自：https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/

 

 

If you are learning data structures, a linked list is one data structure you should know. If you do not really understand it or how it is implemented in JavaScript, this article is here to help you.
如果你正在学习数据结构，链表是你应该知道的一种数据结构。如果你不真正理解它或它是如何在 JavaScript 中实现的，这篇文章在这里帮助你。

In this article, we will discuss what a linked list is, how it is different from an array, and how to implement it in JavaScript. Let's get started.
在本文中，我们将讨论什么是链表，它与数组有何不同，以及如何在 JavaScript 中实现它。让我们开始吧。

What is a Linked List?
什么是链表？


A linked list is a linear data structure similar to an array. However, unlike arrays, elements are not stored in a particular memory location or index. Rather each element is a separate object that contains a pointer or a link to the next object in that list.
链表是一种类似于数组的线性数据结构。但是，与数组不同，元素不存储在特定的内存位置或索引中。相反，每个元素都是一个单独的对象，其中包含指向该列表中下一个对象的指针或链接。

Each element (commonly called nodes) contains two items: the data stored and a link to the next node. The data can be any valid data type. You can see this illustrated in the diagram below.
每个元素（通常称为节点）包含两个项目：存储的数据和指向下一个节点的链接。数据可以是任何有效的数据类型。您可以在下图中看到这一点。

Image of a linked list

The entry point to a linked list is called the head. The head is a reference to the first node in the linked list. The last node on the list points to null. If a list is empty, the head is a null reference.
链表的入口点称为 head。head 是对链表中第一个节点的引用。列表中的最后一个节点指向 null。如果列表为空，则标头为空引用。

In JavaScript, a linked list looks like this:
在 JavaScript 中，链表如下所示：

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

An advantage of Linked Lists
链表的优势

  • Nodes can easily be removed or added from a linked list without reorganizing the entire data structure. This is one advantage it has over arrays.
    可以轻松地从链表中删除或添加节点，而无需重新组织整个数据结构。这是它相对于阵列的一个优势。

Disadvantages of Linked Lists
链表的缺点

  • Search operations are slow in linked lists. Unlike arrays, random access of data elements is not allowed. Nodes are accessed sequentially starting from the first node.
    链表中的搜索操作很慢。与数组不同，不允许随机访问数据元素。从第一个节点开始按顺序访问节点。
  • It uses more memory than arrays because of the storage of the pointers.
    由于指针的存储，它比数组使用更多的内存。

Types of Linked Lists 链表的类型

There are three types of linked lists:
链表有三种类型：

  • Singly Linked Lists: Each node contains only one pointer to the next node. This is what we have been talking about so far.
    单链表：每个节点仅包含一个指向下一个节点的指针。这就是我们到目前为止一直在谈论的。
  • Doubly Linked Lists: Each node contains two pointers, a pointer to the next node and a pointer to the previous node.
    双向链表：每个节点包含两个指针，一个指向下一个节点的指针和一个指向前一个节点的指针。
  • Circular Linked Lists: Circular linked lists are a variation of a linked list in which the last node points to the first node or any other node before it, thereby forming a loop.
    循环链表：循环链表是链表的变体，其中最后一个节点指向第一个节点或它之前的任何其他节点，从而形成一个循环。

Implementing a List Node in JavaScript
在 JavaScript 中实现列表节点

As stated earlier, a list node contains two items: the data and the pointer to the next node. We can implement a list node in JavaScript as follows:
如前所述，列表节点包含两个项：数据和指向下一个节点的指针。我们可以在 JavaScript 中实现一个列表节点，如下所示：

class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

Implementing a Linked List in JavaScript
在 JavaScript 中实现链表（JavaScript）

The code below shows the implementation of a linked list class with a constructor. Notice that if the head node is not passed, the head is initialised to null.
下面的代码显示了带有构造函数的链表类的实现。请注意，如果未传递头节点，则头节点将初始化为 null。

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

Putting it all together 将一切整合在一起

Let's create a linked list with the class we just created. First, we create two list nodes, node1 and node2 and a pointer from node 1 to node 2.
让我们用我们刚刚创建的类创建一个链表。首先，我们创建两个列表节点， node1 以及 node2 一个从节点 1 到节点 2 的指针。

let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2

Next, we'll create a Linked list with the node1.
接下来，我们将创建一个带有 . node1

let list = new LinkedList(node1)

Let's try to access the nodes in the list we just created.
让我们尝试访问刚刚创建的列表中的节点。

console.log(list.head.next.data) //returns 5

Some LinkedList methods 一些链接列表方法

Next up, we will implement four helper methods for the linked list. They are:
接下来，我们将为链表实现四个帮助程序方法。它们是：

  1. size() 大小（）
  2. clear() 清除（）
  3. getLast() getLast（）
  4. getFirst() 获取优先（）

1. size() 1. 大小（）

This method returns the number of nodes present in the linked list.
此方法返回链表中存在的节点数。

size() {
    let count = 0; 
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
}

2. clear() 2. 清除（）

This method empties out the list.
此方法清空列表。

clear() {
    this.head = null;
}

3. getLast() 3. 获取最后（）

This method returns the last node of the linked list.
此方法返回链表的最后一个节点。

getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}

4. getFirst() 4. 获取第一（）

This method returns the first node of the linked list.
此方法返回链表的第一个节点。

getFirst() {
    return this.head;
}

Summary 总结

In this article, we discussed what a linked list is and how it can be implemented in JavaScript. We also discussed the different types of linked lists as well as their overall advantages and disadvantages.
在本文中，我们讨论了什么是链表以及如何在 JavaScript 中实现它。我们还讨论了不同类型的链表及其整体优缺点。

I hope you enjoyed reading it.
我希望你喜欢阅读它。

Want to get notified when I publish a new article? Click here.
想要在发布新文章时收到通知？点击这里。