How to Implement a Linked List in JavaScript

Wild front-end such as ME, the linked list related knowledge understanding is less, today found a popular English article, from it to start the entry I believe is a good choice.

If you’re learning about data structures, you should know about linked lists. If you don’t really understand it or don’t know how to generate a linked list in JavaScript, this article will help you.

In this article we’ll discuss what a linked list is, how it differs from an array, and how to implement it in JavaScript. Let’s get started!

What is a linked list

A linked list is a linear data structure similar to an array, but instead of an array whose elements are stored in a specific memory location or index, each element of a linked list is a separate object that contains a pointer or link to the next object in the list.

Each element (often called a node) contains two items: stored data and a link to the next node. The data can be any valid data type. As shown below:

Image of a linked list

We usually use “head” as a list entry, and the “head” is a reference to the first node in the list, and the last node in the list points to NULL. If it is an empty list, the reference to head is null.

In JavaScript, a linked list looks like this:

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

Advantages of linked lists

  • You can easily remove or add nodes from a linked list without reorganizing the entire data structure. That’s one advantage it has over arrays.

Disadvantages of linked lists

  • Linked lists are slow to search and, unlike arrays, do not allow random access to data elements. Nodes must be accessed sequentially, starting with the first node.
  • Because you need to store Pointers, you need more memory than arrays.

Type of linked list

There are three types of linked lists:

  • One-way linked list: Each node contains only one pointer to the next node. That’s what we’ve been talking about up here.
  • Bidirectional linked lists: Each node contains two Pointers, one to the next node and one to the previous node.
  • Circular lists: A circular list is a variant of a linked list in which the last node points to the first node or any other node before it, thus forming a loop.

Implement a table node in JavaScript

As we said earlier, a list node contains two items: data and a pointer to the next node. We can use JavaScript to implement a list node like this:

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

Implement a linked list in JavaScript

The following code shows how to implement a linked list class using constructors. Note that if the “head” node is not passed, it will be initialized to NULL:

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

Let’s put them together

Let’s create a linked list with the class we just created. First, we create two table nodes, node1 and node2, with Pointers between them:

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

Next, we create a linked list using node1:

let list = new LinkedList(node1)        
Copy the code

Let’s try to access the nodes in the list we just created:

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

Some linked list methods:

Next, we’ll implement four helper methods for linked lists:

  1. size()
  2. clear()
  3. getList()
  4. getFirst()
1. size()

This method returns the number of nodes that exist in the list:

size() {
    let count = 0; 
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
}
Copy the code
2. clear()

This method clears the linked list:

clear() {
    this.head = null
}
Copy the code
3. getList()

This method returns the last node of the list:

getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}
Copy the code
4. getFirst()

This method returns the first node of the list:

getFirst() {
    return this.head;
}
Copy the code

conclusion

This article discussed what a linked list is and how to implement it in JavaScript. We also discussed the different types of linked lists and their overall strengths and weaknesses.

After the