In-depth understanding of the data structure in JS (Linked-list)

Related recommendations: "javascript video tutorial"

For JS beginners, understanding linked lists may be a difficult task, because JS No built-in linked list is provided. In a high-level language like JS, we need to implement this data structure from scratch, and if you are not familiar with how this data structure works, the implementation part becomes more difficult?.

In this article, we will discuss how to store linked lists in the database, implement operations such as adding and deleting linked lists, searching and reversing linked lists. Before implementing a linked list, you need to know what the advantages of a linked list are compared to arrays and objects.

We know that the elements in the array are stored in the database in index number and order:

When using the array, in Operations like adding/removing an element from the beginning or at a specific index can be a less performant task because we have to move the index of all other elements. The reason for this is caused by the numbered indexing nature of arrays.

Using objects can solve the above problems. Since in an object, the element storage location is random , there is no need to move the element's index when performing operations such as adding/removing an element at the beginning or at a specific index:

Although adding and removing elements in objects is fast, as you can see from the above figure, objects are not the best choice when iterating operations. Because the elements of the object are stored in random locations. Therefore, iterative operations may take a long time. This is the reason why Linked List is introduced.

So what is a linked list?

You can tell from the name itself that it is a linked list in some way. So how is it linked and what does the list contain?

The linked list consists of nodes with two attributes: data and pointer.

The pointer within the node points to the next node in the list. The first node in the linked list is called head. For better understanding, let us take a look at the diagram describing the linked list:

As can be seen from the above figure, each node has two Attributes, data and pointer. The pointer points to the next node in the list, and the pointer of the last node points to null. The picture above is a singly linked list?.

There is a big difference between linked lists and objects. In a linked list, each node is connected to the next node through a pointer(pointer). So, we have a connection between each node of the linked list, whereas in an object, the key-value pairs are stored randomly without a connection to each other.

Next, we implement a linked list to store integers. Since JS does not provide built-in linked list support, we will use objects and classes to implement linked lists?

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

class LinkedList {
  constructor () {
    this.head = null
    this.tail = this.head
    this.length = 0
  }
  append (value) {
  }

  prepend (value) {

  }

  insert (value, index) {

  }

  lookup (index) {

  }

  remove (index) {

  }

  reverse () {
    
  }
}

In the above code, we have created two classes, one for linked lists itself, one is the node itself. As we discussed, each node will have two properties, a value and a pointer (corresponding to the next field). The

LinkedList class contains three attributes, head (initial value is null), which is used to store the ## of the last node of the linked list. #tail (also points to null) and the length attribute used to save the length of the linked list. Next, let’s implement the method inside?.

append (Add values ​​in order)

This function adds a node to the end of the linked list. In order to implement this function, we need to understand some of the operations it needs to perform:

From the above figure, we can implement it in the following ways

append Function:

  append (value) {
    const newNode = new Node(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length++
  }

Briefly explain the

append method?:

const linkedList1 = new LinkedList()
linkedList1.append(2)

Check whether

head points to null, at this time head points to null, so we create a new object and assign the new object to head and tail :

let node = new Node(2)
this.head = newNode
this.tail = newNode

Now,

head and tail both point to the same object, this is important to remember.

Next, we add two more values ​​to the linked list:

linkedList1.append(3)
linkedList1.append(4)

Now,

head does not point to null, so we enter append The else branch of the function:

this.tail.next = node

由于head 和tail 都指向同一个对象，tail的变化都会导致head对象的变化，这是JS 中对象的工作方式。在JavaScript中，对象是通过引用传递的，因此 head 和tail都指向存储对象的相同地址空间。上面这行代码相当于

this.head.next = node;

下一行：

this.tail = node

现在，在执行完上面的代码行之后，this.head.next和this.tail指向同一对象，因此，每当我们添加新节点时，head对象都会自动更新。

执行三次append之后，linkedList1 的结构应该是这样的：

head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}}
tail : {value: 4, next: null}
length:3

从上面的代码中我们可以看到，链表的append函数的复杂度是O(1)，因为我们既不需要移动索引，也不需要遍历链表。

我们来看下一个函数 ?

prepend (将值添加到链表的开头)

为了实现此函数，我们使用Node类创建一个新节点，并将该新节点的下一个对象指向链表的head 。 接下来，我们将新节点分配给链表的head：

与append函数一样，这个函数的复杂度也是O(1)。

  prepend (value) {
  const node = new Node(value)

  node.next = this.head
  this.head = node
  this.length++
}

就像append函数一样，此函数的复杂度也为O(1)。

insert (在特定索引处添加值)

在实现此函数之前，我们先看看它的一个转化过程。因此，出于理解目的，我们先创建一个值很少的链表，然后可视化insert函数。 insert  函数接受两个参数，值和索引:

let linkedList2 = new LinkedList()
linkedList2.append(23)
linkedList2.append(89)
linkedList2.append(12)
linkedList2.append(3)

