Just Learn Code

Mastering Linked Lists: A Comprehensive Guide in JavaScript

Introduction to Linked List Data Structure

Data structures are an essential aspect of computer science, and one such structure is the linked list. Linked lists are used to hold, organize, and manipulate data in specific ways.

A linked list data structure consists of nodes linked together sequentially, with each node containing a value and a pointer to the next node. Linked lists are dynamic data structures, meaning they can expand and shrink their size according to the requirement of the process.

In this article, we will dive deep into the working of the linked list data structure and the different types of linked lists. We will also discuss how to implement these data structures using JavaScript and explore the function and class methods to create, print, insert, remove, and search nodes.

Working of Linked List

A linked list differs from other data structures such as arrays, which occupy contiguous memory space, whereas linked lists occupy non-contiguous memory space. Linked lists hold references to other nodes as opposed to array’s indexes.

A node in a linked list holds the value and a reference or a pointer to the next node in the list.

To better understand the working of a linked list, let us take an example.

Imagine an unordered list of items that need to be stored, such as a shopping list. In a linked list, each item on the shopping list would be a node.

Each node would contain the item’s name and a reference or a pointer to the next item on the list. The first item on the list would be the head of the linked list.

Types of Linked List

There are three types of linked lists:

Singly Linked List: A singly linked list has each node contain only one reference or pointer to the next node in the list. This type of linked list is simple and efficient to use as operations only need to be performed on one reference at a time.

Doubly Linked List: A doubly linked list has each node containing two pointers- one to the next node and one to the previous node. This type of linked list offers more flexibility in the operations that can be performed on the list since each node now holds two references separate and the length of the list can also be calculated easily.

Circular Linked List: A circular linked list is a linked list where the last node points to the first node, completing a circle. This type of linked list is often used in gaming applications where there are many objects that need to move continuously.

Implementing Linked List using JavaScript

Creating a New Node Object

In JavaScript, we can create a new node object using a constructor or a class. A node object contains the node’s value and reference to the next node.

An example of how to create a node object using a constructor method is:

“`

function Node(value) {

this.value = value;

this.next = null;

}

“`

The `value` property stores the node’s value or object, and `next` is a reference to the next node in the list, and it is null by default.

Writing the LinkedList Class

After creating a node object, we can now write the LinkedList class. The LinkedList class has a constructor method that creates a new linked list and initializes two properties, `head` and `tail`.

The `head` property holds a reference to the first node in the list, and the `tail` property holds a reference to the last node in the list. The constructor also initializes a `length` property representing the number of nodes in the list.

“`

class LinkedList {

constructor() {

this.head = null;

this.tail = null;

this.length = 0;

}

}

“`

Inserting and Printing Nodes

To insert a new node to the end of the list, we can use the `insert()` method. The `insert()` method creates a new node, assigns its value, and sets its next property to `null`.

It then checks if the list is empty; if it is, it sets the new node as the head of the list. If not, it sets the new node as the tail node and updates the `tail` property.

Finally, the length of the list is incremented.

“`

insert(value) {

const node = new Node(value);

if (!this.head) {

this.head = node;

this.tail = node;

} else {

this.tail.next = node;

this.tail = node;

}

this.length++;

}

“`

To display the linked list, we can use the `print()` method, which traverses the list from the head node and prints the value of each node.

“`

print() {

let current = this.head;

while (current) {

console.log(current.value);

current = current.next;

}

}

“`

Removing Nodes

To remove a node from the list, we can use the `remove()` method, which takes the node’s value and finds the node. It then assigns the previous node’s next property to the next node, effectively removing the node from the list.

“`

remove(value) {

let current = this.head;

let previous = null;

while (current) {

if (current.value === value) {

if (previous === null) {

this.head = current.next;

} else {

previous.next = current.next;

}

this.length–;

return current.value;

}

previous = current;

current = current.next;

}

return null;

}

“`

Inserting and

Removing Nodes from the Head

To insert a new node to the beginning of the list, we can use the `insertHead()` method, which creates a new node and makes the new node the head of the list.

