Linked list
A Linked List is a fundamental data structure in computer science, where elements, called nodes, are stored in a linear sequence. Each node contains two main components
1. Data: The actual value or data.
2. Pointer (or reference): A link or reference to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each element points to the next, making it more flexible for dynamic memory usage but slower for random access.
Operations on Linked Lists:
1. Insertion: Adding an element at the beginning, end, or any given position.
Time complexity: O(1) for insertion at the head or O(n) for insertion at a specific position.
2. Deletion: Removing an element from the list (e.g., head, tail, or a specific node).
Time complexity: O(1) for head removal or O(n) for a specific node.
3. Traversal: Accessing elements by following the links from one node to another.
Time complexity: O(n) because we need to traverse through the list sequentially.
4. Search: Finding an element in the list.
Time complexity: O(n), as we need to traverse the list to locate the desired node.
Advantages of Linked Lists:
• Dynamic size: Can grow or shrink dynamically without the need for reallocation.
• Efficient insertions and deletions: Especially at the beginning or middle of the list.
Disadvantages of Linked Lists:
• Random access is not allowed: You have to traverse the list sequentially to access an element.
• Extra memory space for pointers: Each node requires additional memory to store the pointer/reference.
• Slow traversal: Traversing a linked list takes O(n) time as compared to arrays which have O(1) random access.
Applications:
• Implementing stacks, queues, graphs, and dynamic memory allocation.
• Used in undo functionality in text editors, where changes can be tracked in a linked list.
Types of Linked Lists:
There are three main types of linked lists, each with distinct characteristics and use cases: Singly Linked List, Doubly Linked List, and Circular Linked List. Let's explore each type in detail:
1. Singly Linked List (SLL)
A Singly Linked List is the most basic type of linked list. In this list, each node contains:
• Data: The information or value the node holds.
• Next: A reference (or pointer) to the next node in the list.
The last node's Next pointer is set to NULL, which marks the end of the list. Traversal is only possible in one direction (from the head to the tail).
Structure:
[Data | Next] -> [Data | Next] -> [Data | Next] -> NULL
Operations:
• Insertion at the Beginning: New nodes can easily be added at the head of the list in O(1) time.
• Insertion at the End: Requires traversal to the last node, hence O(n) time complexity.
• Deletion: Removing the first node is O(1), but deleting a node from the middle or end requires traversal, resulting in O(n) time.
Advantages:
• Simple to implement.
• Requires less memory than other linked list types because each node has only one pointer (next).
Disadvantages:
• Only supports one-way traversal.
• Reversing the list is complex, as pointers need to be rearranged.
• Inefficient for operations like searching or deletion in the middle of the list, as it requires traversing from the head.
Use Cases:
• Implementing stacks and queues.
• Managing memory in dynamic data structures.
2. Doubly Linked List (DLL)
A Doubly Linked List extends the functionality of the singly linked list by adding an additional pointer in each node:
• Data: The data or value of the node.
• Next: A pointer to the next node.
• Prev: A pointer to the previous node.
This allows for bidirectional traversal (both forward and backward), making certain operations more efficient.
Structure:
NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL
Operations:
• Insertion:
Inserting a node at the head or tail can be done in O(1) time, provided you have direct access to the location.
Inserting at any given position requires traversal, hence O(n) time complexity.
• Deletion:
Removing the first or last node is O(1), but removing from the middle requires traversal, making it O(n).
• Traversal: Traversing the list in both directions is possible, offering greater flexibility.
• Search: Similar to singly linked lists, searching requires traversal and takes O(n) time.
Advantages:
• Supports bidirectional traversal, allowing both forward and backward operations.
• Easier to delete a node if its reference is known, as the previous node pointer is readily available.
• Can be used for more complex structures like dequeues (double-ended queues) or navigating back and forth in browser history.
Disadvantages:
• Requires more memory per node due to the additional pointer.
• Slightly more complex to implement than singly linked lists.
• More overhead in insertion/deletion due to the need to update two pointers (next and prev).
Use Cases:
• Navigation systems where you need to go back and forth (e.g., undo/redo operations, browser history).
• Implementing dequeues and other dynamic data structures.
3. Circular Linked List
In a Circular Linked List, the last node in the list points back to the first node, forming a circle. This can be implemented as either a Singly Circular Linked List or a Doubly Circular Linked List.
a. Singly Circular Linked List (SCLL):
• Similar to a singly linked list but with a twist: the last node's Next pointer points to the head, forming a loop.
Structure:
[Data | Next] -> [Data | Next] -> [Data | Next] --|
Operations:
• Traversal: Traversal can continue indefinitely if not careful, as there's no natural end. To stop, you must check when you've returned to the starting node.
• Insertion: Inserting at the head or tail is efficient, similar to singly linked lists.
• Deletion: Deleting the head or a specific node requires traversal and proper pointer adjustment.
Advantages:
• Circular lists are useful when you want to cycle through data repeatedly, such as in round-robin scheduling algorithms.
• No need to track the last node explicitly because the circular nature makes traversal continuous.
Disadvantages:
• More complex to manage, especially when inserting or deleting nodes.
• Can result in infinite loops if proper exit conditions are not implemented in traversal.
b. Doubly Circular Linked List (DCLL):
• Combines the circular structure with the bidirectional nature of a doubly linked list. The last node's Next pointer points to the head, and the head's Prev pointer points to the tail.
Structure:
Head <-> [Prev | Data | Next] <-> [Prev | Data | Next] <-> Tail
Operations:
• Similar to doubly linked lists but with the added circular nature.
• Efficient in both insertion and deletion, especially at the head and tail, with O(1) complexity.
• Traversal can be both forward and backward, with no natural endpoint.
Advantages:
• Bidirectional and circular, allowing for easy navigation in both directions.
• Ideal for applications that need continuous loops or repeated processing (e.g., multimedia players).
Disadvantages:
• Increased complexity and memory overhead due to the additional pointer in each node and the circular structure.