linkedList2.insert(45,2)

第1步：

遍历链表，直到到达index-1位置:

第2步：

将索引为1的节点的指针（在本例中为89）分配给新节点（在本例中为45）：

第3步：

将新节点(45)的 next 指向给下一个节点(12)

这就是执行插入操作的方式。 通过以上可视化，我们观察到需要在index-1位置和index位置找到节点，以便可以在它们之间插入新节点。 在代码中实现：

insert (value, index) {
  if (index >= this.length) {
  this.append(value)
}

  const node = new Node(value)

  const { prevNode, nextNode } = thisg.getPrevNextNodes(index)
  prevNode.next = node
  node.next = nextNode

  this.length++
}

简单分析一下上面的函数：

如果index的值大于或等于length属性，则将操作移交给append函数。 对于 else 分支，我们使用 Node 类创建一个新节点，接下来观察一个新函数getPrevNextNodes() ，通过该函数我们可以接收prevNode和nextNode的值。 getPrevNextNodes函数的实现如下：

 getPrevNextNodes(index){
    let count = 0;
    let prevNode = this.head;
    let nextNode = prevNode.next;

    while(count < index - 1){
      prevNode = prevNode.next;
      nextNode = prevNode.next;
      count++;
    }

    return {
      prevNode,
      nextNode
    }
  }

通过遍历链表返回在index-1位置和index位置的节点，并将prevNode的next属性指向新节点，并将新节点的next属性指向nextNode。

链表的插入操作的复杂度为 O(n)，因为我们必须遍历链表并在index-1和 index 位置搜索节点。 尽管复杂度为O(n)，但我们发现此插入操作比对数组的插入操作快得多，在数组中，我们必须将所有元素的索引移到特定索引之后，但是在链接中，我们仅操纵 index-1 和index 位置的节点的下一个属性。

remove (删除特定索引处的元素)

实现了插入操作之后，删除操作就比较容易理解，因为它几乎与插入操作相同，当我们从getPrevNextNodes函数获取prevNode和nextNode值时，我们必须在remove中执行以下操作：

remove(index){
  let {previousNode,currentNode} = this.getNodes(index)
  previousNode.next = currentNode.next
  this.length--
}

删除操作的复杂度也为 O(n)，类似于插入操作，链表中的删除操作比数组中的删除操作要快。

reverse (反转链表)

虽然看起来很简单，但反转链表常常是实现起来最令人困惑的操作，因此，在面试中会经常询问这个操作。在实现这个函数之前，让我们先把反转链表的策略可视化一下。

为了反转链表，我们需要跟踪三个节点，previousNode，currentNode和nextNode。

考虑下面的链表:

let linkedList2 = new LinkedList()
linkedList2.append(67)
linkedList2.append(32)
linkedList2.append(44)

第一步：

开始，previousNode的值为null，而currentNode的值为head：

第二步：

接下来，我们将nextNode分配给currentNode.next：

第三步：

接下来，我们将currentNode.next属性指向previousNode：

第三步：

现在，我们将previousNode移至currentNode，将currentNode移至nextNode：

这个过程从步骤2重复操作，一直到currentNode 等于 null。

reverse (){
  let previousNode = null
  let currentNode = this.head

  while(currentNode !== null) {
    let nextNode = currentNode.next
    currentNode.next = previousNode
    previousNode = currentNode
    currentNode = nextNode
  }

  this.head = previousNode
}

就像我们看到的一样，直到currentNode === null，我们一直在遍历和移动这些值。 最后，我们将previousNode值分配给head。

反向运算的复杂度为O(n)。

查找 (查找特定索引的值)

这个操作很简单，我们只是遍历链表并返回特定索引处的节点。这个操作的复杂度也是O(n)。

lookup(index){
    let counter = 0;
    let currentNode = this.head;
    while(counter < index){
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }

好了，我们已经完成了用javascript实现单个链表的基本操作。单链表和双链表的区别在于，双链表的节点具有指向前一个节点和下一个节点的指针。

总结

链表为我们提供了快速的append（末尾添加元素）和prepend（开头添加元素）操作。 尽管链表中的插入操作的复杂度为O(n)，但比数组的插入操作要快得多。 使用数组时我们面临的另一个问题是大小复杂性，当使用动态数组时，在添加元素时，我们必须将整个数组复制到另一个地址空间，然后添加元素，而在链表中，我们不需要 面对这样的问题。

在使用对象时，我们面临的问题是元素在内存中的随机位置，而在链表中，节点是通过指针相互连接的，指针提供了一定的顺序。

原文地址：https://blog.soshace.com/understanding-data-structures-in-javascript-linked-lists/

作者：Vivek Bisht 

译文地址：https://segmentfault.com/a/1190000024565634

更多编程相关知识，请访问：编程教学！！

The above is the detailed content of In-depth understanding of the data structure in JS (Linked-list). For more information, please follow other related articles on the PHP Chinese website!