Linked List in c++ | Scaler Topics (2023)

Overview

A Linked List is a linear dynamic data structure in which every element is linked to another element using pointers, sequentially. There are three types of linked lists in C++:

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

Scope of Article

  • In this article, we will learn about the Linked List data structure in C++.
  • All the types of linked lists will be explained in depth using diagrams in this article.
  • We will discuss all the operations of singly and doubly linked lists thoroughly with examples.
  • The advantages and disadvantages of linked lists will be discussed in this article.

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.

Linked List in c++ | Scaler Topics (1)

Flow Diagram

We will now depict the working of a Linked List using a Flow Diagram; this will help us visualize a Linked list.

Linked List in c++ | Scaler Topics (2)

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

Now we will check if Head is equal to 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++

#include <iostream>using std::cin;using std::cout;// Structure of the node of a singly linked listtypedef struct node{ int data; node* next;}node;// Function prototypesnode *Create(int value);node *InsertAtBeg(node *head, int value);node *InsertAtPos(node *head, int value, int position);node *InsertAtEnd(node *head, int value);node *DeleteAtBeg(node *head);node *DeleteAtPos(node *head, int position);node *DeleteAtEnd(node *head);node *Concatenate(node *head1, node *head2);int Search(node *head, int element);void Traverse(node *head);int main(){ node *head1 = new node; // Creating a head node of value 81 head1 = Create(81); // Inserting a node of value 2 at the end head1 = InsertAtEnd(head1, 2);  // Inserting a node of value 53 at the beginning head1 = InsertAtBeg(head1, 53); // Inserting a node of value 44 at the 2nd position head1 = InsertAtPos(head1, 44, 2); // Printing the first linked list cout<<"FIRST: "; Traverse(head1); cout<<"\n"; node *head2 = new node; // Creating a head node of value 91 head2 = Create(91); // Inserting a node of value 23 at the end head2 = InsertAtEnd(head2, 23); // Inserting a node of value -4 at the end head2 = InsertAtEnd(head2, -4); // Printing the second linked list cout << "SECOND: "; Traverse(head1); cout<<"\n"; // Concatenating first and second linked list head1 = Concatenate(head1, head2); // Printing the concatenated linked list cout << "CONCATENATED: "; Traverse(head1); return 0;}// Function to create the head node (first node) of a singly linked listnode *Create(int value){ node *ptr = new node; ptr->data = value; ptr->next = NULL; return ptr;}// Function to insert a new node at the beginning of a singly linked listnode *InsertAtBeg(node *head, int value){ node *ptr = new node; ptr->data = value; ptr->next = head; head = ptr; return head;}// Function to insert a new node at the specified position of a singly linked listnode *InsertAtPos(node *head, int value, int position){ if(position < 1) { cout<<"Invalid Position"; return head; }  if(position == 1) return InsertAtBeg(head, value); node *ptr1 = new node; ptr1 = head; node *ptr2 = new node; ptr2->data = value; ptr2->next = NULL; while(--position > 1) ptr1 = ptr1->next; ptr2->next = ptr1->next; ptr1->next = ptr2; return head;}// Function to insert a new node at the end of a singly linked listnode *InsertAtEnd(node *head, int value){ node *ptr1 = new node; ptr1 = head; while(ptr1->next != NULL) { ptr1 = ptr1->next; } node *ptr2 = new node; ptr2->data = value; ptr2->next = NULL; ptr1->next = ptr2; return head;}// Function to delete a node from the beginning of a singly linked listnode *DeleteAtBeg(node *head){ if(head == NULL) { cout<<"Underflow! Can't delete from empty list"; return head; } node* ptr = new node; ptr = head; head = head->next; delete ptr; return head;}// Function to delete a node from the specified position of a singly linked listnode *DeleteAtPos(node *head, int position){ if(head == NULL) { cout << "Underflow! Can't delete from empty list"; return head; } if(position < 1) { cout << "Invalid Position"; return head; } if(position == 1) return DeleteAtBeg(head);  node *ptr1 = new node; ptr1 = head; position--; while(position > 1) { ptr1 = ptr1->next; position--; } node *ptr2 = new node; ptr2 = ptr1->next; ptr1->next = ptr2->next; delete ptr2; return head;}// Function to delete a node from the end of a singly linked listnode *DeleteAtEnd(node *head){ if(head == NULL) { cout << "Underflow! Can't delete from empty list"; return head; } if(head->next == NULL) { delete head; return NULL; } node *ptr1 = new node; ptr1 = head; while(ptr1->next->next != NULL) ptr1 = ptr1->next; node *ptr2 = new node; ptr2 = ptr1->next; delete ptr2; ptr1->next = NULL; return head;}// Function to concatenate two singly linked listsnode *Concatenate(node *head1, node *head2){ node *ptr = new node; ptr = head1; while (ptr->next != NULL) { ptr = ptr->next; } ptr->next = head2; return head1;}// Function to search for an element in a singly linked listint Search(node *head, int element){ node *ptr = new node; ptr = head; int position = 0; while (ptr != NULL) { position++; if (ptr->data == element) return position; ptr = ptr->next; } return 0;}// Function to print a singly linked list from head node to tail nodevoid Traverse(node *head){ node *ptr = head; cout << "The linked list: "; while (ptr != NULL) { cout << ptr->data << " "; ptr = ptr->next; }}

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

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:

