Circular Linked Lists Demystified: From Novice to Node Master

I welcome you back to the series on Data Structures and Algorithms in JavaScript! 🎉 In this article, we'll be learning about Circular Linked Lists and how to implement them in JavaScript. It is important to note that Circular Linked Lists are similar to Singly Linked Lists and Doubly Linked Lists, but with a slight difference. In a Circular Linked List, the last node points back to the first node, creating a circular structure. 🔄 If you've been following this series from the beginning, you'll find this article pretty easy to understand. 😊 Haven said that, let's get started, shall we? 💪

Course Outline

1. Introduction
2. What is a Circular Linked List?
3. Types of Circular Linked Lists
   • Circular Singly Linked List
   • Circular Doubly Linked List
4. Circular Singly Linked List Implementation
5. Circular Doubly Linked List Implementation
6. Conclusion

Introduction

A circular linked list is a type of linked list data structure where the last node connects back to the first node, forming a circular loop. This structure allows for continuous traversal without any interruptions. Circular linked lists are especially helpful for tasks like scheduling and managing playlists (consider youtube videos playing one after the other with the repeat button on), this allowing for smooth navigation. In this tutorial, we’ll cover the basics of circular linked lists, how to work with them, their advantages and disadvantages, and their applications.

What is a Circular Linked List?

A circular linked list is a special type of linked list where all the nodes are connected to form a circle. Unlike a regular linked list, which ends with a node pointing to NULL, the last node in a circular linked list points back to the first node. This means that you can keep traversing the list without ever reaching a NULL value.

Before we dive into the implementation, let's first understand the types of circular linked lists we have and their structures.

Types of Circular Linked Lists

Basically, there are two types of circular linked lists based on our two previous types of linked lists (Singly and Doubly).

Circular Singly Linked List

This type of circulat linked list is built on the same structure of singly linked list but with a circularly looped structure. This is a type of circular linked list where the last node points back to the first node, creating a circular structure.

Circular Doubly Linked List

This type of circular linked list is built on the same structure of doubly linked list but with a circularly looped structure. This is a type of circular linked list where the last node points back to the first node and the first node points forward to the last node, creating a circular structure.

Now, that we have a clear picture of the types of circular linked lists, it's time to dive into how to implement them in JavaScript.

Circular Singly Linked List Implementation

The implementation of a circular singly linked list is similar to that of a singly linked list, but with a few key differences. To implement a circular singly linked list, we need to create a class for the nodes and the linked list itself.

Creating the Node class

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

This is what our singly circular linked list node looks like:

   +------+------+
   | data | next |
   +------+------+
      |      |
      |      +---> points to the next node
      |            (or back to head for the last node)
      v
 Stored value

Creating the SinglyCircularLinkedList class

class SinglyCircularLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // Methods will be implemented here
}

Explanation: We start with an empty list. The head and tail are null because we don't have any nodes yet. The size is 0 since our list is empty.

Insert at the beginning

insertAtBeginning(data) {
  const newNode = new Node(data);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
    newNode.next = this.head;
  } else {
    newNode.next = this.head;
    this.head = newNode;
    this.tail.next = this.head;
  }
  this.size++;
}

Explanation: This method adds a new node at the start of our list.

• We create a new node with the given data.
• If the list is empty, the new node becomes both the head and tail, and it points to itself.
• If the list isn't empty, we put the new node at the front and update the connections.
• We increase the size by 1 because we added a new node.

Insert at the end

insertAtEnd(data) {
  const newNode = new Node(data);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
    newNode.next = this.head;
  } else {
    this.tail.next = newNode;
    newNode.next = this.head;
    this.tail = newNode;
  }
  this.size++;
}

Explanation: This method adds a new node at the end of our list.

• We create a new node with the given data.
• If the list is empty, it's the same as inserting at the beginning.
• If the list isn't empty, we add the new node after the tail and update the connections.
• We increase the size by 1 because we added a new node.

Delete a node

deleteNode(data) {
  if (!this.head) return false;
  if (this.head.data === data) {
    if (this.size === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.tail.next = this.head;
    }
    this.size--;
    return true;
  }
  let current = this.head;
  let prev = null;
  do {
    if (current.next.data === data) {
      if (current.next === this.tail) {
        this.tail = current;
      }
      current.next = current.next.next;
      this.size--;
      return true;
    }
    current = current.next;
  } while (current !== this.head);
  return false; // Node not found
}

Explanation: This method removes a node with the given data from our list.

