Hi ?, welcome back to this series on linked lists. In our last article, we learned about the basics of linked lists, including their definition, terminologies, its difference with arrays, and the types of linked lists. I promised we'd dive deeper into the implementation of linked lists, so let's get started.

Course Outline

1. Introduction
2. Implementing Singly Linked Lists
   • Creating new Node
   • Insert at the Beginning
   • Insert at the End
   • Delete a Node
   • Search for a Node
   • Traverse the List
3. Conclusion

Introduction

As we've learned in the previous article, Linked Lists are fundamental data structures in the world of programming. They consist of nodes, where each node contains data and a reference (or link) to the next node (in a singly linked list) or both the next and previous nodes (in a doubly linked list) in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, allowing for efficient insertions and deletions.

Understanding the concept of a linked list is crucial for mastering data structures and algorithms. In this article, we'll dive deeper into the implementation of linked lists, starting with the basics of a singly linked list.

Implementing Singly Linked Lists

A Singly Linked List is the simplest type of linked list, where each node points to the next node in the sequence. Just like in the image below.

Now, it's time to start implementing our singly linked list basics operations. Shall we?

Creating new Node

Let's start by creating a new Node class. The Node class will have a constructor that takes in the data for the node and a next pointer which is initially set to null.

// Node class for Singly Linked List
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

This newly created Node class (which represents a node in the linked list) can be visualized as below.

Before we proceed, let's create a new instance of our SinglyLinkedList class that will hold our linked list operations.

// Singly Linked List class
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Operations come here ?
}

Insert at the Beginning

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the beginning
  insertAtBeginning(data) {
    const newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // Set the new node's next pointer to the current head
    this.head = newNode; // Update the head to be the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explanation: Inserting at the beginning is like someone new joining the line at the front. They become the new first person, linking to the previous first.

Insert at the End

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the end
  insertAtEnd(data) {
    const newNode = new Node(data); // Create a new node with the given data

    // check if the list does not have a head i.e the list is empty
    // NOTE: Every non-empty linked list will have a head
    if (!this.head) {
      this.head = newNode; // If the list is empty, set the new node as the head
      return;
    }
    let current = this.head; // Start at the head of the list
    while (current.next) {
      current = current.next; // Move to the next node in the list by updating the current node
    }
    current.next = newNode; // Set the next pointer of the last node to the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explanation: Inserting at the end is like someone joining the line at the very end. We need to walk to the end to find the last person, then link them to the new person.

Delete a Node

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Delete a node
  deleteNode(data) {
    if (!this.head) return; // If the list is empty, do nothing
    if (this.head.data === data) {
      this.head = this.head.next; // If the node to delete is the head, update the head to the next node
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next; // If the node to delete is found, update the next pointer to skip it
        return;
      }
      current = current.next;
    }
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explanation: Deleting a node is like someone in the middle of the line deciding to leave. We find that person and connect the one before them to the one after them.

Search for a Node

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Search note
  search(data) {
    let current = this.head; // Start at the head of the list
    while (current) {
      if (current.data === data) {
        // If the data is found, return true
        return true;
      }
      current = current.next; // Move to the next node
    }
    return false;
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explanation: Searching for a node is like trying to find a specific person in the line. We start at the front and ask each person until we find them or reach the end.

Traverse the List

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  traverse() {
    let current = this.head; // Start at the head of the list
    while (current) {
      console.log(current.data); // Print the data of the current node
      current = current.next; // Move to the next node
    }
  }
}

// End of class

Explanation: Traversing is like walking down the line and greeting each person. We start at the front and keep moving until we reach the end.

Conclusion

In this article, we've learned about the basics operations of linked lists and how to implement them in JavaScript. In the next article, we'll be learning about Doubly Linked Lists.

Remember, mastering linked lists requires practice. Continue solving problems and implementing these data structures in various scenarios.

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

• GitHub
• Linkedin
• X (Twitter)

Stay tuned and happy coding ?‍??