“`

insertHead(value) {

const node = new Node(value);

if (!this.head) {

this.head = node;

this.tail = node;

} else {

node.next = this.head;

this.head = node;

}

this.length++;

}

“`

To remove a node from the beginning of the list, we can use the `removeHead()` method, which assigns the current head’s next property to the new head, effectively removing the current head from the list.

“`

removeHead() {

if (!this.head) {

return null;

}

const value = this.head.value;

this.head = this.head.next;

this.length–;

return value;

}

“`

Bonus: Inserting and

Removing Nodes at a Specific Index

To insert a node at a specific index, we can use the `insertIndex()` method, which takes the node’s value and index as arguments. It then traverses the list and finds the node before the index and the node after the index.

It sets the `next` property of the node before the index to the new node and sets the `next` property of the new node to the node after the index.

“`

insertIndex(value, index) {

if (index < 0 || index > this.length) {

return false;

}

if (index === 0) {

this.insertHead(value);

return true;

}

if (index === this.length) {

this.insert(value);

return true;

}

const node = new Node(value);

let current = this.head;

let previous = null;

let i = 0;

while (i < index) {

previous = current;

current = current.next;

i++;

}

previous.next = node;

node.next = current;

this.length++;

return true;

}

“`

To remove a node at a specific index, we can use the `removeIndex()` method, which takes the index as an argument.

It then traverses the list and finds the node before the index and the node after the index. It sets the `next` property of the node before the index to the node after the index, effectively removing the node at the index from the list.

“`

removeIndex(index) {

if (index < 0 || index >= this.length) {

return null;

}

if (index === 0) {

return this.removeHead();

}

let current = this.head;

let previous = null;

let i = 0;

while (i < index) {

previous = current;

current = current.next;

i++;

}

const value = current.value;

previous.next = current.next;

this.length–;

return value;

}

“`

Conclusion

In summary, the linked list data structure is an essential tool for holding, organizing, and manipulating data in a specific way. JavaScript offers many built-in methods for creating and manipulating linked lists.

Today we learned about how to create a new node object, write the LinkedList class, insert, remove, print the linked list, and implement the linked list’s functions to insert and remove nodes from the head and at a specific index. With this knowledge, we can implement this data structure in our projects, which benefits from dynamic functionality and efficient memory usage.

Introduction to Linked List Data Structure

Data structures are fundamental to computer science, and one such structure is the linked list. Linked lists are used to hold, organize, and manipulate data in specific ways.

They are dynamic data structures that can expand and shrink their size according to the requirement of the process.

In this article, we will dive deeper into the working of the linked list data structure and explore how to implement these data structures using JavaScript.

We will cover the creation of a new node object, the writing of the LinkedList class, inserting, removing, and printing nodes, as well as inserting and removing nodes from the head and at a specific index.

Working of Linked List

A linked list differs from other data structures such as arrays, which occupy contiguous memory space, whereas linked lists occupy non-contiguous memory space. In a linked list, each node holds a value and a reference or a pointer to the next node.

To better understand the workings of a linked list, let us consider an unordered list of items that need to be stored, such as a shopping list. In a linked list, each item on the shopping list would be a node holding the item’s name and a reference or a pointer to the next item on the list.

The first item on the list would be the head of the linked list.

Types of Linked List

The most commonly used types of linked lists are singly linked lists, doubly linked lists, and circular linked lists. Singly Linked List: A singly linked list has each node containing only one reference or pointer to the next node in the list.

This type of linked list is simple and efficient to use as operations only need to be performed on one reference at a time. Doubly Linked List: A doubly linked list has each node containing two pointers – one to the next node and one to the previous node.

This type of linked list offers more flexibility in the operations that can be performed on the list since each node now holds two references separate and the length of the list can also be calculated easily. Circular Linked List: A circular linked list is a type of linked list where the last node points to the first node, completing a circle.

This type of linked list is often used in gaming applications where there are many objects that need to move continuously.

Implementing Linked List using JavaScript

Creating a New Node Object

In JavaScript, we can create a new node object using a constructor or a class. A node object contains the node’s value and a reference to the next node.

To create a new node object using a constructor method, we can use the following code:

