Linked lists are an essential and flexible data structure in computer science, known for their dynamic memory allocation and efficient data management. Unlike arrays, linked lists allow for variable sizes, enabling seamless modifications to the list. As nodes containing data and references to the next node, linked lists ensure efficient insertion and deletion operations, even within the middle of the list. Implementing linked list in C++ involves defining a node structure and managing node connections. This blog will provide an in-depth exploration of Linked List in C++, covering their definition, implementation, various operations like insertion, deletion, traversal, and searching, and their practical applications in real-world scenarios. Understanding linked list in C++ will equip programmers with a powerful tool to manage data in a dynamic and organized manner in C++ programming endeavors.
What is a Linked List?
A linked list is a linear data structure consisting of nodes, where each node contains data and a pointer (or reference) to the next node in the sequence. The nodes are not necessarily stored in contiguous memory locations, unlike arrays. Instead, they are dynamically allocated, allowing for efficient insertion and deletion operations, even in the middle of the list.
Implementation of Linked List in C++
To implement a linked list in C++, we need to define a node structure representing each element and then manage the connections between nodes. Let’s explore the basic structure of a singly linked list:
- First, we define a structure named
Nodeto represent each element (node) in the linked list. Each node contains two fields:data, which stores the actual data of the node, andnext, which is a pointer to the next node in the sequence. - Inside the
main()function, we create three pointers of typeNode, namelyhead,second, andthird, representing three nodes of the linked list. - We assign data values to each node using the
datafield and establish the link between nodes using thenextpointers. In this example, we set the data values to 10, 20, and 30 for the nodeshead,second, andthird, respectively. We then linkheadtosecondandsecondtothird. Finally, we set thenextpointer of the last nodethirdtonullptr, indicating the end of the linked list. - The next step is to traverse the linked list and print the data of each node. We start from the
headnode and use a loop to traverse through the linked list until we reach the end (wherenextisnullptr). During traversal, we print the data of each node, separated by spaces. - After printing the linked list, we must deallocate the memory used by the nodes to prevent memory leaks. We use the
deletekeyword to free the memory occupied by each node. - The program then returns 0, indicating successful execution.
OUTPUT
The code implements a singly linked list with three nodes, containing data 10, 20, and 30, respectively. The program traverses the linked list and prints the data of each node, resulting in the output 10 20 30. Finally, the program deallocates the memory used by the nodes to avoid memory leaks.
Linked List Operations
Linked lists support various operations, including:
- Insertion: Inserting a new node at the beginning, end, or middle of the list.
- Deletion: Removing a node from the list.
- Traversal: Iterating through the list to access and process elements.
- Searching: Finding a specific element in the list.
- Concatenation: Combining two linked lists.
Time complexity of Linked list in C++
| Operation | Singly Linked List | Doubly Linked List | Circular Linked List |
|---|---|---|---|
| Accessing an Element (by index) | O(n) | O(n/2) or O(n) | O(n) |
| Insertion (at the Beginning) | O(1) | O(1) | O(1) |
| Insertion (at the End) | O(n) | O(1) | O(n) |
| Insertion (in the Middle, given node) | O(1) | O(1) | O(1) |
| Deletion (at the Beginning) | O(1) | O(1) | O(1) |
| Deletion (at the End) | O(n) | O(1) | O(n) |
| Deletion (in the Middle, given node) | O(1) | O(1) | O(1) |
Explanation:
1. Accessing an Element (by index): Singly linked list has a time complexity of O(n) since it may need to traverse the entire list to reach the desired index. In a doubly linked list, it takes O(n/2) or O(n) (worst-case) depending on the proximity of the index to the head or tail. Circular linked list’s time complexity is also O(n) since it behaves similarly to a singly linked list.
2. Insertion (at the Beginning): All three types of linked lists (singly, doubly, and circular) have a time complexity of O(1) for insertion at the beginning. It only involves updating pointers and does not require traversing the list.
3. Insertion (at the End): Singly linked list has a time complexity of O(n) since it requires traversing the entire list to reach the last node and then linking the new node. Doubly linked list has O(1) time complexity, as it can directly insert at the end using the tail pointer. Circular linked list’s time complexity is O(n) (worst-case) if the tail pointer is not available.
4. Insertion (in the Middle, given a node): All three types of linked lists (singly, doubly, and circular) have O(1) time complexity for insertion in the middle, given a node, as it involves updating pointers and does not require traversal.
5. Deletion (at the Beginning): All three types of linked lists (singly, doubly, and circular) have a time complexity of O(1) for deletion at the beginning. It only involves updating pointers and deallocating the old head node.
6. Deletion (at the End): Singly linked list has a time complexity of O(n) since it requires traversing the entire list to reach the second-to-last node and updating its next pointer to nullptr. Doubly linked list has O(1) time complexity, as it can directly delete the last node using the tail pointer. Circular linked list’s time complexity is O(n) (worst-case) if the tail pointer is not available.
7. Deletion (in the Middle, given a node): All three types of linked lists (singly, doubly, and circular) have O(1) time complexity for deletion in the middle, given a node, as it involves updating pointers and does not require traversal.
Space Complexity of Linked list in C++
| Linked List Type | Space Complexity |
|---|---|
| Singly Linked List | O(n) |
| Doubly Linked List | O(n) |
| Circular Linked List (Singly or Doubly) | O(n) |
Explanation:
1. Singly Linked List: Each node in a singly linked list contains two parts: the data and a pointer to the next node. The space complexity of a singly linked list is O(n), where n is the number of elements (nodes) in the list. It includes the memory required for data storage and the memory used for maintaining the pointers to link the nodes.
2. Doubly Linked List: Each node in a doubly linked list contains three parts: the data, a pointer to the next node, and a pointer to the previous node. The space complexity of a doubly linked list is also O(n), where n is the number of elements (nodes) in the list. Similar to a singly linked list, it includes the memory for data storage and the extra memory for the two pointers (next and previous) to maintain the doubly linked structure.
3. Circular Linked List: A circular linked list can be either singly or doubly linked. The space complexity of a circular linked list, whether singly or doubly linked, is O(n), where n is the number of elements (nodes) in the list. It includes the memory required for data storage and the additional memory for the circular connections, which link the last node back to the first node.
Some code examples
1. Insertion at the beginning of Linked list in C++
In this code, we define a struct Node representing the nodes of the linked list with two members: data to store the data and next as a pointer to the next node. The insertAtBeginning function inserts a new node with the given newData at the beginning of the linked list. We achieve this by creating a new node, updating its next pointer to the current head of the list, and making the new node the new head.
OUTPUT
2. Insertion at the end of Linked list in C++
The insertAtEnd function inserts a new node with the given newData at the end of the linked list. It traverses the list until it reaches the last node (where next is nullptr), and then appends the new node to the next pointer of the last node.
OUTPUT
3. Insertion after a node of Linked List in C++
The insertAfterNode function inserts a new node with the given newData after the specified prevNode. It first checks if the prevNode is not nullptr. If it’s valid, it creates a new node, updates its next pointer to prevNode->next, and then updates prevNode->next to point to the new node.
OUTPUT
4. Deletion of a node of Linked List in C++
The deleteNode function deletes the node with the given key from the linked list. It traverses the list to find the node with the matching key. Once found, it updates the previous node’s next pointer to skip the node to be deleted, and then deletes the node using the delete keyword.
OUTPUT
5. Traversal of Linked list in C++
The traverseList function simply traverses the linked list and prints each node’s data from the head to the end of the list.
OUTPUT
6. Search for an element of Linked list in C++
The searchElement function searches for the given key in the linked list. It starts at the head of the list and traverses the list, comparing each node’s data with the key. If the key is found, the function returns true; otherwise, it returns false
OUTPUT
7. Concatenation of two linked lists of Linked list in C++
The concatenateLists function concatenates the second linked list (head2) to the end of the first linked list (head1). If the first list (head1) is empty, it simply points head1 to head2. Otherwise, it traverses the first list (head1) to reach the last node and then updates its next pointer to point to the head of the second list (head2).
OUTPUT
Advantages of Linked Lists:
1. Dynamic Size: Linked lists can grow or shrink dynamically, as memory is allocated or deallocated for each node independently. This flexibility allows efficient handling of data with unpredictable or varying sizes.
2. Efficient Insertion and Deletion: Insertion and deletion of elements in linked lists are efficient operations, especially when adding or removing elements at the beginning or in the middle. It requires updating only a few pointers, making it faster than shifting elements in an array.
3. Memory Efficiency: Linked lists use memory efficiently, as each node only requires memory for its data and a pointer to the next node. In contrast, arrays may require additional memory for unused or empty slots, leading to potential memory wastage.
4. Ease of Implementation: Implementing linked lists is relatively straightforward, especially for singly linked lists. Nodes are connected through pointers, and no resizing of the data structure is required.
5. No Need for Pre-allocation: Unlike arrays, linked lists do not require pre-allocation of memory for a fixed number of elements. They can grow as needed, saving memory in situations where the exact number of elements is unknown.
Limitations of Linked Lists:
1. Memory Overhead: Linked lists require extra memory for storing pointers/references in each node, adding memory overhead compared to arrays.
2. Inefficient Random Access: Accessing elements in linked lists takes linear time (O(n)) in the worst case since it requires traversing the list from the beginning. In contrast, arrays offer constant-time (O(1)) random access by index.
3. Cache Inefficiency: Due to scattered memory locations, linked lists may not utilize hardware caching efficiently, leading to potentially slower performance compared to contiguous arrays.
4. More Complex Operations: Some operations, such as reversing a linked list, require more complex algorithms compared to arrays, making certain tasks less straightforward.
5. Lack of Direct Access: Unlike arrays, linked lists do not support direct access to elements by index, which may be a disadvantage for specific applications.
Real-World Applications
Linked lists find applications in various real-world scenarios, such as:
1. Dynamic Data Structures: Linked lists’ dynamic memory allocation makes them suitable for managing data structures with varying sizes, such as stacks and queues.
2. File Systems: Linked lists are used to maintain the directory structure, where each node represents a file or a subdirectory, linked to its parent directory.
3. Music and Video Playlists: Linked lists can be used to create playlists, where each node represents a song or video, linked to the next song or video in the playlist.
Some use of Linked List
1. Dynamic Data Structures: Linked lists are fundamental for implementing other dynamic data structures like stacks and queues. They allow efficient push and pop operations in stacks and enqueue and dequeue operations in queues.
2. Memory Management: Linked lists are used in memory management systems to manage and organize free memory blocks for efficient allocation and deallocation.
3. File Systems: Linked lists are used in file systems to maintain the hierarchical directory structure. Each node represents a file or directory, linked to its parent and child nodes, forming a tree-like structure.
4. Music and Video Playlists: Linked lists are employed to create playlists for music and video streaming applications. Each node represents a song or video, linked to the next element in the playlist.
5. Hash Tables: Linked lists are used to handle collisions in hash tables, where elements with the same hash value are stored as nodes in the linked list associated with the corresponding hash index.
6. Graph Representation: Linked lists can be utilized to represent graph data structures, where each node represents a vertex, and the linked list contains the adjacent vertices.
7. Undo/Redo Functionality: Linked lists are handy for implementing undo and redo functionality in software applications. Each node in the linked list stores the state of the application at a specific point in time, allowing users to undo or redo actions.
8. Image Processing: Linked lists are employed in image processing applications to represent and manipulate linked lists of pixels, allowing easy manipulation and filtering.
9. Garbage Collection: In some garbage collection algorithms, linked lists are used to manage memory allocation and deallocation, helping in identifying and freeing unused memory.
10. Polynomial Representations: Linked lists can be used to represent and perform operations on polynomials in mathematical applications.
These are just a few examples of how linked lists are utilized in various domains. Their dynamic nature, ability to handle varying sizes, and efficient insertion and deletion operations make them valuable in many applications, both in software development and computer science.
Conclusion
Linked lists provide an elegant solution for efficient data organization and manipulation in C++. The ability to dynamically allocate memory and the flexibility in insertion and deletion operations make them indispensable in various applications. As you journey deeper into the realm of C++ programming, understanding linked lists will undoubtedly enrich your ability to design elegant and optimized solutions for diverse programming challenges. So, embark on the chain of data and unravel the power of linked list in C++ endeavors!
Want a good reference book for DSA in C++?
This is a classic and widely regarded as one of the most comprehensive and authoritative books on algorithms. It covers a broad range of algorithms and data structures and provides in-depth explanations and analyses. Although the examples in the book use pseudocode, many students and programmers have successfully applied the concepts in C++.
check 4rth Hardcover price Kindel Edition price.
check 3rd edition price: Paper Back
you can also check out for DSA in java:
This book is a part of a series that covers data structures and algorithms using different programming languages, including Java, C, and Python. So, if you specifically want to learn data structures and algorithms in Java, you can look for the Java version of this book. It will provide examples and explanations using Java programming language to illustrate various concepts related to data structures and algorithms.
check price: Paperback
Best problem-solving book in c++: Problem Solving with C++ by Walter Savitch
Although not specifically a DSA book, this resource introduces C++ programming through problem-solving techniques. It is beginner-friendly and includes some coverage of basic data structures and algorithms.
check price : paperback
In this book, you’ll find a wide range of array-related problems, including array manipulation, searching, sorting, dynamic programming, and more. Each problem is explained thoroughly, and the solutions are provided with step-by-step explanations and code examples in multiple programming languages, including C++.
The book also includes valuable tips and strategies for approaching coding interviews, making it a useful resource for anyone preparing for technical interviews at top tech companies.
check price: paperback
| see my blogs | Programming Series | Fact Series | Tech Series |
