Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

A linked list is a type of linear data structure that uses nodes to store the data.

Each node in a linked list is a structure-defined data type that consists of data and a pointer referencing the address of the next node.

What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are connected through pointers. Each node contains data and a reference to the next node, forming a sequence. Unlike arrays, linked lists do not require contiguous memory allocation, allowing dynamic memory management and efficient insertion and deletion operations.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Representation of Linked Lists

A linked list is a collection of “nodes” connected together via links. These nodes consist of the data to be stored and a pointer to the address of the next node within the linked list. In the case of arrays, the size is limited to the definition, but in linked lists, there is no defined size. Any amount of data can be stored in it and can be deleted from it.

The first node in a linked list is referred to as the head, while the last node frequently links to null to denote the end of the list. Each link contains a data field or fields as well as a link field named next. Every link is connected to the next link using the next link.

Syntax:

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

The syntax above represents a single node in a linked list. The next pointer connects the next node, forming a lengthy chain known as a linked list.

Why do we need linked lists?

It offers some amazing features and thus it is of great use, some of the advantages of it include:

Dynamic Size: It offers the flexibility to extend the size at runtime and thus we need to worry about the size of data elements beforehand.

Ease of Deletion/Insertion: It offers a good and economical way of insertion and deletion of data elements as this insertion and deletion can be costly with the use of arrays.

Operations in the Linked Lists

There are several operations which were performed on the Linked Lists

Traversal - To traverse throughout the linked list.

Insertion - Insertion of a node at any position.

Deletion - Deletion of a node from any position.

Updation - Updation of data of a node.

Sort - Sorting the node members

We will cover each one of these operations on linked lists in C/C++ one by one in detail. So, fasten your seat belts.

1. Traversal Operation

Traversal is one of the basic operations on linked lists in C/C++ in which we traverse throughout the linked list from beginning to the end or from head to tail.

Traversal can be used to print the nodes of the linked list, to reach out for a required node in a list.

Let us take the example of printing the nodes of the linked list through traversal operation.

Algorithm :

First, initialize a Node variable, say ‘temp’ pointing to the head of the linked list.

Of the operations on linked lists in C/C++, insertion is used to insert a node at a particular position. The positions can be:

At the beginning of the linked list.

At the end of the linked list.

After after a particular node.

Insertion at the Beginning - In this case we need not to traverse the linked list. We will check if the list is empty then we will make the new node as head. Otherwise, we have to connect the head of the list with the new node by making the next pointer of the node pointing to the head and then making the new node as head of the list.

Source : codeforwin

Node* insertAtBegin(Node* head, int x)
{
// creation of a new node of linked list.
Node* newNode = new Node(x)
// checking if the linked list is empty.
if(head == NULL)
return newNode;
// insertion of the node at the beginning.
else
{
newNode->next = head;
return newNode;
}
}

Insertion at the end - In this case we have to traverse throughout the linked list until we will find the last node and then we will insert the required node in the list.

For this, we have to consider some special cases. For eg. if the list is empty then we will just create the new node and make it as head. In this case the new node will be the first and the last node of the list.

Source: AfterAcademy

Node* insertAtEnd(Node* head, int x)
{
// If the list is empty.
if( head == NULL )
{
Node* newNode = new Node(x);
head = newNode;
return head;
}
Node* temp = head;
// Traversing the list till the last node
while(temp->next != NULL)
{
temp = temp->next;
}
Node* newNode = new Node(x);
temp->next = newNode;
return head;
}

Insertion after a particular node -

In this case a reference to a particular node will be given. Then a new node will be inserted after that.

If the reference of the node is not given instead data of the node is given, then we have to traverse to the given node matching the given data and then we will insert the new node after that node.

Source: AfterAcademy

void insertAfterNode(Node* givenNode, int x)
{
Node* newNode = new Node(x);
newNode->next = givenNode->next;
givenNode->next = newNode;
}

3. Deletion Operation

This is one type of the operations on linked lists in C/C++, in which we just need to follow the following steps:

Traversing to the previous node of the node to be deleted.

Changing the next pointer of that previous node to point to the address of the next node of the node to be deleted.

Freeing up the memory which is occupied by the node to be deleted.

Source : AfterAcademy

