Introduction to Linked List in C++
Have you ever wondered how a data sequence can be managed efficiently without the constraints of physical storage order? In C++, a linked list data structure offers this flexibility, allowing elements to be easily inserted or removed without reorganizing the entire structure. Let us understand more!
Data Structures offers various ways to organise and use data effectively. One such famous data structure is the Linked List. As the name suggests, linked list data structures are a collection of data elements in linear form.
Table of Content
- What is Linked List Data Structure in C++?
- Properties of Linked List
- Representation of Linked List
- Creating a Linked List in C++
- How is Linked List Stored in the Memory in C++?
- Real-life Example of Linked-List Data Structure
- Arrays vs. Linked List
- Types of Linked Lists in C++
- Linked List Operations
- Linked List Time Complexity
Best-suited C / C++ courses for you
Learn C / C++ with these high-rated online courses
What is Linked List Data Structure in C++?
Linked List is a linear data structure that contains two parts: a collection of data called Nodes and a Reference pointer that holds the address of the next node in the sequence.
Take a look at the below image for reference:
Properties of Linked List
A Linked List generally has the below-listed properties:
- Dynamic size: Linked lists are dynamic in nature, as they can expand and contract as required.
- Non-contiguous storage: Linked list nodes are stored in a non-contiguous storage.
- Effective insertion and deletion: When compared to arrays, a linked list easily allows the insertion and deletion of nodes.
- Flexible: Data structures, like stacks, queues, and hash tables, can be implemented using linked lists.
- Access Time: Unlike arrays, accessing elements of a linked list is less efficient as we need to traverse starting from the linked list HEAD.
- Memory Overhead: As the data and the pointers of a linked list need to be stored in the case of a linked list, the memory required to store a linked list is higher than an array.
Traversal Direction: Traversal of a linked list is generally uni-directional as we have to start from the HEAD and iterate until we reach the linked list's tail.
Representation of Linked List
A linked list is a chain of nodes, where each node has the 2 below-listed components.
- Data: This is where the data is stored
- Next: This is where the address of the next node is stored.
Take a look at the below image for reference:
A linked list with a single Node can be defined as follows in C++
struct node{ int data; struct node *next;};
Let’s explore the linked list in detail further now.
Creating a Linked List
A linked list can be created in C++ by declaring a single class to represent each node in the Linked List. Take a look at the below example:
// Node class represents an// individual element in the linked listclass Node {public: int data; // Data stored in the node Node* next; // Pointer to the next node
// Constructor to initialize data // and set next to nullptr Node(int val) : data(val), next(nullptr) {}};
How is Linked List Stored in the Memory?
Since the nodes are allocated and deallocated in a Linked List as necessary, it can be dynamically and flexibly sized in memory. A basic explanation of how a singly linked list is kept in memory is provided below:
- Node Structure: The linked list's nodes are often implemented as classes. A node's structure normally consists of two key components: Data (where the elements you wish to keep are saved) and The Next Pointer (a reference or pointer to the node after it in the list). if the next node is absent, it points to the null.
- Head Pointer: A HEAD pointer usually points to the list's first node and controls how the linked list is organised. The head pointer is often set to the null pointer if the list is empty.
- Dynamic Allocation: As nodes are added to the list using operators like new or malloc, they are dynamically allocated from the heap memory. Unlike arrays with a fixed size, the list can expand or contract as needed, thanks to dynamic allocation.
- Connecting Nodes: A reference (the next pointer) to the following node in the list can be found in each node. The nodes are linked in this way. The existing last node's next pointer is changed to point to the new node whenever a brand-new node is added to the list.
- Traversal: Starting at the head node, you can move across the linked list via the successive nodes' pointers. The traversal persists till the list's end.
- Deallocation: When you're done working with a linked list, it's crucial to dispose of the memory by looping through the list and either deleting or freeing each node. Failure to do so may cause memory leaks.
The below image represents a simple linked list with 5 nodes:
The image above, shows a chunk of memory locations which range from 1 to 10. The highlighted portion contains data. Remember that the nodes of a linked list need not be in consecutive memory locations. In our example, the nodes for the linked list are stored at addresses 1, 5, 7, 8, and 10.
In the diagram on the left in the image above, the variable HEAD is used to hold the address of the first node. Since HEAD = 1 in this case, the initial data ‘H’ is stored at address 1. The address of the next node is stored in the corresponding NEXT, which is 5. So, we’ll go to address 5 to get the next data item.
E is the second data piece retrieved from address 5. We find the corresponding NEXT to go to the next node. We receive the next address, 7, from the item in the NEXT, and L as the data. This operation is repeated until we reach a place where the NEXT item contains -1 or NULL, and this denotes the end of the linked list.
Real-life Example of Linked-List Data Structure
Some of the real-world applications of linked lists are listed below:
- Operating system: Most operating systems use linked lists to manage directories and give them a structure. It is also used for tracking & maintaining system processes.
- Garbage collection: Most programming languages come with garbage collection, including C++. A linked list can be used here to maintain a list of memory blocks that must be cleared after process completion.
- DB Index Management: Linked lists are frequently used for implementing database indexes internally by most relational database management systems like MySQL & PostgreSQL, etc.
- Task Scheduling: A linked list can also be used to schedule and maintain the queues containing the tasks for processing.
- Cache management: Caching allows us to fetch frequently requested data from the database without actually making a database query. These caches can be implemented using a linked list for efficient cache eviction policies such as Least Recently Used(LRUs), meaning the least requested data are placed at the end of the linked list and are replaced when the cache is full.
- Browsing History: Browsers typically use linked lists to manage and store browsing history. This allows the implementation of features like going back and going forward from a particular browsing instance.
Tabular Comparision of Arrays vs Linked List
The below table lists the key differences between Arrays and Linked Lists in C++:
| Feature |
||
| Storage |
Contiguous memory locations |
Non-contiguous memory locations |
| Size |
Fixed |
Dynamic |
| Access |
Random |
Sequential |
| Insertion |
Slow |
Fast |
| Deletion |
Slow |
Fast |
| Memory usage |
Efficient |
Less efficient |
| Complexity |
Access an element – O(1)Insert an element at the beginning – O(n)Insert an element at the end – O(n) |
:Access an element – O(n)Insert an element at the beginning – O(1)Insert an element at the end – O(n) |
| Applications |
Storing large amounts of data that need to be accessed randomly |
Storing data that needs to be inserted and deleted frequently |
Types of Linked Lists in C++
There are 3 key types of Linked Lists in C++, as listed below:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Let’s look at each of them in a bit more detail.
Singly Linked List
A singly linked list is a node-based linear data structure. Each node in the list has a data field and a pointer to the following node. The head and tail of a list are the first and last nodes, respectively.
Each node in singly linked lists has just one link, which points to the node after it in the list, hence the name "singly". Singly-linked lists are now less effective for some operations, including accessing entries in the centre of the list, but they are also easier to create as a result.
Doubly Linked List
A doubly linked list is a node-based linear data structure. Every node in the list has two references—one to the node before it and the other to the node after it—and a data field. The head and tail of a list are the first and last nodes, respectively.
The term "doubly" linked lists refers to every node in the list containing two links: one to the node before it and another to the node after it. Because of this, doubly linked lists are more effective for certain actions (such as retrieving members from the centre of the list), but their implementation becomes more difficult.]
Circular Linked List
A circular linked list is a variant of a linked list where the list's final node is looped back around to connect to the initial node. The last node in a conventional singly linked list usually has a null pointer(or equivalent) as its subsequent pointer to denote the list's end. A continuous loop is created in a circular linked list when the subsequent pointer from the last node points back towards the first node.
Basic Operations on a List
- Traversing a Linked List
- Inserting an item in the Linked List
- Deleting an item from the Linked List
Traversing a Linked List
To traverse a linked list in C++, we can make use of the following steps::
- Create a pointer to the head node of the linked list.
- Unless the pointer is null, continue with the following:
- Get/print the data at the current node
- Change the pointer to the subsequent node of the linked list
- Stop the traversal ifd the pointer points to null.
Algorithm
The algorithm typically looks like the following:
Step 1: [INITIALIZE] SET PTR = HEAD
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR DATA
Step 4: SET PTR = PTR NEXT
[END OF LOOP]
Step 5: EXIT
A simple implementation of the above algorithm is given below
// This program traverses a linked list and prints the data field of each node.
#include < iostream >
struct Node { int data; // The data field of the node. Node* next; // A pointer to the next node in the linked list.};
// Traverses the linked list and prints the data field of each node.void traverse_linked_list(Node* head) { // Create a pointer to the current_node node in the linked list. Node* current_node = head;
// While the pointer is not null, print the data field of the current_node node and // move the pointer to the next node in the linked list. while (current_node != nullptr) { std::cout < < current_node- > data < < " "; current_node = current_node- > next; }
// Print a newline character. std::cout < < std::endl;}
int main() { // Create a head node for the linked list. Node* head = new Node{10};
// Add two more nodes to the linked list. head- > next = new Node{20}; head- > next- > next = new Node{30};
// Traverse the linked list and print the data field of each node. traverse_linked_list(head);
return 0;}
Output
10 20 30
Time complexity: O(n)
Space complexity: O(1)
Inserting an item in the Linked List
There are 3 different ways to insert elements to a linked list in C++. Let’s discuss each one of them in detail.
Insert at the beginning of the Linked list.
To insert an element at the beginning of a linked list, follow the below steps:
- Create a new node with the new data.
- Set the next pointer of the new node to the current head node.
- Set the head node to the new node.
Algorithm
A typical implementation of this process follows the below algorithm
Step 1: [INITIALIZE] CREATE NEW_NODE
Step 2: SET NEW_NODE DATA = VALUE
Step 3: SET NEW_NODE NEXT = HEAD
Step 4: SET HEAD = NEW_NODE
Step 5: EXIT
Take a look at the image below for reference
Insert at the end of the Linked list.
Follow the below steps to insert an element at the end of a linked list:
- Create a new node with the given data.
- Traverse the linked list until the last node is reached.
- Set the next pointer of the last node to the new node.
Algorithm
A typical implementation of this process follows the below algorithm:
Step 1: [INITIALIZE] CREATE NEW_NODE, SET PTR = HEAD
Step 2: SET NEW_NODE DATA = VALUE, NEW_NODE NEXT = NULL
Step 3: If HEAD is NULL
SET HEAD = NEW_NODE
Else
Repeat Steps 4 and 5 while PTR NEXT != NULL
Step 4: SET PTR = PTR NEXT
[END OF LOOP]
Step 5: SET PTR NEXT = NEW_NODE
Step 4: EXIT
Take a look at the image below for reference
Insert at the middle of the Linked list.
Follow the below steps to insert an element in the middle of a linked list:
- Traverse the linked list until you reach the middle node.
- Create a new node with the given data.
- Set the next pointer of the new node to the current middle node.
- Set the next pointer of the previous node to the new node.
Algorithm
The algorithm for such operation over a linked list typically looks like below:
Step 1: [INITIALIZE] CREATE NEW_NODE, SET PTR = HEAD
Step 2: SET NEW_NODE DATA = VALUE, NEW_NODE NEXT = NULL
Step 3: Calculate the position to insert (e.g., at position 'POS')
Step 4: Repeat Steps 5 and 6 'POS - 1' times
Step 5: SET PTR = PTR NEXT
[END OF LOOP]
Step 5: SET NEW_NODE NEXT = PTR NEXT
Step 6: SET PTR NEXT = NEW_NODE
Step 7: EXIT
Take a look at the image below for reference
Take a look at the example below for reference
#include < iostream >
struct Node { int data; Node* next;};
void insertAtBeginning(Node*& head, int data) { Node* newNode = new Node{data}; newNode- > next = head; head = newNode;}
void insertAtMiddle(Node*& head, int data) { if (head == nullptr) { head = new Node{data, nullptr}; return; }
Node* slow = head; Node* fast = head- > next; // Start fast one node ahead for even-length adjustment
while (fast != nullptr && fast- > next != nullptr) { slow = slow- > next; fast = fast- > next- > next; }
Node* newNode = new Node{data}; newNode- > next = slow- > next; slow- > next = newNode;}
void insertAtEnd(Node*& head, int data) { Node* newNode = new Node{data}; newNode- > next = nullptr;
if (head == nullptr) { head = newNode; return; }
Node* current = head; while (current- > next != nullptr) { current = current- > next; }
current- > next = newNode;}
int main() { Node* head = nullptr;
insertAtBeginning(head, 30); insertAtBeginning(head, 20); insertAtBeginning(head, 10);
Node* current = head; std::cout < < "List after inserting at the beginning: "; while (current != nullptr) { std::cout < < current- > data < < " "; current = current- > next; } std::cout < < std::endl; insertAtMiddle(head, 60); current = head; std::cout < < "List after inserting in the middle: "; while (current != nullptr) { std::cout < < current- > data < < " "; current = current- > next; } std::cout < < std::endl;
insertAtEnd(head, 40);
current = head; std::cout < < "List after inserting at the end: "; while (current != nullptr) { std::cout < < current- > data < < " "; current = current- > next; } std::cout < < std::endl;
// Memory cleanup (to prevent memory leaks) while (head != nullptr) { Node* temp = head; head = head- > next; delete temp; }
return 0;}
Output
List after inserting at the beginning: 10 20 30
List after inserting in the middle: 10 20 60 30
List after inserting at the end: 10 20 60 30 40
Deleting Node(s) of a Linked List
To delete a specific node from the linked list, use the following method:
- Traverse to the node that is to be deleted.
- If the node is HEAD node, set the node to the next node in the sequence.
- Else, find the previous node to the node that is to be deleted.
- Set the next pointer of the previous node to the next node of the node to be deleted.
Algorithm
For deleting an element from a linked list, make use of the below algorithm.
Step 1: SET PTR = HEAD, SET PREV = NULL
Step 2: Calculate the value to delete (e.g., VALUE)
Step 3: Repeat Steps 4 and 5 while PTR != NULL and PTR DATA != VALUE
Step 4: SET PREV = PTR
Step 5: SET PTR = PTR NEXT
[END OF LOOP]
Step 6: If PTR is NULL (Value not found)
EXIT
Step 7: If PREV is NULL (Deleting the first node)
Step 8: SET HEAD = PTR NEXT
Step 9: DELETE PTR
EXIT
Step 10: SET PREV NEXT = PTR NEXT
Step 11: DELETE PTR
Step 12: EXIT
Take a look at the below image for reference.
Here is a simple example of in C++ implementing the above algorithm
#include < iostream >
struct Node { int data; Node* next;};
// Inserts an element at the beginning of the linked list.void insertAtBeginning(Node*& head, int data) { Node* newNode = new Node{data}; newNode- > next = head; head = newNode;}
// Deletes a node from the linked list.void deleteNode(Node*& head, Node* nodeToDelete) { if (nodeToDelete == nullptr) { return; }
// If the node to be deleted is the head node. if (nodeToDelete == head) { head = head- > next; delete nodeToDelete; return; }
// Find the previous node of the node to be deleted. Node* previousNode = nullptr; Node* currentNode = head; while (currentNode != nullptr && currentNode != nodeToDelete) { previousNode = currentNode; currentNode = currentNode- > next; }
// If the node to be deleted is not in the linked list. if (currentNode == nullptr) { return; }
// Set the `next` pointer of the previous node to the next node of the node to be deleted. previousNode- > next = currentNode- > next;
// Free the memory allocated to the node to be deleted. delete currentNode;}
int main() { Node* head = nullptr;
// Insert some elements to the linked list. insertAtBeginning(head, 30); insertAtBeginning(head, 20); insertAtBeginning(head, 10);
// Print the elements of the linked list. std::cout < < "List before deletion: "; Node* current = head; while (current != nullptr) { std::cout < < current- > data < < " "; current = current- > next; } std::cout < < std::endl;
// Delete the node with the value 20. deleteNode(head, head- > next);
// Print the elements of the linked list again. std::cout < < "List after deletion: "; current = head; while (current != nullptr) { std::cout < < current- > data < < " "; current = current- > next; } std::cout < < std::endl;
// Memory cleanup while (head != nullptr) { Node* temp = head; head = head- > next; delete temp; }
return 0;}
Output
List before deletion: 10 20 30
List after deletion: 10 30
Time Complexity: O(n)
Space Complexity: O(1)
Linked List Time Complexity
Linked Lists provide an optimized way to insert, delete, and update information while storing data. This optimization comes at the cost of extra space required for storing pointers to the next node in each node of the list.
| Operation | Average Case | Worst Case |
|---|---|---|
| Search | O(n) | O(n) |
| Insertion | O(1)* | O(n) |
| Deletion | O(1)* | O(n) |
* The O(1) complexity for insertion and deletion assumes that the position where the operation is to be performed is already known and accessible (e.g., inserting or deleting at the head of the list). However, if you need to find a specific position first (other than the head), the complexity becomes O(n) since it requires traversing the list to locate the position.
With this, we end this article on Linked Lists in C++. We hope you found it informative. Now, you can practice our popular linked list questions asked in the interview.
Conclusion
In this article, we have covered the following concepts associated with linked lists in C++:
- Basics of linked list & its structure
- Types of linked list
- Traversing a linked list
- Inserting elements in a linked list
- Deleting elements in a linked list
- Time complexity
Contributed by: Raju Kumar
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