“`

function Node(value) {

this.value = value;

this.next = null;

}

“`

The `value` property stores the node’s value or object, and `next` is a reference to the next node in the list, and it is null by default.

Writing the LinkedList Class

After creating a node object, we can write the LinkedList class. The LinkedList class has a constructor method that creates a new linked list and initializes two properties, `head` and `tail`.

The `head` property holds a reference to the first node in the list, and the `tail` property holds a reference to the last node in the list. The constructor also initializes a `length` property representing the number of nodes in the list.

“`

class LinkedList {

constructor() {

this.head = null;

this.tail = null;

this.length = 0;

}

}

“`

Inserting and Printing Nodes

To insert a new node at the end of the list, we can use the `insert()` method. We create a new node, set its value, and its `next` property to `null`.

Then, we check if the list is empty; if it is, we set the new node as the head of the list. If not, we set the new node as the tail node and update the `tail` property.

Finally, we increment the length of the list. “`

insert(value) {

const node = new Node(value);

if (!this.head) {

this.head = node;

this.tail = node;

} else {

this.tail.next = node;

this.tail = node;

}

this.length++;

}

“`

To display the linked list, we can use the `print()` method.

The `print()` method traverses the list from the head node and prints the value of each node. “`

print() {

let current = this.head;

while (current) {

console.log(current.value);

current = current.next;

}

}

“`

Removing Nodes

To remove a node from the list, we can use the `remove()` method, which takes the node’s value and finds the node. Then, it assigns the previous node’s `next` property to the next node, effectively removing the node from the list.

“`

remove(value) {

let current = this.head;

let previous = null;

while (current) {

if (current.value === value) {

if (previous === null) {

this.head = current.next;

} else {

previous.next = current.next;

}

this.length–;

return current.value;

}

previous = current;

current = current.next;

}

return null;

}

“`

Inserting and

Removing Nodes from the Head

To insert a new node at the beginning of the list, we can use the `insertHead()` method, which creates a new node and makes it the head of the list. “`

insertHead(value) {

const node = new Node(value);

if (!this.head) {

this.head = node;

this.tail = node;

} else {

node.next = this.head;

this.head = node;

}

this.length++;

}

“`

To remove a node from the beginning of the list, we can use the `removeHead()` method, which assigns the `next` property of the current head to the new head, effectively removing the current head from the list.

“`

removeHead() {

if (!this.head) {

return null;

}

const value = this.head.value;

this.head = this.head.next;

this.length–;

return value;

}

“`

Bonus: Inserting and

Removing Nodes at a Specific Index

To insert a node at a specific index, we can use the `insertIndex()` method, which takes the node’s value and index as arguments. It then traverses the list and finds the node before the index and the node after the index.

It sets the `next` property of the node before the index to the new node and sets the `next` property of the new node to the node after the index. “`

insertIndex(value, index) {

if (index < 0 || index > this.length) {

return false;

}

if (index === 0) {

this.insertHead(value);

return true;

}

if (index === this.length) {

this.insert(value);

return true;

}

const node = new Node(value);

let current = this.head;

let previous = null;

let i = 0;

while (i < index) {

previous = current;

current = current.next;

i++;

}

previous.next = node;

node.next = current;

this.length++;

return true;

}

“`

To remove a node at a specific index, we can use the `removeIndex()` method, which takes the index as an argument.

It then traverses the list and finds the node before the index and the node after the index. It sets the `next` property of the node before the index to the node after the index, effectively removing the node at the index from the list.

“`

removeIndex(index) {

if (index < 0 || index >= this.length) {

return null;

}

if (index === 0) {

return this.removeHead();

}

let current = this.head;

let previous = null;

let i = 0;

while (i < index) {

previous = current;

current = current.next;

i++;

}

const value = current.value;

previous.next = current.next;

this.length–;

return value;

}

“`

Conclusion

Linked lists are essential data structures that allow for dynamic functionality and efficient memory usage. In this article, we explored the workings of linked lists and how to implement them using JavaScript.

We learned how to create a new node object, write the LinkedList class,

Popular Posts