typedef struct node{ int data; node *next;}node;

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:

typedef struct node{ node* previous; int data; node *next;}node;

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

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

Types of Linked Lists in C++

Linked List in c++ | Scaler Topics (3)

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

Linked List in c++ | Scaler Topics (4)

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

Doubly linked list

Linked List in c++ | Scaler Topics (5)

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

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

Circular linked list

Linked List in c++ | Scaler Topics (6)

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 that its last node (TailTailTail) points to its first node (HeadHeadHead). 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.

Linked List in c++ | Scaler Topics (7)

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.

Linked List in c++ | Scaler Topics (8)

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

Linked List in c++ | Scaler Topics (9)

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

Linked List in c++ | Scaler Topics (10)

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.

Linked List in c++ | Scaler Topics (11)

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

Linked List in c++ | Scaler Topics (12)

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

Linked List in c++ | Scaler Topics (13)

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 also traverse from tail to head.

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 to be assigned to the data part of the node.

Algorithm:We will create a new node object named ptr, and the data part of this node, i.e., 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:

node *Create(int value){ // Creating the head node of a singly linked list node *ptr = new node; ptr->data = value; ptr->next = NULL; return ptr;}

This function creates the head node of a singly linked list.

Example:

node *head = new node;head = Create(24);// Linked List: 24

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 new node's value is to be inserted in the linked list.

Algorithm:At first, we will create a new node object named ptr and it's data part 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:

node *InsertAtBeg(node *head, int value){ // Inserting a new node at the beginning of a singly linked list node *ptr = new node; ptr->data = value; ptr->next = head; head = ptr; return head;}

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

Example:

node *head = new node;head = Create(2);// Linked List: 2head = InsertAtBeg(head, 33);// Linked List: 33 -> 2

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 new node's value is 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:

node *InsertAtPos(node *head, int value, int position){ // Inserting a new node at a specified position in a singly linked list if(position < 1) { cout<<"Invalid Position"; return head; }  if(position == 1) return InsertAtBeg(head, value); node *ptr1 = new node; ptr1 = head; node *ptr2 = new node; ptr2->data = value; ptr2->next = NULL; position--; while(position > 1) { ptr1 = ptr1->next; position--; } ptr2->next = ptr1->next; ptr1->next = ptr2; return head;}

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

Example:

node *head = new node;head = Create(81);head = InsertAtBeg(head, 19);// Linked List: 19 -> 81head = InsertAtPos(head, 22, 2);// Linked List: 19 -> 22 -> 81

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 new node's value is 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:

node *InsertAtEnd(node *head, int value){ // Inserting a new node at the end of a singly linked list node *ptr1 = new node; ptr1 = head; while(ptr1->next != NULL) { ptr1 = ptr1->next; } node *ptr2 = new node; ptr2->data = value; ptr2->next = NULL; ptr1->next = ptr2; return head;}

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

Example:

node *head = new node;head = Create(81);head = InsertAtBeg(head, 19);// Linked List: 19 -> 81head = InsertAtEnd(head, 1000)// Linked List: 19 -> 81 -> 1000

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

Delete At the Beginning of Operation

Deletes the first node of a singly linked list.

Parameters:It has a single parameter, head, 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 a head pointer. Now, we just have to assign the head pointer to be head->next and then delete the ptr node using the delete keyword to free space.

Implementation:

node *DeleteAtBeg(node *head){ // Deletes the first node of a singly linked list if(head == NULL) { cout<<"Underflow! Can't delete from empty list"; return head; } node* ptr = new node; ptr = head; head = head->next; delete ptr; return head;}

This function deletes the first node of a singly linked list.

Example:

node *head = new node;head = Create(81);head = InsertAtBeg(head, 19);head = InsertAtEnd(head, 1000);head = InsertAtEnd(head, 10);// Linked List: 19 -> 81 -> 1000 -> 10head = DeleteAtBeg(head);// Linked List: 81 -> 1000 -> 10

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 must 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:

node *DeleteAtPos(node *head, int position){ // Deletes a node from the specified position in a singly linked list if(head == NULL) { cout << "Underflow! Can't delete from empty list"; return head; } if(position < 1) { cout << "Invalid Position"; return head; } if(position == 1) return DeleteAtBeg(head);  node *ptr1 = new node; ptr1 = head; position--; while(position > 1) { ptr1 = ptr1->next; position--; } node *ptr2 = new node; ptr2 = ptr1->next; ptr1->next = ptr2->next; delete ptr2; return head;}

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

Example:

node *head = new node;head = Create(81);head = InsertAtBeg(head, 19);head = InsertAtEnd(head, 1000);head = InsertAtEnd(head, 10);// Linked List: 19 -> 81 -> 1000 -> 10head = DeleteAtPos(head, 2);// Linked List: 19 -> 1000 -> 10

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, 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:

node *DeleteAtEnd(node *head){ // Deletes the last node of a singly linked list if(head == NULL) { cout << "Underflow! Can't delete from empty list"; return head; } if(head->next == NULL) { delete head; return NULL; } node *ptr1 = new node; ptr1 = head; while(ptr1->next->next != NULL) ptr1 = ptr1->next; node *ptr2 = new node; ptr2 = ptr1->next; delete ptr2; ptr1->next = NULL; return head;}

This function deletes the last node of a singly linked list.

Example:

node *head = new node;head = Create(81);head = InsertAtBeg(head, 19);head = InsertAtEnd(head, 1000);head = InsertAtEnd(head, 10);// Linked List: 19 -> 81 -> 1000 -> 10head = DeleteAtEnd(head);// Linked List: 19 -> 81 -> 1000

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. Iter it through the linked list until ptr is not NULL. In each iteration, print ptr->data and move ptr one node forward.

Implementation:

void Traverse(node *head){ // Prints all the elements of a singly linked list node *ptr = new node; ptr = head; cout<<"The linked list: "; while (ptr != NULL) { cout<<ptr->data<<" "; ptr = ptr->next; }}

This function prints a singly linked list from the head node to the tail node.

Example:

node *head = new node;head = Create(81);head = InsertAtBeg(head, 19);head = InsertAtEnd(head, 1000);head = InsertAtEnd(head, 10);Traverse(head);// Output: // Linked List: 19 81 1000 10

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 created node object ptr to be head. Iterate it through the linked list, moving one node till ptr->data is equal to an element or ptr is NULL. If the element is not found, return 0.

Implementation:

int Search(node *head, int element){ // Searches for an element in a singly linked list node *ptr = new node; ptr = head; int position = 0; while (ptr != NULL) { position++; if (ptr->data == element) return position; ptr = ptr->next; } return 0;}

This function searches 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:

node *head = new node;head = Create(81);head = InsertAtBeg(head, 19);head = InsertAtEnd(head, 1000);head = InsertAtEnd(head, 10); // Linked List: 19 -> 81 -> 1000 -> 10int position = Search(head, 1000);if(position)  cout<<"The position of 1000 in linked list: "<<position;else  cout<<"1000 is not present in the linked list.";// Output: // The position of 1000 in linked list: 3

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 is to be concatenated at the end of the first linked list.

Algorithm:Assign a newly created node object ptr to 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:

node *Concatenate(node *head1, node* head2){ // Concatenates two different singly linked lists node *ptr = new node; ptr = head1; while(ptr->next != NULL) ptr = ptr->next; ptr->next = head2; return head1;}

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

Example:

node *head1 = new node;head1 = Create(81);head1 = InsertAtEnd(head1, 2);head1 = InsertAtEnd(head1, 44); // First Linked List: 81 -> 2 -> 44node *head2 = new node;head2 = Create(91);head2 = InsertAtEnd(head2, 23);head2 = InsertAtEnd(head2, -4); // Second Linked List: 91 -> 23 -> -4head1 = Concatenate(head1, head2);Traverse(head1);// Output: // The linked list: 81 2 44 91 23 -4 

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

node *Create(int value){ // Creates the head node of a doubly linked list node *ptr = new node;  ptr->previous = NULL; ptr->data = value; ptr->next = NULL; return ptr;}

This function creates the head node of a doubly linked list.

Example:

node *head = new node;head = Create(43);// Linked List: 43

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 head of the linked list in which we have to insert a new node.
  2. value: The new node's value is 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:

node *InsertAtBeg(node *head, int value){  // Inserts a new node at the beginning of a doubly linked list node *ptr = new node; ptr->previous = NULL; ptr->data = value; ptr->next = head; head->previous = ptr; head = ptr; return head;}

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

Example:

node *head = new node;head = Create(-4);// Linked List: -4head = InsertAtBeg(head, 90);// Linked List: 90 <-> -4

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 new node's value 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:

node *InsertAtPos(node *head, int value, int position){ // Inserts a new node at a specified position in a doubly linked list if (position < 1) { cout << "Invalid Position"; return head; } if (position == 1) return InsertAtBeg(head, value); node *ptr1 = new node; ptr1 = head; node *ptr2 = new node; ptr2->previous = NULL; ptr2->data = value; ptr2->next = NULL; position--; while (position > 1) { ptr1 = ptr1->next; position--; } if(ptr1->next == NULL) { ptr2->previous = ptr1; ptr2->next = NULL; ptr1->next = ptr2; return head; } ptr2->previous = ptr1; ptr2->next = ptr1->next; ptr2->next->previous = ptr2; ptr1->next = ptr2; return head;}

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

Example:

node *head = new node;head = Create(32);head = InsertAtBeg(head, -9);// Linked List: -9 <-> 32head = InsertAtPos(head, 1000, 2);// Linked List: -9 <-> 1000 <-> 32

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 new node's value is 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:

node *InsertAtEnd(node *head, int value){ // Inserts a new node at the end of a doubly linked list. node *ptr1 = new node; ptr1 = head; node *ptr2 = new node; ptr2->previous = NULL; ptr2->data = value; ptr2->next = NULL; while (ptr1->next != NULL) ptr1 = ptr1->next; ptr1->next = ptr2; ptr2->previous = ptr1; return head;}

This function inserts a new node at the end of a doubly linked list.

Example:

node *head = new node;head = Create(2);head = InsertAtBeg(head, 1);// Linked List: 1 <-> 2head = InsertAtEnd(head, 333)// Linked List: 1 <-> 2 <-> 333

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

Delete At the Beginning of Operation

Deletes the first node of a doubly linked list.

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

Algorithm:We will start by 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:

node *DeleteAtBeg(node *head){ // Deletes the first node of a doubly linked list if (head == NULL) { cout << "Underflow! Can't delete from empty list"; return head; } node *ptr = new node; ptr = head; head = head->next; head->previous = NULL; delete ptr; return head;}

This function deletes the first node of a doubly linked list.

Example:

node *head = new node;head = Create(54);head = InsertAtBeg(head, 22);head = InsertAtEnd(head, 10);head = InsertAtEnd(head, 1);// Linked List: 22 <-> 54 <-> 10 <-> 1head = DeleteAtBeg(head);// Linked List: 54 <-> 10 <-> 1

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 must 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:

node *DeleteAtPos(node *head, int position){ // Deletes a node from a specified position of a doubly linked list if (head == NULL) { cout << "Underflow! Can't delete from empty list"; return head; } if (position < 1) { cout << "Invalid Position"; return head; } if (position == 1) return DeleteAtBeg(head); node *ptr1 = new node; ptr1 = head; position--; while (position > 1) { ptr1 = ptr1->next; position--; } node *ptr2 = new node; ptr2 = ptr1->next; if(ptr2->next == NULL) { ptr1->next = NULL; delete ptr2; return head; } ptr2->next->previous = ptr1; ptr1->next = ptr2->next; delete ptr2; return head;}

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

Example:

node *head = new node;head = Create(81);head = InsertAtBeg(head, 19);head = InsertAtEnd(head, 1000);head = InsertAtEnd(head, 10);// Linked List: 19 <-> 81 <-> 1000 <-> 10head = DeleteAtPos(head, 2);// Linked List: 19 <-> 1000 <-> 10

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, 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:

node *DeleteAtEnd(node *head){ // Deletes the last node of a doubly linked list if (head == NULL) { cout << "Underflow! Can't delete from empty list"; return head; } if (head->next == NULL) { delete head; return NULL; } node *ptr1 = new node; ptr1 = head; while (ptr1->next->next != NULL) ptr1 = ptr1->next; node *ptr2 = new node; ptr2 = ptr1->next; delete ptr2; ptr1->next = NULL; return head;}

This function deletes the last node of a doubly linked list.

Example:

node *head = new node;head = Create(81);head = InsertAtBeg(head, 19);head = InsertAtEnd(head, 1000);head = InsertAtEnd(head, 10);// Linked List: 19 <-> 81 <-> 1000 <-> 10head = DeleteAtEnd(head);// Linked List: 19 <-> 81 <-> 1000

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

Traverse Operation

Prints the value of each node from the head to the 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. Iter it through the linked list until ptr is not NULL. In each iteration, print ptr->data and move ptr one node forward.

Implementation:

void Traverse(node *head){ // Prints elements of a doubly linked list from head to tail node *ptr = new node; ptr = head; cout << "The linked list: "; while (ptr != NULL) { cout << ptr->data << " "; ptr = ptr->next; }}

This function prints a doubly linked list from the head node to the tail node.

Example:

node *head = new node;head = Create(1);head = InsertAtBeg(head, 19);head = InsertAtEnd(head, 1050);head = InsertAtEnd(head, 0);Traverse(head);

Output:

Linked List: 19 1 1050 0

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

Reverse Traverse Operation

Prints the value of each node from the tail to the 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 the tail to the head of the linked list, and in each iteration, print ptr->data and assign ptr to be ptr->previous.

Implementation:

void ReverseTraverse(node *head){ node *ptr = new node; ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } cout << "Reversed Linked List: "; while(ptr != NULL) { cout << ptr->data << " "; ptr = ptr->previous; }}

This function prints a doubly linked list from the tail node to the head node.

Example:

node *head = new node;head = Create(1);head = InsertAtBeg(head, 19);head = InsertAtEnd(head, 1050);head = InsertAtEnd(head, 0);ReverseTraverse(head);

Output:

 Reverse Linked List: 0 1050 1 19

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.

Algorithm:Assign a newly created 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:

int Search(node *head, int element){ // Searches for an element in a doubly linked list node *ptr = new node; ptr = head; int position = 0; while (ptr != NULL) { position++; if (ptr->data == element) return position; ptr = ptr->next; } return 0;}

This function searches for an element in a doubly linked list. It returns the element's position in the linked list and 0 if the element is not present in the linked list.

Example:

node *head = new node;head = Create(1);head = InsertAtBeg(head, 9);head = InsertAtEnd(head, 100);head = InsertAtEnd(head, 0);// Linked List: 9 <-> 1 <-> 100 <-> 0int position = Search(head, 1000);if(position)  cout<<"The position of 1000 in linked list: "<<position;else  cout<<"1000 is not present in the linked list.";

Output:

 1000 is not present in the linked list.

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 is to be concatenated at the end of the first linked list.

Algorithm:Assign a newly created node object ptr to 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:

node *Concatenate(node *head1, node *head2){ // Concatenates two different doubly linked lists node *ptr = new node; ptr = head1; while (ptr->next != NULL) ptr = ptr->next; ptr->next = head2; head2->previous = ptr; return head1;}

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

Example:

node *head1 = new node;head1 = Create(81);head1 = InsertAtEnd(head1, 2);head1 = InsertAtEnd(head1, 44); // First Linked List: 81 <-> 2 <-> 44node *head2 = new node;head2 = Create(91);head2 = InsertAtEnd(head2, 23);head2 = InsertAtEnd(head2, -4); // First Linked List: 91 <-> 23 <-> -4head1 = Concatenate(head1, head2);Traverse(head1);

Output:

The linked list: 81 2 44 91 23 -4 

The head1 and head2 linked lists are concatenated.

Advantages of Linked Lists in C++

Dynamic memory allocation :
A Linked List is a dynamic data structure; it can increase or decrease in size at runtime by allocating and deallocating memory. This means we don't need to specify the size of a linked list, as that is decided at runtime.

Fast insertion and deletion :We can delete or insert elements in a linked list more efficiently than in an array. In a linked list, we just have to update a node's next pointer to insert an element, whereas, in an array, we have to shift all the elements for every insertion and deletion.

No memory wastage :As a linked list is a dynamic data structure, its size increases or decreases at runtime as per the requirement, resulting in zero memory wastage. In the case of arrays, there is a lot of memory wastage; if we initialize an array of size 100 but store only 38 elements, the space of 62 elements gets wasted. There is no such problem in linked lists, as space is allocated at runtime.

Implements Stack and Queue :Data structures such as stacks and queues can be easily implemented using linked lists.

Disadvantages of Linked Lists

Inefficient memory usage :More memory is required to store the same number of elements in a linked list as compared to an array because, in a linked list, each node contains a next pointer which requires extra memory for itself. Each node contains the previous and next pointers in a doubly linked list, which take even more memory.

No random access :We cannot randomly access any node in a linked list as it does not support indexing` like an array. We will need to traverse all the nodes of a linked list that come before the required node to access it.

Problems with reverse traversing :Reverse traversing is very difficult in a linked list as we will need to reverse the linked list. We can overcome this problem by using a doubly linked list, but this solution comes with another problem:

Inefficient memory usage : as in a doubly linked list, each node contains two pointers requiring extra memory.

Conclusion

  • A linked list in C++ is a linear dynamic data structure.
  • The node of a singly or a circular linked list has two parts: data and the address of the next node.
  • The node of a doubly linked list has three parts: data, the address of the previous node, and the address of the next node.
  • In a singly linked list, we can only traverse from the head node to the tail node.
  • In a doubly linked list, we can traverse from the head node to the tail node and from the tail node to the head node.
  • The main advantage of a linked list is dynamic memory allocation due to no memory wastage.
  • The main disadvantage of a linked list is that we cannot access random nodes; we will have to traverse through the linked list to get to the required node.
Top Articles
Latest Posts
Article information

Author: Dong Thiel

Last Updated: 01/06/2023

Views: 6495

Rating: 4.9 / 5 (79 voted)

Reviews: 86% of readers found this page helpful

Author information

Name: Dong Thiel

Birthday: 2001-07-14

Address: 2865 Kasha Unions, West Corrinne, AK 05708-1071

Phone: +3512198379449

Job: Design Planner

Hobby: Graffiti, Foreign language learning, Gambling, Metalworking, Rowing, Sculling, Sewing

Introduction: My name is Dong Thiel, I am a brainy, happy, tasty, lively, splendid, talented, cooperative person who loves writing and wants to share my knowledge and understanding with you.