Check if Linked List is Empty

Linked list is a linear data structure used to store elements of similar data type.
Each node in a list consists of at least two parts:

  1. data value
  2. pointer to the next node

Linked list can be formed in two ways:

  • with a root element
  • without a root

Checking if the given Linked List is empty depends on the ways Linked List has been formed. We have covered both approaches.

With a root

The root acts as an element which is always present even if the list is empty.
The other use of having a root in list is that we can link the last element back to the root forming a cycle. According to this concept, next of any node is never NULL.

rootimg

Pseudocode:

bool isEmpty(node *root){
    if (root->next == root) return true;
    else return false;
}

The implementation is given below:

#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:
hihff

without root

Without a root, the list pointer is NULL when the list is empty.
Pseudocode:

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

Implementation of Linked List without root is given below:

#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 list
	push(&list,8);
	push(&list,4);
	
	if(isEmpty(&list)) cout<<"List is Empty"<<endl;
	else{
		cout<<"List is not empty! List contains:"<<" ";
		printList(list);
	}
	return 0;
}

Output:
og2.1

Complexity:
The complexity to check whether the list is empty or not in both the approaches is same i.e O(1)