Linked List in C++

What is Linked List in C++?

Linked lists are fundamental data structures in computer programming, especially useful in scenarios where the size of the dataset cannot be predicted upfront & the ability to efficiently insert & remove elements is critical. Unlike arrays, linked lists are composed of nodes that are not stored in contiguous memory locations; instead, each node points to the next node in the sequence. This structure allows for dynamic memory allocation & flexible management of data.

In this article, we'll learn how to implement linked lists in C++, including creating nodes & performing various operations. We'll also look at both singly & doubly linked lists to understand their advantages & specific use cases.

Flow Diagram of a Linked List

A flow diagram provides a visual representation of the structure & operations of a linked list. Essentially, a linked list consists of a series of nodes where each node contains two parts: data & a reference (or link) to the next node in the sequence. In a basic singly linked list, the flow starts from a 'head' which marks the beginning of the list. Each node links to the next one, & the last node points to a null value, indicating the end of the list.

This diagram helps in visualizing how data flows through the list, making it easier to understand the insertion, deletion, & traversal operations that we will explore further.

In the context of C++, the node structure can be defined as follows:

struct Node {
    int data;     // Data to hold the integer value
    Node* next;   // Pointer to the next node in the list
};
Node* head = nullptr; // Initially, the list is empty, so head is set to nullptr

This code sets up the basic building block of a linked list, which we will use to create more complex operations & types of linked lists.

Implementation of a Linked List in C++

Implementing a linked list in C++ involves setting up a structure for the nodes and writing functions to manage the nodes: adding, removing, and traversing through the list. Let's start by defining how to set up the linked list and create a simple function to add nodes to the front of the list.

First, we define the structure of a node. Each node will store an integer as data and a pointer to the next node:

struct Node {
    int data;     // Data to hold the integer value
    Node* next;   // Pointer to the next node in the list
};
Node* head = nullptr; // Start with an empty list

To add elements to the linked list, we can use the following function, which inserts nodes at the beginning:

void insertAtHead(int value) {
    Node* newNode = new Node(); // Create a new node
    newNode->data = value;      // Set the data of the node
    newNode->next = head;       // Point the new node's next to the current head
    head = newNode;             // Make the new node the new head of the list
}

This function creates a new node, sets its data, and then places it at the beginning of the list by updating the head pointer. This approach is efficient for inserting data at the start of the list since it only requires a few operations, regardless of the list's size.

By using these building blocks, we can extend our linked list to perform more complex operations, such as adding nodes at specific positions, deleting nodes, and more, which will be covered in subsequent sections.

Creating a Node of a Linked List

To work with linked lists in C++, understanding how to create a node is crucial. A node is the fundamental unit of a linked list, containing the data and a reference to the next node. Here’s how you can define and add a new node to a linked list:

Define the Node Structure

First, define the structure of a node, which includes the data part and a pointer to the next node.

struct Node {
    int data;  // The data stored in the node
    Node* next;  // Pointer to the next node in the list
};

Creating a New Node

To create a new node, you typically write a function that allocates memory for a node, initializes its data, and sets its next pointer.

Node* createNode(int value) {
    Node* newNode = new Node();  // Dynamically allocate a new node
    newNode->data = value;       // Set the node's data
    newNode->next = nullptr;     // Initially, the next pointer is set to nullptr
    return newNode;              // Return the newly created node
}

This function creates a new node with the specified data and returns a pointer to it. The node’s next pointer is initially set to nullptr, indicating that it does not yet link to another node.

Using the Node

Once the node is created, it can be linked into the linked list. For example, to add this node at the beginning of the list, you can modify the head of the list:

void insertAtHead(Node*& head, Node* newNode) {
    newNode->next = head;  // Point the new node's next to the current head
    head = newNode;        // Update the head to the new node
}

This function updates the list’s head to the new node, effectively adding it to the front of the list. Creating nodes and manipulating them through functions like this forms the basis of more complex linked list operations.

Types of Linked Lists in C++

1. Singly Linked Lists

Structure

In a singly linked list, each node contains two components: the data and a pointer to the next node. The list is navigated starting from the head node and moving through each node until the end is reached (indicated by a null pointer).

Declaration

