Linked List in C++

Introduction

A Linked List is a linear data structure that is a collection of objects, called nodes. Each node in a linked list consists of two parts, the first part contains the Data and the second part contains the Address of the next node in the Linked List. A Linked List is a dynamic data structure, i.e., memory is allocated at run time, and memory size can be changed at run time according to our requirements.

Linked List in C++ works using pointers, each node is connected to the next node using C++ pointers.

Flow Diagram

We will now depict the working of a Linked List by means of a Flow Diagram, this will help us in the visualization of a Linked list.

In the above flow diagram, we are first using the terminal Start, then we will input the values (data and address of the next node) of a new node. After that, we will set the new node as the head of the linked list.

Now we will check if $Head \neq NULL$ or not, if true, we will create the next node of the current node, and check the Head again, if it is false, then that will mean the Linked list is empty, and we will $Stop$.

Implementation of a Linked List in C++

This is the implementation of a singly linked list with all the operations. These operations will be discussed in detail further in the article.

Creating a node of a Linked List

To create a Linked list, we will first have to define its nodes. The nodes can be of different types, depending upon the type of linked list they are for.

Node of a singly linked list / circular linked list:

A singly linked list's node or a circular linked list's node has data and the address of the next node.

Node of a doubly linked list:

A doubly linked list's node has data and the address of the previous node and next node.

We have used a C++ structure to create the node. The data is of int type, the next pointer and the previous pointer are of struct node type as they will point to a node of struct node type.

Types of Linked Lists in C++

There are mainly three types of Linked Lists:

• Singly Linked Lists
• Doubly Linked Lists
• Circular Linked Lists

Let us discuss these in depth:

Singly linked list

A Singly Linked List is a unidirectional linked list, so we can traverse it in one direction only, i.e., from $Head$ (first) node to $Tail$ (last) node. Its node has two parts: $data$ and $next$ pointer (address of the next node).

Doubly linked list

A Doubly Linked List is a bidirectional linked list, so it can be traversed in both the directions (from $Head$ to $Tail$ and from $Tail$ to $Head$).

Its node has three parts: previous pointer (address of the previous node), data, and next pointer (address of the next node).

Circular linked list

A Circular Linked List is a unidirectional linked list, so it can be traversed in only one direction. It is the same as a Singly Linked List except for the fact that its last node ($Tail$) points to its first node ($Head$). The node of a Circular Linked List is identical to that of a Singly Linked List.

Operations of a Linked List

Creation

The Create operation is used to create the head node (first node) of a linked list.

After creating a linked list with a single node, we can use the insert operation to add more nodes to the linked list.

Insertion

The Insert operation is used to insert a new node at any location in the linked list.

There are three types of insert operations:

• Insert At Beginning: This operation inserts a node at the beginning of the linked list, making it the head node. The previous head node becomes the second node of the linked list.

• Insert At Position: This operation inserts a node at the position specified by the user.

• Insert At End: This operation inserts a node at the end of the linked list, making it the tail node.

Deletion

The Delete operation is used to delete a node at any location in the linked list.

There are three types of delete operations:

• Delete At Beginning: This operation deletes a node from the beginning of the linked list. The second node becomes the head node of the linked list.

• Delete At Position: This operation delete a node from the position specified by the user.

• Delete At End: This operation deletes a node from the end of the linked list, the second last node becomes the tail node.

Traversing

The Traverse operation is used to traverse through each node of a linked list while printing the value of the nodes from head to tail. In a doubly linked list, we can traverse from tail to head also.

Searching

The Search operation is used to find an element in a linked list. It traverses through each node of the linked list before the required element to find it.

Concatenation

The Concatenate operation is used to concatenate (join) two linked lists. The tail of the first linked list is pointed to the head of the second linked list, this results in a concatenated linked list.

Example 1 - Operations of a Singly Linked List

Create Operation

Creates the head node (first node) of a singly linked list.

Parameters:
It has a single parameter value which is to be assigned to the data part of the node.

Algorithm: We will create a new node object named ptr. ptr->data is assigned to be value and ptr->next to be NULL (as we are only creating the head node, the next pointer will be NULL). Lastly, we will return the ptr node.

Implementation:

This function is used to create the head node of a singly linked list.

Example:

A Head node is created with the value 24.

Insert At Beginning Operation

Inserts a new node at the beginning of a singly linked list.

