What is Linked List?

Linked List is a linear data structure, that stores information/data as a set of linearly connected nodes. Each node in this list contains data along with a pointer to another node. It can only be accessed in sequence, either from the beginning or from the end. Linked list looks similar to an array but it doesn’t store the index of its values and makes random access at a specific index unavailable without traversing the entire linked list from the head to the Null.

Properties of Linked List

1. Linked Lists are dynamic.

2. It can only be accessed in a specific order.

3. Nodes are not stored in the contiguous memory location.

4. A node contains data and the pointer.

5. A particular node can be accessed by the pointer stored in the previous node.

6. A unique pointer known as the head is used to point to the first node of the linked list.

7. The last node points to Null, indicating the list’s conclusion.

Types of Linked lists

There are three types of Linked lists. They are —

Singly Linked List

The simplest linked list we have discussed up to this point can only be navigated in one way, from start to finish. There is just one direction of entrance permitted.

Doubly Linked List

This type of linked list is accessible in both directions. This linked list’s node has two pointers instead of just one, allowing users to access both the next and previous nodes from the current node. It is simple to add a node before the existing one.

Circular Linked List

This linked list is capable of both sequential and circular traversal. Instead of referring to null, the linked list’s last node refers to the first node. It typically appears in notions relating to queues.

Example of implementing a linked list using JavaScript

For the example, I will create a function for creating a new Node object, the LinkedList class with the proper constructor, the insert() and print() methods.

// Creating a function for creating a new Node object

function createNode(value) {
 return {
  value: value,
  next: null,
 };
}

// Creating the LinkedList class with the proper constructor and the  insert() and print() methods

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

 insert(value) {
  this.length++;
  let newNode = createNode(value);

  if (this.tail) {
   this.tail.next = newNode;
   this.tail = newNode;
   return newNode;
  }

  this.head = this.tail = newNode;
  return newNode;
 }

 print() {
  let current = this.head;
  while (current) {
   console.log(current.value);
   current = current.next;
  }
 }
}

const linkedList = new LinkedList();

linkedList.insert(7);
linkedList.insert(true);
linkedList.insert(20);
linkedList.print(); // 7 true 20

console.log(linkedList);

Output:

7
true
20
LinkedList {
  head: { value: 7, next: { value: true, next: [Object] } },
  tail: { value: 20, next: null },
  length: 3
}

Conclusion

I’ve attempted to explain the operation of the linked list data structure as well as how to implement one using JavaScript. I have also added how to create a node object using both JavaScript class and function keywords.

Thank you for reading, and maybe this lesson has helped you learn something new 😉