Linked List in C++

In C++, a linked list is a linear data structure that allows the users to store data in non-contiguous memory locations. A linked list is defined as a collection of nodes where each node consists of two members which represents its value and a next pointer which stores the address for the next node. In this article, we will learn about the linked list, its implementation, and its practical applications.

Types of Linked Lists

Following are the types of linked lists in C++:

1. Singly Linked List

The singly linked list is the simplest form of linked list in which the node contain two members data and a next pointer that stores the address of the next node. Each node is a singly linked list is connected through the next pointer and the next pointer of the last node points to NULL denoting the end of the linked list. The following diagram describes the structure of a singly linked list:

Structure of a singly linked list

2. Doubly Linked List

The doubly linked list is the modified version of the singly linked list where each node of the doubly linked consists of three data members data ,next and prev. The prev is a pointer that stores the address of the previous node in the linked list sequence. Each node in a doubly linked list except the first and the last node is connected with each other through the prev and next pointer. The prev pointer of the first node and the next pointer of the last node points to NULL in the doubly linked list. The following diagram describes the structure of a doubly linked list:

Structure of a Doubly linked list

3. Circular Linked List

The circular linked list is almost same as the singly linked list but with a small change. In a circular linked list the next pointer of the last node points to the first node of the linked list rather than pointing to NULL, this makes this data structure circular in nature which is used in various applications like media players. The following diagram describes the structure of a circular linked list:

Structure of a Circular linked list

4. Doubly Circular Linked List

The doubly circular linked list is a combination of a doubly linked list and a circular linked list. In a doubly circular linked list the prev pointer of the first node points to the last node and the next pointer of the last node points to the first node. The main advantage of a doubly circular linked list is that we can access the last node of the linked list in constant time through the first node. The following diagram describes the structure of a doubly circular linked list:

Structure of a doubly circular linked list

Implementation of Linked List in C++

To implement a linked list in C++ we can follow the below approach:

Approach:

• Define a structure Node having two members data and a next pointer. The data will store the value of the node and the next pointer will store the address of the next node in the sequence. For doubly linked list you will have to add an addition pointer prev that will store the address of the prev node in the sequence.
• Define a class LinkedList consisting of all the member functions for the LinkedList and a head pointer that will store the reference of a particular linked list.
• Initialize the head to NULL as the linked list is empty initially.
• Implement basic functions like insertAtBeginning, insertAtEnd, deleteFromBeginning, deleteFromEnd that will manipulate the elements of the linked list.

Representation of a Node in the Linked List

Each node of the linked list will be represented as a structure having two members data and next where:

• Data: Represents the value stored in the node.
• Next Pointer: Stores the reference to the next node in the sequence.

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

Note: Add another data member Node * prev in the structure for doubly linked lists.

Basic Operations of a Linked List

Following are some basic operations which are required to manipulate the nodes of a linked list:

Note: Here n denotes the number of nodes in the linked list.

Now let’s learn how we can implement these basic functions of linked list in C++:

Algorithm for insertAtBeginning Implementation

1. Create a new Node
2. Point the new Node’s next pointer to the current head.
3. Update the head of the linked list as the new node.

Inserting a node at the first of the linked list

Algorithm for insertAtEnd Implementation

1. Create a new Node
2. If the linked list is empty, update the head as the new node.
3. Otherwise traverse till the last node of the linked list.
4. Update the next pointer of the last node from NULL to new node.

Inserting a node at the end of the linked list

Algorithm for insertAtPosition Implementation

1. Check if the provided position by the user is a valid poistion.
2. Create a new node.
3. Find the node at position -1.
4. Update the next pointer of the new node to the next pointer of the current node.
5. Update the next pointer of the current node to new node.

Inserting a node after the second position in the linked list

Algorithm for deleteFromBeginning Implementation

1. Check whether the Head of the linked list is not NULL. If Head is equal to NULL return as the linked list is empty, there is no node present for deletion.
2. Store the head of the linked list in a temp pointer.
3. Update the head of the linked list to next node.
4. Delete the temporary node stored in the temp pointer.

Deleting the first node of the linked list

Algorithm for deleteFromEnd Implementation

1. Verify whether the linked is empty or not before deletion.
2. If the linked list has only one node, delete head and set head to NULL.
3. Traverse till the second last node of the linked list.
4. Store the last node of the linked list in a temp pointer.
5. Pointer the next pointer of the second last node to NULL.
6. Delete the node represented by the temp pointer.

Deleting the last node of the linked list

Algorithm for deleteFromPosition Implementation

1. Check if the provided postion by the users is a valid position in the linked list or not.
2. Find the node at position -1.
3. Save node to be deleted in a temp pointer.
4. Set the next pointer of the current node to the next pointer of the node to be deleted.
5. Set the next pointer of temp to NULL.
6. Delete the node represented by temp pointer.

Deleting the node present at the second position in the linked list

Algorithm for Display Implementation

1. Check if the Head pointer of the linked list is not equal to NULL.
2. Set a temp pointer to the Head of the linked list.
3. Until temp becomes null:
   1. Print temp->data
   2. Move temp to the next node.

C++ Program for Implementation of Linked List

