Shulou(Shulou.com)06/03 Report--

This article is about how to understand the linked list in the JavaScript data structure. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article.

For JS beginners, understanding linked lists can be a difficult task because JS does not provide built-in linked lists. 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 will become more difficult.

We will discuss how to store linked lists in the database, add and delete linked lists, find and reverse linked lists, and so on. Before implementing linked lists, you need to know what the advantages of linked lists 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 arrays, operations such as adding / removing elements at the beginning or at a specific index can be a low-performance task because we have to move the indexes of all other elements. This is caused by the numbered index property of the array.

The above problems can be solved by using objects. Because the storage location of the element in the object is random, there is no need to move the index of the element when performing operations such as adding / deleting elements at the beginning or at a specific index:

Although it is fast to add and remove elements from an object, you can see from the figure above that the object is not the best choice when iterating because the elements of the object are stored in random locations. As a result, iterative operations can take a long time. This is the reason why the linked list comes out.

So what is a linked list?

It can be seen from the name itself that it is a linked list in some way. So how is it linked, and what does the list contain?

A linked list consists of nodes with two attributes: data and pointers.

The pointer within the node points to the next node in the list. The first node in the linked list is called head. To better understand, let's take a look at the description list diagram:

As you can see from the figure above, each node has two attributes, data and pointer. The pointer points to the next node in the list, and the pointer to the last node points to null. The figure above shows a single linked list.

There is a big difference between linked lists and objects. In the linked list, each node is connected to the next node by a pointer. Therefore, we have a connection between each node of the linked list, while in the object, the key-value pairs are stored randomly and are not connected to each other.

This article is translated by Xiao Zhi. Welcome to "the Great shift of the World".

Next, we implement a linked list that stores 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 created two classes, one for the linked list itself and one for the node itself. As we discussed, each node will have two attributes, a value and a pointer (corresponding to the next field).

The LinkedList class contains three attributes, head (with an initial value of null), which stores the tail of the last node of the linked list (also pointing to null) and the length property used to hold the length of the linked list. Then, let's implement the method in it.

Append (add values sequentially)

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

From the figure above, we can implement the append function in the following ways:

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

Simply explain the append method?

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

Check to see if head points to null, and now the head points to null, so we create a new object and assign the new object to head and tail:

Let node = newNode (2) this.head = newNode this.tail = newNode

Now, it's important to remember that head and tail both point to the same object.

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

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

Now, head does not point to null, so let's go to the else branch of the append function:

This.tail.next = node

Because both head and tail point to the same object, changes in tail will lead to changes in head objects, which is how objects in JS work. In JavaScript, objects are passed by reference, so both head and tail point to the same address space where the object is stored. The above line of code is equivalent to

This.head.next = node

Next line:

This.tail = node

Now, after executing the above line of code, this.head.next and this.tail point to the same object, so the head object is automatically updated every time we add a new node.

After performing the append three times, the structure of the linkedList1 should look like this:

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

As we can see from the above code, the complexity of the append function of the linked list is O (1), because we neither need to move the index nor traverse the linked list.

Shall we look at the next function?

Prepend (add values to the beginning of the linked list)

To implement this function, we use the Node class to create a new node and point the next object of the new node to the head of the linked list. Next, we assign the new node to the head of the linked list:

Like the append function, the complexity of this function is O (1).

Prepend (value) {const node = new Node (value) node.next = this.head this.head = node this.length++

Just like the append function, this function has a complexity of O (1).

Insert (add a value at a specific index)

Before implementing this function, let's take a look at one of its transformation processes. So, for understanding purposes, we first create a linked list with few values, and then visualize the insert function. The insert function takes two parameters, the value and the index:

Let linkedList2 = new LinkedList () linkedList2.append (23) linkedList2.append (89) linkedList2.append (12) linkedList2.append (3) linkedList2.insert (45)

Step 1:

Traverse the linked list until you reach the index-1 location:

Step 2:

Assign the pointer of the node with index 1 (89 in this case) to the new node (45 in this case):

Step 3:

Point next of the new node (45) to the next node (12)

This is how the insert operation is performed. Through the above visualization, we observe that the nodes need to be found at the index-1 location and the index location so that new nodes can be inserted between them. Implement in the code:

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++}

Take a brief analysis of the above functions:

If the value of index is greater than or equal to the length attribute, the operation is handed over to the append function. For the else branch, we use the Node class to create a new node, and then look at a new function, getPrevNextNodes (), through which we can receive the values of prevNode and nextNode. The getPrevNextNodes function is implemented as follows:

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}}

Return the nodes at the index-1 location and index location by traversing the linked list, pointing the next attribute of prevNode to the new node, and pointing the next attribute of the new node to nextNode.

The complexity of inserting a linked list is O (n), because we have to traverse the linked list and search for nodes at index-1 and index locations. Despite the complexity of O (n), we find that this insert operation is much faster than the insert operation of a logarithmic array, where we have to move the index of all elements to a specific index, but in the link, we only manipulate the next attribute of the node at the index-1 and index position.

Remove (delete the element at a specific index)

After the insert operation is implemented, the delete operation is easier to understand because it is almost the same as the insert operation, and when we get the prevNode and nextNode values from the getPrevNextNodes function, we must do the following in remove:

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

The complexity of the delete operation is also O (n), which is similar to the insert operation, and the delete operation in the linked list is faster than that in the array.

Reverse (inverted linked list)

Although it may seem simple, reversing the linked list is often the most confusing operation to implement, so it is often asked during the interview. Before implementing this function, let's visualize the strategy of reversing the linked list.

To reverse the linked list, we need to track three nodes, previousNode,currentNode and nextNode.

Consider the following linked list:

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

Step one:

At first, the value of previousNode is null, and the value of currentNode is head:

Step 2:

Next, we assign nextNode to currentNode.next:

Step 3:

Next, we point the currentNode.next attribute to previousNode:

Step 3:

Now, let's move previousNode to currentNode and currentNode to nextNode:

This process repeats from step 2 until currentNode equals 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}

As we can see, we traverse and move these values until currentNode = null. Finally, we assign the previousNode value to head.

The complexity of reverse operation is O (n).

Find (find the value of a specific index)

This operation is simple, we just traverse the linked list and return the node at a specific index. The complexity of this operation is also O (n).

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

Well, we have completed the basic operation of implementing a single linked list with javascript. The difference between a single-linked list and a double-linked list is that the nodes of the double-linked list have pointers to the previous node and the next node.

The linked list provides us with fast append (adding elements at the end) and prepend (adding elements at the beginning). Although the complexity of the insert operation in the linked list is O (n), it is much faster than the insert operation of the array. Another problem we face when using arrays is size complexity. When using dynamic arrays, when adding elements, we have to copy the entire array to another address space, and then add elements, and in the linked list, we don't have to face such a problem.

When using objects, the problem we face is the random location of the elements in memory, while in the linked list, nodes are connected to each other through pointers, which provide a certain order.

The above is how to understand the linked list in the JavaScript data structure. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.