Parameters:

1. head: The head of the linked list in which we have to insert a new node.
2. value: The value of the new node to be inserted in the linked list.

Algorithm: At first, we will create a new node object named ptr. ptr->data is assigned to be value and ptr->next to be head (as the node being inserted at the beginning is now the new head node). Then we will return the head node.

Implementation:

This function is used to insert a new node at the beginning of a singly linked list.

Example:

A new node of value 33 is inserted at the beginning of the linked list, and is now the head node.

Insert At Position Operation

Inserts a new node in a singly linked list at the position specified by the user.

Parameters:

1. head: The head of the linked list in which we have to insert a new node.
2. value: The value of the new node to be inserted in the linked list.
3. position: The position at which we have to insert the new node in the linked list.

Algorithm: At first we will create new node objects named ptr1 and ptr2. The ptr1 will be assigned head, ptr2->data will be value. Then we will iterate in the linked list till we reach the required position, at which we will insert the ptr2 node. The ptr1 node will be one node before the required position.

The ptr2->next will be assigned ptr1->next and ptr1->next will be assigned ptr2. Lastly, we will return the head node.

Implementation:

This function is used to insert a new node in a singly linked list at the position specified by the user.

Example:

A new node of value 22 is inserted at the 2nd position of the linked list.

Insert At End Operation

Inserts a new node at the end of a singly linked list.

Parameters:

1. head: The head of the linked list in which we have to insert a new node.
2. value: The value of the new node to be inserted in the linked list.

Algorithm: At first we will create new node objects named ptr1 and ptr2. The ptr1 node will be assigned to be head, ptr2->data will be value, and ptr2->next will be NULL.

Then we will iterate the linked list till ptr1 reaches the last node. ptr1->next will be assigned to be ptr2 (as ptr2 is now the last node). Lastly, return the head node.

Implementation:

This function is used to insert a new node at the end of a singly linked list.

Example:

A new node of value 1000 is inserted at the end of the linked list.

Delete At Beginning Operation

Deletes the first node of a singly linked list.

Parameters: It has a single parameter head, which is the head of the linked list whose first node is to be deleted.

Algorithm: At first, we will create a new node object named ptr and then assign it head pointer. Now, we just have to assign head pointer to be head->next and then delete the ptr node using the delete keyword to free space.

Implementation:

This function is used to delete the first node of a singly linked list.

Example:

The node of value 19 is deleted from the beginning of the linked list.

Delete At Position Operation

Deletes the node of a singly linked list from a position specified by the user.

Parameters:

1. head: The head of the linked list from which we have to delete a node.
2. position: The position from which the node is to be deleted.

Algorithm: At first, we will create two new node objects named ptr1 and ptr2. The ptr1 will be assigned the head pointer. We will now iterate through the nodes of the linked list such that ptr1 points at the node before the required position.

The ptr2 will be assigned ptr1->next and ptr1->next will be ptr2->next. Lastly, we will delete the ptr2 pointer and return the head pointer.

Implementation:

This function is used to delete a node from the user-specified position of a singly linked list.

Example:

The node of value 81 at position 2 is deleted from the linked list.

Delete At End Operation

Deletes the last node of a singly linked list.

Parameters: It has a single parameter head, which is the head of the linked list whose last node is to be deleted.

Algorithm: At first, we will create two new node objects named ptr1 and ptr2. The ptr1 pointer will be assigned head. Then we will iterate it through each node of the linked list till we reach its second last node. Now, the ptr2 pointer will be assigned ptr1->next.

The ptr2 pointer will be deleted using the delete keyword and ptr1->next will be assigned to be NULL. Lastly, the head pointer will be returned.

Implementation:

This function is used to delete the last node of a singly linked list.

Example:

The node of value 10 is deleted from the end of the linked list.

Traverse Operation

Prints the value of each node from head to tail of a singly linked list.

Parameters: It has a single parameter head, which is the head of the linked list to be traversed.

Algorithm: Assign a newly created node object ptr to be head. Iterate it through the linked list till ptr is not NULL. In each iteration, print ptr->data and move ptr one node forward.

Implementation:

This function is used to print a singly linked list from the head node to the tail node.

Example:

The linked list is printed from its head node to the tail node.

Search Operation

Searches for a value in a singly linked list.

Parameters:

1. head: The head node of the linked list in which we have to search for an element.
2. element: The element to search for in the linked list.

