Javascript Singly Linked Lists: Where, When, And How

👋 Every time I learn about Singly Linked Lists, I find myself thinking, "I've never used this before, and I have no idea where to use it." 🤔 If you've ever felt the same way, this post is for you!

Table of Contents

1. What is a Singly Linked List? 🔗
2. Queue Implementation 🔄
3. Stack Implementation 📚
4. Undo Feature 🖋
5. Browser History 🌐

1. What is a Singly Linked List? 🔗

There's a ton of information out there about what a Singly Linked List is, but let me write it one more time for good measure!

📦 Node Structure 📦

A Singly Linked List is made up of elements known as nodes. Each node consists of two parts:

• Data: The actual value or information.
• Next: A reference to the next node in the list.

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

📜 List Structure 📜

The list itself has two main pointers:

• Head: Points to the first node in the list.
• Tail: Points to the last node in the list.

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

  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    this.tail.next = newNode;
    this.tail = newNode;
  }
}

Having a head and a tail allows for efficient operations, such as quick access to the first and last elements, and makes appending elements at the end an O(1) operation.

Here's a simple visualization to help you understand:

Now we are ready to discuss where to use it

2. Queue Implementation 🔄

What is a Queue?
A queue is a data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed.

Why Use a Singly Linked List?
Using a Singly Linked List for a queue implementation allows for dynamic resizing and efficient use of memory. You can easily enqueue an element by appending it at the tail and dequeue an element by removing it from the head.

Example Scenario: Task Scheduling
In a multi-threaded environment, tasks can be scheduled based on their priority or order of arrival using a queue. A Singly Linked List can be particularly useful here due to its dynamic nature.

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

  enqueue(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    this.tail.next = newNode;
    this.tail = newNode;
  }

  dequeue() {
    if (!this.head) return null;
    const temp = this.head;
    this.head = this.head.next;
    return temp.data;
  }
}

3. Stack Implementation 📚

What is a Stack?
A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. The last element added is the first one to be removed.

Why Use a Singly Linked List?
Arrays are commonly used for stack implementations, but Singly Linked Lists offer dynamic resizing without manual intervention, better memory efficiency by allocating space only when needed, quicker element deletion with O(1) complexity, and no wasted space, unlike dynamic arrays that may double in size.

Example Scenario: Expression Evaluation
In algorithms that require expression evaluation or syntax parsing, a stack is often used. A Singly Linked List can be a good fit for such cases.

class Stack {
  constructor() {
    this.top = null;
  }

  push(data) {
    const newNode = new Node(data);
    newNode.next = this.top;
    this.top = newNode;
  }

  pop() {
    if (!this.top) return null;
    const temp = this.top;
    this.top = this.top.next;
    return temp.data;
  }
}

4. Undo Feature 🖋

What is an Undo Feature?
An undo feature allows users to revert their last action. This is common in text editors, drawing applications, and many other software.

Why Use a Singly Linked List?
Each node in the list can represent a state of the document or drawing. By traversing the list backward, you can easily implement an undo feature.

Example Scenario: Text Editor
In a text editor, each node could represent the text content at a given time. The undo feature would simply navigate back through the list to previous states.

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

  addAction(action) {
    const newNode = new Node(action);
    newNode.next = this.head;
    this.head = newNode;
  }

  undo() {
    if (!this.head) return null;
    const temp = this.head;
    this.head = this.head.next;
    return temp.data;
  }
}

5. Browser History 🌐

What is Browser History?
Browser history is a record of web pages that you have visited in the past.

Why Use a Singly Linked List?
Each node in the list can represent a visited web page. The head can point to the most recently visited page, and the tail can point to the first page you visited in that session.

Example Scenario: Web Browser
In a web browser, you can use a Singly Linked List to implement the forward and backward navigation features efficiently.

class BrowserHistory {
  constructor() {
    this.current = null;
  }

  visitPage(url) {
    const newNode = new Node(url);
    newNode.next = this.current;
    this.current = newNode;
  }

  goBack() {
    if (!this.current) return null;
    const temp = this.current;
    this.current = this.current.next;
    return temp.data;
  }
}

I'd love to hear your thoughts! 💭 Have you ever implemented or used a Singly Linked List in your projects? 🛠️ What were your use cases? Share your experiences in the comments below. 🗨️ Your insights could be the gem 💎 someone else is looking for!

If you found this post insightful and want to dive deeper into the world of coding, consider subscribing to my YouTube channel: WebForDevs. 📺