Algorithms and Data Structures in JS — Linked-List

List (Linked – the list)

Earlier we discussed how to use stacks and queues to store data. They are actually a kind of list, and the underlying data structure is array.

But arrays are not always the best data structures because, in many programming languages, arrays are fixed in length, and it is very difficult to add new elements if the array is already filled with data. Moreover, deleting and adding elements to an array often involves shifting other elements of the array forward or backward, which can be tedious.

Arrays in JS, however, do not have this problem, mainly because they are implemented as objects, but are much less efficient than other languages (such as C or Java).

Instead, consider using linked-lists, which can be used in almost any situation where a one-dimensional array can be used, except for random access to data. If you happen to be using a high-level language like C or Java, you’ll find that linked lists perform much better than arrays.

There are many types of lists: one-way lists, two-way lists, one-way cyclic lists, and two-way cyclic lists. Next, we will implement a one-way list based on objects, because it is the most widely used.

Definition of linked list

First, to implement linked lists, we first understand some of the basic things linked lists, because this is very important!

A linked list is a collection of nodes, each of which uses a reference to an object to refer to its next node. A reference to another node is called a chain. Below I draw a simple link structure diagram, easy to understand.

Linked list structure diagram

Data holds the data, and next holds a reference to the next linked list. In the figure above, we say data2 follows data1, not that data2 is the second element in the list. Above, it’s worth noting that we point the end of the list to a null node, indicating where the link ends.

Since it is difficult to determine the starting point of a linked list, many implementations add a special node at the beginning of the list, called the head node, to represent the head of the list. After modification, the linked list looks like this:

A linked list with head nodes

Inserting a node into a linked list is efficient by modifying the node before it (the precursor) to point to the newly added node and the new node to point to the node that the original precursor pointed to. I’ll show you how to insert a datA4 node after a data2 node using a picture.

Insert the node

Similarly, removing a node from a linked list is simple. Simply point the precursor node of the node to be deleted to the node to be deleted and point the node to null, and the node is deleted successfully. Below is a graphic illustration of how to remove the datA4 node from a linked list.

Remove nodes

Design of linked lists

We designed the LinkedList to contain two classes, one is Node class to represent nodes, and the other is LinkedList class to insert nodes, delete nodes, etc.

The Node class

The Node class contains two attributes: Element holds data on a Node and next holds a link to the next Node.