Node deleteNode(Node* head, Node* toBeDeleted)
{
// If the node to be deleted is the head node.
if(head == toBeDeleted)
{
return head.next;
}
// temp is the traversing node.
Node* temp = head;
while( temp->next != NULL )
{
// Searching for the previous node of the node to be deleted.
if(temp->next == toBeDeleted)
{
temp->next = temp->next->next;
// Freeing up the memory of the node to be deleted.
return head;
}
temp = temp->next;
}
// If no node matches in the Linked List.
return head;
}

4. Updation Operation

This kind is one of the operations on linked lists in C/C++, in which we have to replace the data part of the required node with the given value.

For this, we will be traversing throughout the linked list until we find a node that will be matching to the required node to be updated.

void updateNode(Node* head, int value, int newValue)
{
// temp is the traversing node
Node* temp = head;
while(temp != NULL)
{
// If the node matches the given node to be updated.
if( temp->data == val)
{
// Updating the data part of the node with the new value.
temp->data = newVal;
return;
}
temp = temp->next;
}
}

5. Sort Operation

This operation sorts the nodes present in a linked list. You can use various sorting algorithms for linked lists but merge sort is one of the most performant. Let's see the implementation of Merge sort for singly linked lists in C++:-

The sortList() function accepts the Linked List head pointer and returns the head pointer after sorting it recursively. At each step, the middle node is found, and the left and right halves are sorted independently, and then they are merged using the mergeLists() helper function.

Types of Linked Lists

There are three types of linked lists that have their own unique ways of implementation. They are namely:

Singly Linked List is the collection of nodes which consist of data and the pointer part which will be pointing to the address of the next node.

The structure of the node of Singly Linked List be like:

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

The nodes are connected with the help of the next pointer which is pointing towards the address of the next node. If the next node is not present or the current node is the last node of the Linked List then the next pointer will be pointing to NULL.

Doubly Linked Lists

Doubly Linked List is the collection of nodes which consists of data and two pointers one of which will be pointing to the previous node’s address and another will be pointing to the next node’s address.

The structure of the node of Singly Linked List be like:

Struct Node
{
int data;
Node* next;
Node* prev;
};

The nodes are connected with the help of the next pointer which is pointing towards the address of the next node and the prev pointer which is pointing towards the address of the previous node. If the next node is not present or the current node is the last node of the Linked List then the next pointer will be pointing to NULL. And in the other case if the previous node is not present or the current node is the first node of the linked list then the prev pointer will be pointing to NULL.

Circular Linked Lists

Circular Linked List is the collection of nodes which consists of data and a pointer which will be pointing to the next node’s address.

The Last node’s next pointer will be pointing to the first node of the Circular Linked List.

Source: AlphaCodingSkills

Now let us jump to the basic operations performed on a linked list.

Advantages of Linked List

Linked Lists are dynamic in nature, which means they can allocate memory when required.

Insertion and deletion in Linked Lists can be on both sides, i.e., either from the head part or from the tail part.

Linked Lists reduce access time.

Applications of Linked List

Linked Lists can be used to implement queues, stacks, and graphs.

Forward and backward button in the toolbar for navigation uses doubly linked lists.

The four types of linked lists are Singly Linked List, Doubly Linked List, Circular Linked List, and Doubly Circular Linked List. Each has unique properties and advantages for different applications.

Which of the following are linked list operations?

Linked list operations include insertion, deletion, traversal, searching, and updating nodes. These operations are essential for manipulating the elements within the linked list efficiently.

What are the operations of queue?

Queue operations involve enqueue (adding elements to the rear), dequeue (removing elements from the front), peek (viewing the front element without removing), and isEmpty (checking if the queue is empty).

What are the various operations on stack using linked list?

Stack operations using linked list include push (adding elements to the top), pop (removing elements from the top), peek (viewing the top element without removing), and isEmpty (checking if the stack is empty). These operations follow the Last In, First Out (LIFO) principle.

Conclusion

This article covered the types of linked lists and various operations on linked lists in C/C++. If you want to learn more about linked lists and want to practice some questions which require you to take your basic knowledge on operations on linked lists in C/C++, a notch higher, then you can visit our Guided Path for Linked List.