Algorithm: Assign a newly create node object ptr to be head. Iterate it through the linked list moving one node till ptr->data is equal to element or ptr is NULL. If the element is not found, return 0.

Implementation:

This function is used to search for an element in a singly linked list. It returns the position of the element in the linked list and 0 if the element is not present in the linked list.

Example:

The node of the value 1000 is at the 3rd position in the linked list.

Concatenate Operation

Concatenates two singly linked lists.

Parameters:

1. head1: The head node of the linked list to which we have to concatenate the second linked list.
2. head2: The head node of the linked list to be concatenated at the end of the first linked list.

Algorithm: Assign a newly created node object ptr to be head1. Iterate it through the linked list till it reaches the last node. Now, we just have to assign the ptr->next to be head2 and then return the head1 pointer.

Implementation:

This function is used to concatenate two singly linked lists. The tail node of the first linked list is pointed towards the head node of the second linked list.

Example:

The head1 and head2 linked lists are concatenated.

Example 2 - Operations of a Doubly-Linked List

Create Operation

Creates the head node (first node) of a doubly linked list.

Parameters: It has a single parameter value which is to be assigned to the data part of the node.

Algorithm:

We will create a new node object named ptr. ptr->previous is assigned to be NULL, ptr->data to be value and ptr->next to be NULL (as we are only creating the head node, the previous and next pointer will be NULL). Lastly, we will return the ptr node.

Implementation:

This function is used to create the head node of a doubly linked list.

Example:

A Head node is created with the value 24.

Insert At Beginning Operation

Inserts a new node at the beginning of a doubly linked list.

Parameters:

1. head: The hea of the linked list in which we have to insert a new node.
2. value: The value of the new node to be inserted in the linked list.

Algorithm: At first, we will create a new node object named ptr. ptr->previous is assigned to be NULL, ptr->data to be value and ptr->next to be head (as the node being inserted at the beginning is now the new head node).

Now, we will assign head->previous to be ptr and head to be ptr. Lastly, we will return the head node.

Implementation:

This function is used to insert a new node at the beginning of a doubly linked list.

Example:

A new node of value 90 is inserted at the beginning of the linked list, and is now the head node.

Insert At Position Operation

Inserts a new node in a doubly linked list at the position specified by the user.

Parameters:

1. head: The head of the linked list in which we have to insert a new node.
2. value: The value of the new node to be inserted in the linked list.
3. position: The position at which we have to insert the new node in the linked list.

Algorithm: At first we will create new node objects named ptr1 and ptr2. The ptr1 will be assigned head, ptr2->previous will be ptr1, and ptr2->data will be value.

Then we will iterate in the linked list till we reach the required position, at which we will insert the ptr2 node. The ptr1 node will be one node before the required position.

The ptr2->next will be assigned ptr1->next, ptr2->next->previous will be ptr2, and ptr1->next will be ptr2.

Lastly, we will return the head node.

Implementation:

This function is used to insert a new node in a doubly linked list at a position specified by the user.

Example:

A new node of value 1000 is inserted at the 2nd position of the linked list.

Insert At End Operation

Inserts a new node at the end of a doubly linked list.

Parameters:

1. head: The head of the linked list in which we have to insert a new node.
2. value: The value of the new node to be inserted in the linked list.

Algorithm: At first we will create two new node objects named ptr1 and ptr2. The ptr1 will be assigned head, ptr2->previous will be ptr1, ptr2->data will be value, and ptr2->next will be NULL. Then we will iterate ptr1 in the linked list till we reach the last node. After that, we will assign ptr1->next to be ptr2 and ptr2->previous to be ptr1.

Lastly, we will return the head node.

Implementation:

This function is used to insert a new node at the end of a doubly linked list.

Example:

A new node of value 333 is inserted at the end of the linked list.

Delete At Beginning Operation

Deletes the first node of a doubly linked list.

Parameters: It has a single parameter head, which is the head of the linked list whose first node is to be deleted.

Algorithm: We will start be assigning a newly created node object ptr to be head. The head pointer will be assigned head->next (as the second node is now the new head) and head->previous will be NULL.

Lastly, we will delete the ptr using the delete keyword and then return the head pointer.

Implementation:

This function is used to delete the first node of a doubly linked list.

Example:

The node of value 22 is deleted from the beginning of the linked list.