• If the list is empty, we can't delete anything.
• If the node to delete is the head, we handle it specially.
• For other nodes, we go through the list to find and remove the node.
• If we find and remove the node, we decrease the size by 1.
• If we can't find the node, we return false.

Traverse

traverse() {
  if (!this.head) return;
  let current = this.head;
  do {
    console.log(current.data);
    current = current.next;
  } while (current !== this.head);
}

Explanation: This method goes through each node in our list and shows its data.

• We start at the head and keep moving to the next node.
• We stop when we get back to the head (because it's circular).
• We print out the data in each node as we go.

Circular Doubly Linked List Implementation

The implementation of a circular doubly linked list is similar to that of a doubly linked list, but with a few key differences. To implement a circular doubly linked list, we need to create a class for the nodes and the linked list itself.

Creating the Node class

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

This is what our doubly circular linked list node looks like:

   +------+------+------+
   | prev | data | next |
   +------+------+------+
      |      |      |
      |      |      +---> points to the next node
      |      |            (or back to head for the last node)
      |      v
      |   Stored value
      |
      +---> points to the previous node
            (or to tail for the head node)

Creating the DoublyCircularLinkedList class

class DoublyCircularLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // Methods will be implemented here
}

Explanation: Just like with the singly circular list, we start empty. The head and tail are null, and the size is 0.

Insert at the beginning

insertAtBeginning(data) {
  const newNode = new Node(data);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
    newNode.next = newNode;
    newNode.prev = newNode;
  } else {
    newNode.next = this.head;
    newNode.prev = this.tail;
    this.head.prev = newNode;
    this.tail.next = newNode;
    this.head = newNode;
  }
  this.size++;
}

Explanation: This method adds a new node at the start of our list.

• We create a new node with the given data.
• If the list is empty, the new node becomes both the head and tail, and it points to itself in both directions.
• If the list isn't empty, we put the new node at the front and update all the connections.
• We increase the size by 1 because we added a new node.

Insert at the end

insertAtEnd(data) {
  const newNode = new Node(data);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
    newNode.next = newNode;
    newNode.prev = newNode;
  } else {
    newNode.prev = this.tail;
    newNode.next = this.head;
    this.tail.next = newNode;
    this.head.prev = newNode;
    this.tail = newNode;
  }
  this.size++;
}

Explanation: This method adds a new node at the end of our list.

• We create a new node with the given data.
• If the list is empty, it's the same as inserting at the beginning.
• If the list isn't empty, we add the new node after the tail and update all the connections.
• We increase the size by 1 because we added a new node.

Delete a node

deleteNode(data) {
  if (!this.head) return false;
  let current = this.head;
  do {
    if (current.data === data) {
      if (this.size === 1) {
        this.head = null;
        this.tail = null;
      } else {
        if (current === this.head) {
          this.head = current.next;
        }
        if (current === this.tail) {
          this.tail = current.prev;
        }
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
      this.size--;
      return true;
    }
    current = current.next;
  } while (current !== this.head);
  return false; // Node not found
}

Explanation: This method removes a node with the given data from our list.

• If the list is empty, we can't delete anything.
• We go through the list to find the node with the data we want to remove.
• If we find it, we remove it by updating the connections of the nodes around it.
• We handle special cases when removing the head or tail.
• If we remove a node, we decrease the size by 1.
• If we can't find the node, we return false.

Traverse forward

traverseForward() {
  if (!this.head) return;
  let current = this.head;
  do {
    console.log(current.data);
    current = current.next;
  } while (current !== this.head);
}

**Explanation: **This method goes through each node in our list from start to end and shows its data.

• We start at the head and keep moving to the next node.
• We stop when we get back to the head (because it's circular).
• We print out the data in each node as we go.

Traverse backward

traverseBackward() {
  if (!this.head) return;
  let current = this.tail;
  do {
    console.log(current.data);
    current = current.prev;
  } while (current !== this.tail);
}

Explanation: This method goes through each node in our list from end to start and shows its data.

• We start at the tail and keep moving to the previous node.
• We stop when we get back to the tail (because it's circular).
• We print out the data in each node as we go.

Conclusion

In conclusion, circular linked lists are a special type of linked list where the last node points back to the first node, creating a circular structure. This structure allows for continuous traversal without any interruptions. Circular linked lists are especially helpful for tasks like scheduling and managing playlists (consider youtube videos playing one after the other with the repeat button on), this allowing for smooth navigation.

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 👨‍💻🚀