Linked List in Javascript

What is Linked List in Javascript

LinkedList is a kind of dynamic data structure in which we can easily add or remove elements.
It has a structure similar to arrays, with the difference that in a LinkedList, the elements have a link to the next item in the list.

Example:

const linked_list = [
    head: [
        value: 3
        next: [
            value: 5                                             
            next: [
                value: 7
                next: null
                ]
            ]
        ]
    ]
];

Linked Lists are an important data structure in computer science, and they can be implemented in many programming languages, including Javascript. 

A Linked List is a data structure that consists of a sequence of nodes, where each node contains a value and a reference to the next node in the sequence. 

Types of Linked Lists

There are several types of Linked Lists: 

• Singly Linked Lists, where each node only has a reference to the next node in the sequence.
• Doubly Linked Lists, where each node has references to both the next and previous nodes.
• Circular Linked List, where the last node points to the first node or any other previous node forming a loop.

Linked Lists have advantages such as dynamic memory allocation and efficient insertion and deletion of nodes, but they also have disadvantages such as slower access times and higher memory usage compared to arrays.

Using linked lists

• Linked Lists have many applications in Javascript, including as the underlying data structure for stacks and queues:
  • A stack is a Last-In-First-Out (LIFO) data structure where elements are added and removed from the top of the stack.
  • A queue is a First-In-First-Out (FIFO) data structure where elements are added to the back of the queue and removed from the front.
    We can implement stacks and queues using Linked Lists by adding and removing nodes from either end of the sequence.
• Linked Lists can also be used to implement hash tables, which are a data structure that allows for efficient lookup of values based on a key, sometimes used to store passwords encrypted using a hash key.
  In a hash table implementation, each key-value pair is stored in a node, and the nodes are stored in an array of Linked Lists based on the hash value of the key.
• Linked Lists are used in many graph algorithms, such as depth-first search and breadth-first search, which traverse graphs by following the references between nodes.

Linked Lists are a powerful data structure that can be implemented in Javascript to solve a wide range of problems. By creating a Node class and manipulating the references between nodes, we can implement basic and advanced operations on Linked Lists have many applications in Javascript, including as the underlying data structure for stacks and queues, hash tables, and graph algorithms. While Linked Lists have advantages and disadvantages compared to other data structures, they are an important tool in any programmer's toolkit.

Implement a Linked List in Javascript

To implement a Linked List in Javascript, we first need to create a Node class that defines the structure of each node in the sequence. 

class NodeClass {
  constructor(element) {
    this.element= element;
    this.next = null;
  }
}

The Node class should have a constructor that initializes the value of the node and the reference to the next node.

A linkedList class will be created and indicates the initial node. From there, the node class will be the one that links one element to another. This would be in the case of a simple linked list. In the case of another type of linked list, everything would be a bit more complicated.

class LinkedListName {
    constructor(head = null) {
        this.head = head
    }
    methods_add_delete_(){..}
}

let node1 = new Node(4);
node1.next = node2;

let myLinkedList = new LinkedListName(node1)

Singly Linked Lists

As we have said so far, we created a node class that would pair one node with the next and a class that would include the linked list and indicate the header node with the rest of the functions to add, delete, show, etc.

We can then implement basic operations such as adding, deleting, and searching nodes by manipulating the references between nodes:

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

class SinglyLinkedList{

    constructor(){

      this.head = null;

      this.tail = null;

      this.length = 0;

    }

    methods_add_delete_show(){...}

}

let node1 = new Node(4)
let node2 = new Node(6)
node1.next = node2

let myLinkedList = new LinkedList(node1)

Try It YourSelf

Doubly Linked Lists

We created a node class that would match one node to the next and to the previous node.
We also created a class that would include the linked list and would indicate the head node and the tail node in the constructor function, it would also include the rest of the methods to operate with the linked list, such as functions to add, delete, show, etc.

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

class DoublyLinkedList {
    constructor(value) {
        this.head = {
            value: value,
            next: null,
            previous: null
        };
        this.length = 1;
        this.tail = this.head;
    }
    methods_add_delete_show(){...}
}
let myLinkedList = new DoublyLinkedList(4);
myLinkedList.append(3);
...

Try It YourSelf

Circular Linked List

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

class CircularLinkedList{
  constructor(){
    this.length = 0;
    this.head = null;
  }
  methods_add_delete_show(){...}
}

Try It YourSelf

Operations and Methods to perform in a Linked List

• add(element): Adds an element to the end of the list.
• insertAt(element, index): Inserts an element at the given index into a list.
• removeAt(index): Removes and returns a list item at the specified index
• removeElement(element): This method removes the element from the list. Returns the removed element, or if not found returns -1.
• removeHead(): Removes the first item from the list.
• indexOf(element): Returns the index of a given element if the element is in the list.
• isEmpty(): Returns true if the list is empty.
• printList(): Prints the content of the list.
• getElementAt(index): Returns the node at the given position in the list.
• toString(): Matches all the elements of the list and returns them as a string.
• toArray(): Converts the bound list to an array and returns it.
• isPresent(element): Returns true if the element is present in the list, otherwise returns false.
• size(): Returns the size of the list.
• getHead(): Returns the entire list to iterate forward.