Delete At Position Operation

Deletes the node of a doubly linked list from a position specified by the user.

Parameters:

1. head: The head of the linked list from which we have to delete a node.
2. position: The position from which the node is to be deleted.

Algorithm: At first, we will create two new node objects named ptr1 and ptr2. We will iterate the linked list such that ptr1 points at the node before the specified position. ptr2 will be assigned to be ptr1->next, ptr2->next->previous to be ptr1, and ptr1->next will be ptr2->next.

Lastly, we will delete ptr2 using the delete keyword and then return the head pointer.

Implementation:

This function is used to delete a node from a user-specified position of a doubly linked list.

Example:

The node of value 81 at position 2 is deleted from the linked list.

Delete At End Operation

Deletes the last node of a doubly linked list.

Parameters: It has a single parameter head, which is the head of the linked list whose last node is to be deleted.

Algorithm: At first, we will create two new node objects ptr1 and ptr2. ptr1 will be assigned head. We will then iterate it in the linked list until ptr1 reaches the second last node. After this, ptr2 will be assigned to be ptr1->next and then will be deleted using the delete keyword.

At last, ptr1->next will be assigned NULL and we will return the head pointer.

Implementation:

This function is used to delete the last node of a doubly linked list.

Example:

The node of value 10 is deleted from the end of the linked list.

Traverse Operation

Prints the value of each node from head to tail of a doubly linked list.

Parameters: It has a single parameter head, which is the head of the linked list to be traversed.

Algorithm: Assign a newly created node object ptr to be head. Iterate it through the linked list till ptr is not NULL. In each iteration, print ptr->data and move ptr one node forward.

Implementation:

This function is used to print a doubly linked list from the head node to the tail node.

Example:

The linked list is printed from its head node to the tail node.

ReverseTraverse Operation

Prints the value of each node from tail to head of a doubly linked list.

Parameters: It has a single parameter head, which is the head of the linked list to be traversed.

Algorithm: Assign a newly created node object ptr to be head. Iterate it through the linked list till ptr->next till ptr is at the last node (tail) of the linked list.

Now, iterate ptr from tail to head of the linked list and in each iteration, print ptr->data and assign ptr to be ptr->previous.

Implementation:

This function is used to print a doubly linked list from the tail node to the head node.

Example:

The linked list is printed from its tail node to the head node.

Search Operation

Searches for a value in a doubly linked list.

Parameters:

1. head: The head node of the linked list in which we have to search for an element.
2. element: The element to search for in the linked list.

Alogrithm: Assign a newly create node object ptr to be head. Iterate it through the linked list moving one node till ptr->data is equal to element or ptr is NULL. If the element is not found, return 0.

Implementation:

This function is used to search for an element in a doubly linked list. It returns the position of the element in the linked list and 0 if the element is not present in the linked list.

Example:

There is no node of the value 1000 in the linked list.

Concatenate Operation

Concatenates two doubly linked lists.

Parameters:

1. head1: The head node of the linked list in which we have to concatenate the second linked list.
2. head2: The head node of the linked list to be concatenated at the end of the first linked list.

Algorithm: Assign a newly created node object ptr to be head1. Iterate it through the linked list till it reaches the last node. Now, assign the ptr->next to be head2 and head2->previous to be ptr. At last, return the head1 pointer.

Implementation:

This function is used to concatenate two doubly linked lists. The tail node of the first linked list is pointed towards the head node of the second linked list.

Example:

The head1 and head2 linked lists are concatenated.

Advantages of Linked Lists in C++

1. Linked Lists are dynamic data structures, adjusting in size as needed at runtime for efficient memory allocation.
2. They excel at quick insertions and deletions by simply updating node pointers, unlike arrays which require shifting elements.
3. Linked Lists minimize memory wastage, unlike arrays where unused space can be considerable.
4. Linked Lists are suitable for implementing stacks and queues due to their flexibility.

Disadvantages of Linked Lists

1. Linked lists require more memory than arrays due to the additional memory needed for each node's next pointer, which is compounded in doubly linked lists with previous and next pointers.
2. Linked lists don't support random access, necessitating traversal of preceding nodes to access a specific node.
3. Reverse traversing in a linked list is challenging and is addressed by using a doubly linked list, albeit this introduces inefficient memory usage with two additional pointers per node.

Related Topics

• Application of Linked Lists
• Data Structures in C++