The following program illustrates how we can implement a singly linked list data structure in C++:

// C++ Program for Implementation of linked list
#include <iostream>
using namespace std;

// Structure for a node in the linked list
struct Node {
    int data;  
    Node* next; 
};

// Define the linked list class
class LinkedList {
     // Pointer to the first node in the list
    Node* head;

public:
    // Constructor initializes head to NULL
    LinkedList() : head(NULL) {}

    // Function to Insert a new node at the beginning of the list
    void insertAtBeginning(int value) {
        Node* newNode = new Node(); 
        newNode->data = value;      
        newNode->next = head;      
        head = newNode;            
    }

    // Function Insert a new node at the end of the list
    void insertAtEnd(int value) {
        Node* newNode = new Node(); 
        newNode->data = value;      
        newNode->next = NULL;       

        // If the list is empty, update the head to the new node
        if (!head) {
            head = newNode;
            return;
        }

        // Traverse to the last node
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }

        // Update the last node's next to the new node
        temp->next = newNode;
    }

    // Function to Insert a new node at a specific position in the list
    void insertAtPosition(int value, int position) {
        if (position < 1) {
            cout << "Position should be >= 1." << endl;
            return;
        }

        if (position == 1) {
            insertAtBeginning(value);
            return;
        }

        Node* newNode = new Node(); 
        newNode->data = value;     

        // Traverse to the node before the desired position
        Node* temp = head;
        for (int i = 1; i < position - 1 && temp; ++i) {
            temp = temp->next;
        }

        // If the position is out of range, print an error message
        if (!temp) {
            cout << "Position out of range." << endl;
            delete newNode;
            return;
        }

        // Insert the new node at the desired position
        newNode->next = temp->next;
        temp->next = newNode;
    }

    // Function to Delete the first node of the list
    void deleteFromBeginning() {
        if (!head) {
            cout << "List is empty." << endl;
            return;
        }

        Node* temp = head; 
        head = head->next; 
        delete temp;      
    }

    // Function to Delete the last node of the list
    void deleteFromEnd() {
        if (!head) {
            cout << "List is empty." << endl;
            return;
        }

        if (!head->next) {
            delete head;   
            head = NULL;   
            return;
        }

        // Traverse to the second-to-last node
        Node* temp = head;
        while (temp->next->next) {
            temp = temp->next;
        }
        
        //  Delete the last node
        delete temp->next; 
        // Set the second-to-last node's next to NULL
        temp->next = NULL; 
    }

    // Function to Delete a node at a specific position in the list
    void deleteFromPosition(int position) {
        if (position < 1) {
            cout << "Position should be >= 1." << endl;
            return;
        }

        if (position == 1) {
            deleteFromBeginning();
            return;
        }

        Node* temp = head;
        for (int i = 1; i < position - 1 && temp; ++i) {
            temp = temp->next;
        }

        if (!temp || !temp->next) {
            cout << "Position out of range." << endl;
            return;
        }
        // Save the node to be deleted
        Node* nodeToDelete = temp->next; 
        // Update the next pointer
        temp->next = temp->next->next;   
         // Delete the node
        delete nodeToDelete;            
    }

    // Function to print the nodes of  the linked list
    void display() {
        if (!head) {
            cout << "List is empty." << endl;
            return;
        }

        Node* temp = head;
        while (temp) {
            cout << temp->data << " -> "; 
            temp = temp->next;
        }
        cout << "NULL" << endl; 
    }
};

int main() {
    // Initialize a new linked list
    LinkedList list1;

    // Insert elements at the end
    list1.insertAtEnd(10);
    list1.insertAtEnd(20);

    // Insert element at the beginning
    list1.insertAtBeginning(5);

    // Insert element at a specific position
    list1.insertAtPosition(15, 3);

    cout << "Linked list after insertions: ";
    list1.display();

    // Delete element from the beginning
    list1.deleteFromBeginning();
    cout << "Linked list after deleting from beginning: ";
    list1.display();

    // Delete element from the end
    list1.deleteFromEnd();
    cout << "Linked list after deleting from end: ";
    list1.display();

    // Delete element from a specific position
    list1.deleteFromPosition(2);
    cout << "Linked list after deleting from position 2: ";
    list1.display();

    return 0;
}

Output

Linked list after insertions: 5 -> 10 -> 15 -> 20 -> NULL
Linked list after deleting from beginning: 10 -> 15 -> 20 -> NULL
Linked list after deleting from end: 10 -> 15 -> NULL
Linked list after deleting from position 2: 10 -> NULL

Note: You can easily implement the other types of linked lists with some minor changes in the above code.

Applications of Linked Lists

Following are some common applications of the linked list data structure:

• In dynamic memory allocation linked lists are used to keep track of free and allocated memory blocks.
• Linked lists are used in text editors to implement undo and redo operations.
• Linked lists are used to implement adjacency lists for the graph data structures.
• Linked lists are also used to implement fundamental data structures like stack and queue.

Related Articles

Following are some of the articles that you can also read to improve your understanding about the linked list data structure:

• Linked List Data Structure
• Insertions in Linked List
• Doubly Linked List
• Circular Linked List