How to Check if Linked List Is Empty in C++

1. Use Root Element to Check if Linked List Is Empty in C++
2. Check if Linked List Is Empty Without Using a Root Element in C++
3. Use Root Points to Check if Linked List Is Empty in C++

The linked list functions as an array and uses pointers for its implementation. It is the simplest example of a dynamic data structure that can grow and shrink from any point in the array.

A linked list has multiple dynamically allocated nodes containing a value and a pointer. This tutorial will teach you three ways to check if a linked list is empty in C++.

Use Root Element to Check if Linked List Is Empty in C++

The root in a linked list acts as an element that is always present even if the list is empty. The other use of having a root in a linked list is to link the last element back to the root forming a cycle.

In C++, there’re two primary ways to check if a linked list is empty either by providing a pointer to the first element of a list (for example: if (root->next == NULL) { /* empty list */ }) or by link back the list element of a linked list to its root to form a cycle (if (root->next == root) { /*empty list */ }). Using a root element to check if a linked list is empty requires at least one linked list node that doesn’t hold data.

Code Example:

#include <bits/stdc++.h>
using namespace std;

class Node {
 public:
  int data;
  Node *next;

  Node() {
    data = 0;
    next = NULL;
  }
};

class linked_list {
  Node *root;

 public:
  linked_list() { root = NULL; }

  Node *getRoot() { return root; }

  void add_node(int n) {
    Node *temp = new Node();
    temp->data = n;
    temp->next = NULL;
    if (root == NULL) {
      root = temp;
      root->next = root;
    } else {
      Node *last = root;
      while (last->next != root) {
        last = last->next;
      }
      temp->next = root;
      last->next = temp;
    }
  }

  void printList() {
    Node *temp = root;
    if (temp != NULL) {
      do {
        cout << temp->data << " ";
        temp = temp->next;
      } while (temp != root);
    }
  }

  bool isEmpty() {
    if (root->next == root && root->data == 0) return true;
    return false;
  }
};

int main() {
  linked_list l1;
  l1.add_node(5);
  l1.add_node(10);
  l1.add_node(15);

  if (l1.isEmpty())
    cout << "The list is empty!\n";
  else {
    cout << "The list is not empty! List contains:\n";
    l1.printList();
  }
  return 0;
}

Output:

The list is not empty! List contains:
5 10 15

A head or root node represents its start position in a linked list. With root, there is always one element.

Check if Linked List Is Empty Without Using a Root Element in C++

Without a root, the list pointer is NULL when the linked list is empty. The complexity of checking whether the linked list is empty or not in this approach is as same as with the root element, i.e. O(1).

You need to initialize a sensible default value to a variable when you allocate a new node so it can be easy to identify a data member with zero length to identify its NULL behavior.

Code Example:

#include <bits/stdc++.h>
using namespace std;

class Node {
 public:
  int data;
  Node* next;
};

void push(Node** head_ref, int new_data) {
  Node* new_node = new Node();
  new_node->data = new_data;
  new_node->next = (*head_ref);
  (*head_ref) = new_node;
}

bool isEmpty(Node** list) {
  if ((*list) == NULL) return true;
  return false;
}

void printList(Node* node) {
  while (node != NULL) {
    cout << node->data << " ";
    node = node->next;
  }
}

int main() {
  Node* list = NULL;
  if (isEmpty(&list))
    cout << "List is Empty" << endl;
  else {
    cout << "List is not empty! List contains:"
         << " ";
    printList(list);
  }
  // Inserting some elements in the list
  push(&list, 8);
  push(&list, 4);

  if (isEmpty(&list))
    cout << "The List is Empty" << endl;
  else {
    cout << "The list is not empty! The list contains:"
         << " ";
    printList(list);
  }
  return 0;
}

Output:

The List is Empty
The list is not empty! The list contains: 4 8

A linked list is only properly terminated when its next pointer of a node is set to NULL. If the head pointer of the linked list is set to NULL, then it’ll be called a zero-length linked list, and a zero-length linked list is also an empty list because it represents a NULL lead pointer.

Use Root Points to Check if Linked List Is Empty in C++

You can link the last element of a linked list to the root to form a cycle so that it can help identify the empty linked list. Utilizing root points comes with various benefits, including never having NULL as the next element; hence, programmers are no longer required to check for it.

It offers some unique cases, like if a linked list’s root or head points link back to itself, it represents an empty linked list. If if (root->next == root) { /* empty list */ } is true, then a linked list is empty.

Pseudo Code:

node *root;

... // process code (exp.)

if (root -> next == root) { /* empty list */ }

// check the head pointer - if it is NULL, there's no entry in the list.

int isEmpty( node * list )
 {
   if( !list )

      return 1;

   return 0; // otherwise in case false check
 }

Your data could be neutralized or zeroed out if you create a variable or assign it some garbage value in C++. You must learn to initialize your variable explicitly, assign them unique values, and learn the rules governing it.