Singly Linked Lists in C++

In this tutorial, we will learn everything about Singly Linked Lists in C++.
We will learn the following –

  • What are Singly Linked lists?
  • How are they created?
  • Different operations
  • Advantages of Linked lists

What are Singly Linked lists?

A linked list is a data structure, in which the elements are not stored at contiguous memory locations, unlike arrays. A linked list is made up of nodes where each node contains a data element and a reference(pointer) to the next element. Only the access to the first node of the list is needed, and enough, to access the whole list elements. And this first node of the list is known as the head. The last node in the list points to nothing and therefore, it points to NULL.

How to create a singly linked list in C++

How is a node created?
So, a node is nothing but a container which contains a data element and a reference. A reference is of type Node pointer as it points to another node of the same type.

struct Node
{
    int data;
    struct Node* next;
};

This defines a Node of the singly linked list.

Different operations of singly Linked Lists in C++

There are a number of operations that can be performed on a linked list. They are – Insertion, Deletion, Display.

Insertion – To insert an element in the beginning, we first need to create a new node and then point the reference of the new pointer to the older node and then make the new node as the head.

The following code shows how it’s done –

void insert(int data) 
{ 
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); 
   new_node->data = data; 
   new_node->next = head; 
   head = new_node; 
}

Deletion – To delete the first element in the list, we just have to point the second element as the head and then point the first element to NULL.

The following code shows how it’s done –

void delete() 
{ 
   struct Node* temp = head;
   head = head->next;
   temp->next = NULL;
   free(temp);
}

Display – Also called as traversal. To traverse the list, we first take a temporary pointer which points to the head. And this pointer is forwarded until all the nodes of the list are printed(that it, until NULL is reached).

The following code shows how it’s done –

void display() 
{ 
   struct Node* temp = head;
   while (temp != NULL) 
   { 
      cout<< temp->data <<" "; 
      temp = temp->next; 
   } 
}

Advantages of Linked lists

  1. Dynamic size – The size of the linked list can be infinite, that is , as much as the CPU can allocate for a process. As linked lists can grow or shrink in size, the size of the linked list keeps on changing with every insertion/deletion.
  2. Ease of insertion and deletion – Insertion and deletion can be done effortlessly. As all the elements are pointed to one other, this makes it easy for the user to delete/insert an element from the list. The main advantage under this point is that insertion and deletion can be done on any element, which is present wherever in the list.

Read more articles –

Leave a Reply

Your email address will not be published. Required fields are marked *