Function Node(element) {this.element = element; This.next = null; // Next node link}Copy the code

LinkedList class

The LinkedList class provides methods for manipulating linked lists, including inserting and removing nodes, finding a given value, and so on. Note that it has only one property, which is to use a Node object to hold the head Node of the list.

Its constructor is implemented as follows:

Function LList () {this.head = new Node('head'); // header this.find = find; This. insert = insert; This. remove = remove; This.findprev = findPrev; This. display = display; // Display list}Copy the code

The next attribute of the head node is initialized to null, and when a new element is inserted, next points to the new element.

Next, let’s look at the implementation of the specific method.

Insert: Inserts a node into the list

Let’s examine the INSERT method first. To insert a node, we must specify which node to insert before or after. Let’s first look at how to insert a node after a known node.

To insert a new node after a known one, we first need to find that node. To do this, we need a find method to walk through the list looking for the given data. If found, the method returns the node where the data was stored. So let’s implement the find method first.

Find: Finds the specified node

Function find (item) {var currNode = this.head; while ( currNode.element ! = item ){ currNode = currNode.next; } return currNode; }Copy the code

The find method also shows how to move around a linked list. First, we create a new node, assign the first node of the list to the newly created node, and then loop through the list. If the element property of the current node does not match the information we are looking for, we move the current node to the next node. If the search is successful, the method returns the node containing the data. Otherwise, null is returned.

Once the node is found, we can insert the new node into the list, set the next attribute of the new node to the value of the next attribute of the next node, and set the next attribute of the next node to point to the new node as follows:

Function insert (newElement, item) {var newNode = newNode (newElement); var currNode = this.find( item ); newNode.next = currNode.next; currNode.next = newNode; }Copy the code

Now we can test our linked list. Wait, let’s first define a display method to display the list elements, otherwise how do we know?

Display: Displays the linked list

Function display () {var currNode = this.head; while ( ! (currNode.next == null) ){ console.log( currNode.next.element ); currNode = currNode.next; }}Copy the code

We assign the first node to a new variable and loop through the list until the next property of the current node is null. We print out the data for each node as we loop.

var fruits = new LList();

fruits.insert('Apple' , 'head');
fruits.insert('Banana' , 'Apple');
fruits.insert('Pear' , 'Banana');

console.log(fruits.display());       // Apple
                                     // Banana
                                     // Pear
Copy the code

Remove: Removes a node from the linked list

To remove a node from a linked list, we first look for the node before the node to be deleted. Once we find it, we modify its next property so that it does not point to the node to be deleted, but to the next node of the node to be deleted. We then need to define a findPrevious method to traverse the linked list and check whether the next node of each node stores the data to be deleted. If found, the node is returned so that its next attribute can be modified. Function findPrev(item) {var currNode = this.head; while ( ! ( currNode.next == null) && ( currNode.next.element ! = item )){ currNode = currNode.next; } return currNode; }Copy the code

In this way, the implementation of the remove method is easily solved

Function remove (item) {var prevNode = this.findPrev(item); if( ! ( prevNode.next == null ) ){ prevNode.next = prevNode.next.next; }}Copy the code

We will test the remove method by writing a test program:

Insert ('Grape', 'Pear'); insert('Grape', 'Pear'); console.log(fruits.display()); // We eat bananas and fruits. Remove ('Banana'); console.log(fruits.display()); // Apple // Pear // GrapeCopy the code

Great! Successful, you are now ready to implement a basic one-way list.

Two-way linked list

Although it is easy to traverse a list from the head node, it is not easy to traverse it from back to front. We can add a previous attribute to the Node class to make it point to the previous Node link, thus forming a bidirectional linked list, as shown in the following figure:

Two-way linked list

At this point, inserting a node into the list changes the precursor and successor of the node, but the efficiency of deleting the node is improved and there is no need to find the precursor of the node to be deleted.

Implementation of bidirectional linked list

To implement bidirectional lists, add a previous attribute to the Node class:

Function Node(element) {this.element = element; This.next = null; // Next node link this.previous = null; // Last node link}Copy the code

The insert method of a bidirectional linked list is similar to that of a single linked list, but requires setting the previous property of the new node to point to the previous of the node, as defined below:

Function insert (newElement, item) {var newNode = newNode (newElement); var currNode = this.find( item ); newNode.next = currNode.next; newNode.previous = currNode; currNode.next = newNode; }Copy the code

The remove method of the bidirectional linked list is more efficient than the single linked list. There is no need to find the precursor node, as long as the node to be deleted is found, and then the next attribute of the node to be deleted points to the successor of the node to be deleted, and the subsequent attribute of the node is set to point to the predecessor of the node to be deleted. The definition is as follows:

Function remove (item) {var currNode = this.find (item); if( ! ( currNode.next == null ) ){ currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; }}Copy the code

There are also some methods to reverse display the linked list dispReverse, find the last element of the linked list findLast and so on. I believe you have the idea. Here I give a basic bidirectional linked list completion code for your reference.

Function Node(element) {this.element = element; This.next = null; // Next node link this.previous = null; Function LList () {this.head = new Node('head'); this.find = find; this.findLast = findLast; this.insert = insert; this.remove = remove; this.display = display; this.dispReverse = dispReverse; } function find (item) {var currNode = this.head; while ( currNode.element ! = item ){ currNode = currNode.next; } return currNode; } function findLast () {var currNode = this.head; while ( ! ( currNode.next == null )){ currNode = currNode.next; } return currNode; Function insert (newElement, item) {var newNode = newNode (newElement); var currNode = this.find( item ); newNode.next = currNode.next; newNode.previous = currNode; currNode.next = newNode; } function display () {var currNode = this.head; while ( ! (currNode.next == null) ){ console.debug( currNode.next.element ); currNode = currNode.next; Function dispReverse () {var currNode = this.findlast (); while ( ! ( currNode.previous == null )){ console.log( currNode.element ); currNode = currNode.previous; Function remove (item) {var currNode = this.find (item); if( ! ( currNode.next == null ) ){ currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } } var fruits = new LList(); fruits.insert('Apple' , 'head'); fruits.insert('Banana' , 'Apple'); fruits.insert('Pear' , 'Banana'); fruits.insert('Grape' , 'Pear'); console.log( fruits.display() ); // Apple // Banana // Pear // Grape console.log( fruits.dispReverse() ); // Grape // Pear // Banana // AppleCopy the code

Circular linked list

A circular list is similar to a singly linked list in that the node type is the same. The only difference is that when a circular list is created, the next property of its head node executes itself, i.e

head.next = head;
Copy the code

This behavior causes the next attribute of each node in the list to point to the head node of the list. In other words, the last node of the list points to the head node, forming a circular list, as shown below:

Circular linked list

Principle I believe you have understood, circular list here on the subsidy code, I believe you can independently complete!

So far, we have a more profound understanding of the linked list, if you want to make our linked list more sound, we can also play their own thinking, add to the linked list such as moving forward a few nodes, moving back a few nodes, show the current node and other methods, we come on together!