struct Node {
    int data;      // The integer data stored in the node
    Node* next;    // Pointer to the next node in the list
};
Node* head = nullptr; // Initially, the list is empty

Usage

This type of list is efficient for simple operations where traversal from the beginning to the end is sufficient. It is less memory intensive as it only holds a single pointer per node.

2. Doubly Linked Lists

Structure

Doubly linked lists allow navigation both forwards and backwards. Each node contains three parts: data, a pointer to the next node, and a pointer to the previous node. This structure makes it easier to perform operations that involve traversing in both directions.

Declaration

struct DoublyNode {
    int data;             // The integer data stored in the node
    DoublyNode* prev;     // Pointer to the previous node
    DoublyNode* next;     // Pointer to the next node
};
DoublyNode* head = nullptr; // Initially, the list is empty

Usage

Doubly linked lists are ideal for data structures that require frequent addition and deletion of nodes from both ends, such as in the implementation of certain types of caches or advanced queuing mechanisms.

3. Circular Linked Lists

Structure: A circular linked list can be singly or doubly linked but with an additional characteristic: the last node points back to the first node, making the list circular. This type of list does not have a natural end as the next pointer of the last node does not point to null but instead to the head of the list.

Singly Circular Linked List Declaration

struct CircularNode {
    int data;              // The integer data stored in the node
    CircularNode* next;    // Pointer to the next node, last node points to head
};
CircularNode* head = nullptr; // Initially, the list might be empty

Doubly Circular Linked List Declaration

struct DoublyCircularNode {
    int data;                    // The integer data stored in the node
    DoublyCircularNode* prev;    // Pointer to the previous node
    DoublyCircularNode* next;    // Pointer to the next node, wraps around to head
};
DoublyCircularNode* head = nullptr; // Initially, the list might be empty

Usage

Circular linked lists are useful in applications where a continuous loop of nodes is beneficial, such as in a music playlist or implementing round-robin algorithms where the system needs to cycle through each node repeatedly without a clear start or end.

Operations of a Linked List

Understanding how to perform basic operations on linked lists is crucial for effectively using them in programming. Here, we'll cover the essential operations you can perform on a linked list in C++, such as insertion, deletion, and traversal.

Insertion

Adding a Node at the Head

This is one of the simplest operations. It involves pointing the new node's next to the current head of the list and then updating the head to this new node.

void insertAtHead(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

Adding a Node at the Tail

To add a node at the end of the list, you need to traverse the list to find the last node and set its next pointer to the new node.

void insertAtTail(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;
    if (head == nullptr) {
        head = newNode;
        return;
    }
    Node* last = head;
    while (last->next != nullptr) {
        last = last->next;
    }
    last->next = newNode;
}

Deletion

Deleting a Node by Key: To delete a node, you must find the node with the given value and update the pointers to exclude it from the list.

void deleteNodeByKey(Node*& head, int key) {
    Node* temp = head;
    Node* prev = nullptr;

    if (temp != nullptr && temp->data == key) {
        head = temp->next;
        delete temp;
        return;
    }
    while (temp != nullptr && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == nullptr) return;  // Key was not found
    prev->next = temp->next;
    delete temp;
}

Traversal

Displaying the List: Traversing the list to display its contents is straightforward. You simply iterate from the head to the end, printing each node’s data.

void printList(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "nullptr\n";
}

Example 1 - Operations of a Singly Linked List

To demonstrate the practical application of the operations we discussed, let's go through examples using a singly linked list in C++. We will create a simple list, add nodes, delete a node, and display the list.

Creating and Populating the List

First, we'll define a function to populate our list with initial data to work with:

void populateList(Node*& head) {
    insertAtTail(head, 10);  // Add a node with value 10 to the list
    insertAtTail(head, 20);  // Add a node with value 20 to the list
    insertAtTail(head, 30);  // Add a node with value 30 to the list
    insertAtTail(head, 40);  // Add a node with value 40 to the list
}

Displaying the List

Next, we display the list to see its contents before any deletions:

cout << "Initial List: ";
printList(head);

Deleting a Node

Let's delete a node from the list to see how deletion is handled:

deleteNodeByKey(head, 20);  // Delete the node with value 20
cout << "List after deleting 20: ";
printList(head);

Final Output of the List

Finally, we display the list after the deletion to observe the changes:

cout << "Final List: ";
printList(head);

This sequence of operations shows how a singly linked list handles basic tasks like insertion, deletion, and traversal. It's clear and straightforward, making it suitable for beginners to understand and implement.

Example 2 - Operations of a Doubly-Linked List

Exploring the functionality of a doubly-linked list in C++, let’s focus on creating, deleting, and displaying elements to demonstrate its bidirectional capabilities.

Creating and Populating the Doubly-Linked List

We start by defining the doubly linked list node structure and functions to manage the list:

struct DoublyNode {
    int data;
    DoublyNode* prev;
    DoublyNode* next;
};
void insertAtTail(DoublyNode*& head, int value) {
    DoublyNode* newNode = new DoublyNode();
    newNode->data = value;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    if (head == nullptr) {
        head = newNode;
        return;
    }
    DoublyNode* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

Displaying the List

To display a doubly-linked list, we need to consider that we can traverse both forwards and backwards:

void printListForward(DoublyNode* head) {
    DoublyNode* temp = head;
    cout << "Forward: ";
    while (temp != nullptr) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "nullptr\n";
}
void printListBackward(DoublyNode* tail) {
    DoublyNode* temp = tail;
    cout << "Backward: ";
    while (temp != nullptr) {
        cout << temp->data << " <- ";
        temp = temp->prev;
    }
    cout << "nullptr\n";
}

Deleting a Node

Deleting a node in a doubly-linked list allows for an efficient process because we can adjust pointers in both directions:

void deleteNodeByKey(DoublyNode*& head, int key) {
    DoublyNode* temp = head;
    while (temp != nullptr && temp->data != key) {
        temp = temp->next;
    }
    if (temp == nullptr) return; // Key not found
    if (temp->prev != nullptr) {
        temp->prev->next = temp->next;
    } else {
        head = temp->next; // Update head if the deleted node was the first node
    }
    if (temp->next != nullptr) {
        temp->next->prev = temp->prev;
    }

    delete temp;
}

Example Operations

After defining these operations, we can perform a sequence similar to the singly linked list:

Populate the list with data.
Display the list from both ends.
Delete a node and show the list after this operation.

This example demonstrates the additional functionality that a doubly-linked list provides, making it suitable for applications that require efficient insertion and deletion from both ends of the list.

Advantages of Linked Lists

Dynamic Size: Linked lists offer dynamic sizing capabilities, allowing them to grow or shrink during runtime based on the program's requirements. Unlike arrays, linked lists are not constrained by a fixed size, providing flexibility in memory management. Memory is allocated only when needed, ensuring efficient utilization of system resources.
Efficient Insertion & Deletion: Insertion and deletion operations in linked lists are highly efficient, especially when performed at the beginning or end of the list. These operations involve updating the pointers of adjacent nodes, resulting in a time complexity of O(1) when the position is known. This efficiency makes linked lists well-suited for scenarios that involve frequent modifications to the data structure.
Memory Efficiency: Linked lists allocate memory only for the nodes currently present in the list, minimizing memory wastage. Unlike arrays, there is no need to pre-allocate memory for a fixed size, reducing unnecessary memory consumption. Memory is dynamically allocated and deallocated as nodes are added or removed, ensuring optimal memory utilization throughout the lifetime of the linked list.
Flexibility: Linked lists serve as a flexible foundation for implementing various other data structures, such as stacks, queues, and graphs. They offer the ability to easily add or remove nodes at any position within the list, making them adaptable to a wide range of programming scenarios. Linked lists can efficiently handle dynamic and unknown-sized data, providing a versatile tool for solving complex problems.
Non-Contiguous Memory: Unlike arrays, linked lists do not require contiguous memory locations. Nodes can be scattered throughout different parts of the memory, allowing for better memory utilization. This characteristic of linked lists helps avoid memory fragmentation issues that may arise with arrays, particularly when dealing with large datasets or long-running programs.
Easy Reordering: Reordering elements in a linked list is more straightforward compared to arrays. Reordering can be accomplished by simply updating the pointers of the nodes, without the need to shift elements or allocate new memory. This simplicity makes linked lists efficient for scenarios that involve frequent reordering of elements, such as sorting or rearranging data based on specific criteria.

Disadvantages of Linked Lists

Random Access: Linked lists do not support random access to elements. Unlike arrays, where elements can be accessed directly using an index, accessing an element in a linked list requires traversing the list from the head node until the desired position is reached. This sequential access can be time-consuming, especially for large lists, resulting in a time complexity of O(n) for accessing an element at a specific position.
Extra Memory: Linked lists require extra memory to store the pointers that connect the nodes. Each node in a linked list contains a data field and one or more pointers to other nodes. These pointers consume additional memory compared to the actual data being stored. In contrast, arrays do not require extra memory for pointers, as elements are stored in contiguous memory locations.
Cache Inefficiency: Linked lists are not cache-friendly due to their non-contiguous memory layout. Unlike arrays, where elements are stored in consecutive memory locations, the nodes of a linked list can be scattered throughout the memory. This lack of locality can lead to poor cache performance, as accessing nodes may require fetching data from different cache lines or even from the main memory, resulting in slower access times.
Complexity of Implementation: Implementing certain operations on linked lists can be more complex compared to arrays. For example, inserting or deleting a node in the middle of a linked list requires updating the pointers of the adjacent nodes, which can be more involved than simply overwriting an element in an array. Additionally, operations like reversing a linked list or detecting cycles require careful manipulation of pointers and can be more challenging to implement correctly.
Overhead of Memory Allocation: Creating a new node in a linked list involves dynamic memory allocation using the new keyword. This memory allocation operation has some overhead, as it requires system calls and may introduce memory fragmentation over time. In contrast, arrays have a fixed size and do not require dynamic memory allocation for individual elements, making them more memory-efficient in certain scenarios.
Lack of Spatial Locality: Linked lists do not provide good spatial locality, which can impact performance when iterating over the elements. In arrays, elements are stored in contiguous memory locations, allowing for efficient iteration and better cache utilization. However, in linked lists, nodes can be scattered throughout the memory, leading to more cache misses and slower iteration performance, especially for large lists.

Frequently Asked Questions

Why use a linked list instead of an array?

Use a linked list when you need dynamic data allocation, frequent insertion and deletion of elements at any position, and do not require quick access to elements by index, as linked lists do not support random access efficiently.

What are the advantages of doubly linked lists over singly linked lists?

Doubly linked lists allow traversal in both directions, making operations like deletion more efficient because you can access the previous node directly. This is particularly useful in applications requiring frequent addition and removal of nodes from both ends of the list.

How do you handle memory management in linked lists?

In C++, it's crucial to ensure that every node allocated with new is later deallocated with delete to prevent memory leaks. Proper memory management involves careful tracking and freeing of nodes when they are no longer needed.

Conclusion

In this article, we have learned about linked lists in C++, covering their types, operations, and practical applications. We explored how to implement and manipulate singly and doubly linked lists, discussed their advantages and disadvantages, and provided code examples to illustrate their operations. Understanding these concepts is very important for solving problems that require dynamic data management, and linked lists serve as a critical component in the toolkit of an efficient programmer.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

What is Linked List in C++?

Flow Diagram of a Linked List

Implementation of a Linked List in C++

Creating a Node of a Linked List

Define the Node Structure

Creating a New Node

Using the Node

Types of Linked Lists in C++

1. Singly Linked Lists

Structure

Declaration

Usage

2. Doubly Linked Lists

Structure

Declaration

Usage

3. Circular Linked Lists

Singly Circular Linked List Declaration

Doubly Circular Linked List Declaration

Usage

Operations of a Linked List

Insertion

Adding a Node at the Head

Adding a Node at the Tail

Deletion

Traversal

Example 1 - Operations of a Singly Linked List

Creating and Populating the List

Displaying the List

Deleting a Node

Final Output of the List

Example 2 - Operations of a Doubly-Linked List

Creating and Populating the Doubly-Linked List

Displaying the List

Deleting a Node

Example Operations

Advantages of Linked Lists

Disadvantages of Linked Lists

Related Topics

Arrays

Stacks

Queues

Trees

Graphs

Hashing

Frequently Asked Questions

Why use a linked list instead of an array?

What are the advantages of doubly linked lists over singly linked lists?

How do you handle memory management in linked lists?

Conclusion