One interesting aspect of linked lists is their dynamic nature, allowing for efficient data manipulation. Unlike arrays, where elements are stored in contiguous memory locations, linked lists use nodes that are scattered in memory. This flexibility makes it easy to insert or delete elements anywhere in the list without the need to shift or resize the entire structure.
Table of Contents
Watch the video below to understand linked lists in data structures
What is a Linked List in Data Structure?
A linked list is a fundamental data structure used in computer science for organizing and managing data. Unlike arrays, which store elements in contiguous memory locations, a linked list comprises nodes connected through pointers. Each node contains data and a reference to the next node in the sequence.
Structure of a Linked List
Consider a simple example: a chain of linked paper clips. Each paper clip represents a node, and the linking mechanism is the pointer. The first paper clip holds the initial data, while each subsequent paper clip points to the next one.
How It Works
A linked list starts with a head node, representing the beginning of the list.
- Nodes are dynamically allocated in memory as data is added. Each node contains information and a pointer to the next node.
- The pointers link nodes sequentially. The last node’s pointer typically points to null, signifying the end of the list.
- To access elements, the list is traversed by following the pointers from the head to the desired node.
- Adding or removing elements involves adjusting pointers, allowing for efficient operations without moving entire blocks of memory.
The below diagram is a linked list with nodes A, B, C, and D.
Here, each arrow represents a pointer, indicating the sequence of nodes.
Enroll in this Full Stack Developer Course and start your journey now!
Linked List vs. Array
The table below lists the differences between linked lists and arrays. It showcases scenarios where one may be more suitable than the other based on specific requirements.
Feature | Linked List | Array |
Memory Allocation | Dynamically allocated, nodes scattered in memory | Contiguous block, fixed size at initialization |
Insertion/Deletion | Efficient for insertions/deletions anywhere | Costly, requires shifting elements for insertions |
Memory Efficiency | Variable size only uses memory as needed | Fixed size, may lead to wasted or insufficient space |
Access Time | O(n) for traversal, random access inefficient | O(1) for direct access using an index |
Memory Overhead | Additional memory for pointers | Compact, only stores data |
Flexibility | Easily adaptable to dynamic data | Fixed structure, less flexible |
Search Operation | Linear search, O(n) time complexity | Efficient search using index, O(log n) for binary |
Size Flexibility | Dynamic, grows or shrinks easily | Static requires resizing for changes |
Implementation | Simplifies complex data structures | Simple, suitable for straightforward structures |
Also, check our blog on Linkedlist in Java
Components of a Linked List
Understanding the components of a linked list is the key to unraveling the power and versatility embedded in linked list data structures.
a) Nodes
In a linked list, a node is the fundamental building block that encapsulates data and facilitates the structure of the list. Each node comprises two essential components:
- Data Field
- The data field is where the actual information is stored. It could be any data type depending on the application—integer, character, object, etc.
- For instance, in a singly linked list representing a sequence of numbers, the data field of each node would store a numerical value.
- Pointer Field
- The pointer field is crucial, as it holds the memory address of the next node in the linked list.
- This pointer enables linkage between nodes, creating a sequential flow of data. In a doubly linked list, there may be two pointers—one pointing to the next node and another to the previous one.
b) Pointers
Pointers are variables that store the memory address of another variable. In the context of linked lists, pointers play a pivotal role in establishing the connections between nodes. There are two primary types of pointers in linked lists:
- Head Pointer
- The head pointer points to the first node in the linked list. It serves as the entry point, allowing traversal through the entire list by following subsequent pointers.
- Initializing the head pointer is the starting point for creating and navigating a linked list.
- Next (and Previous) Pointers
- The next pointer in a node points to the memory location of the next node in the sequence. It is what enables the linked structure.
- In a doubly linked list, there might be an additional previous pointer pointing to the node preceding the current one.
Types of Linked Lists
Each type of linked list has its strengths and weaknesses, making it suitable for different scenarios. The choice depends on the specific requirements of the task at hand, balancing factors like memory efficiency, traversal needs, and the complexity of operations. Let us now discuss the different types of linked lists.
Singly Linked Lists
A singly linked list is a linear data structure where elements are stored in nodes, and each node points to the next one in the sequence. Each node contains two fields: data and a reference (or pointer) to the next node. The last node points to null, indicating the end. Traversal begins at the head node and moves through each subsequent node. Accessing elements involves iterating through the list, making it suitable for forward-only navigation.
Structure
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
Traversal
def traverse_list(linked_list):
current = linked_list.head
while current:
print(current.data, end=" ")
current = current.next
Example
# Creating a singly linked list
sll = SinglyLinkedList()
sll.head = Node(1)
second_node = Node(2)
third_node = Node(3)
sll.head.next = second_node
second_node.next = third_node
# Traversing the list
traverse_list(sll)
# Output: 1 2 3
Advantages
- Efficient memory usage, as each node only needs one pointer.
- Simple implementation and memory management.
Drawbacks
- Limited in reverse traversal.
- Inefficient for operations requiring access to previous nodes.
Doubly Linked Lists
A doubly linked list is a type of linked list where each node contains data and two pointers—one pointing to the next node and another to the previous node. Nodes have three fields: data, a pointer to the next node, and a pointer to the previous node. The first node’s previous pointer and the last node’s next pointer point to null. Traversal is bidirectional, allowing both forward and backward movements through the list. This flexibility aids in operations involving adjacent nodes.
Structure
class DoublyNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
Traversal
def traverse_doubly_list(linked_list):
current = linked_list.head
while current:
print(current.data, end=" ")
current = current.next
Example
# Creating a doubly linked list
dll = DoublyLinkedList()
dll.head = DoublyNode(1)
second_node = DoublyNode(2)
third_node = DoublyNode(3)
dll.head.next = second_node
second_node.prev = dll.head
second_node.next = third_node
third_node.prev = second_node
# Traversing the list
traverse_doubly_list(dll)
# Output: 1 2 3
Advantages
- Efficient for reverse traversal.
- Supports operations requiring access to both previous and next nodes.
Drawbacks
- Increased memory overhead due to an additional pointer in each node.
- More complex implementation compared to singly linked lists.
Get a comprehensive understanding of Recursion in Data Structure with our in-depth blog post!
Get 100% Hike!
Master Most in Demand Skills Now !
Circular Linked Lists
A circular linked list is a variation where the last node points back to the first, forming a closed loop. Similar to a singly linked list, the last node’s pointer points to the first, creating a circular structure. Traversal continues indefinitely, circling through the list until a specific condition is met.
Structure
class CircularNode:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
Traversal
def traverse_circular_list(linked_list):
if linked_list.head is not None:
current = linked_list.head
while True:
print(current.data, end=" ")
current = current.next
if current == linked_list.head:
break
Example
# Creating a circular linked list
cll = CircularLinkedList()
cll.head = CircularNode(1)
second_node = CircularNode(2)
third_node = CircularNode(3)
cll.head.next = second_node
second_node.next = third_node
third_node.next = cll.head
# Traversing the list
traverse_circular_list(cll)
# Output: 1 2 3 (looped back to 1)
Get a comprehensive understanding of Hashing in Data Structure with our in-depth blog!
Basic Operations on Linked Lists
Basic operations on linked lists involve effortless insertion, deletion, and traversal, forming the core of dynamic data organization and manipulation.
a) Insertion: Adding Items to the Linked List
Insertion in a linked list involves adding a new node with a specific value at a desired position. There are different scenarios for insertion:
- Inserting at the Beginning: To add a node at the beginning, you create a new node, set its pointer to the current head, and update the head to the new node.
def insert_at_beginning(head, value):
new_node = Node(value)
new_node.next = head
return new_node
- Inserting at the End: To add a node at the end, traverse the list to find the last node and update its pointer to the new node.
def insert_at_end(head, value):
new_node = Node(value)
if not head:
return new_node
current = head
while current.next:
current = current.next
current.next = new_node
return head
- Inserting at a Specific Position: To insert at a particular position, traverse the list to that position and adjust pointers to include the new node.
def insert_at_position(head, value, position):
new_node = Node(value)
if position == 0:
new_node.next = head
return new_node
current = head
for _ in range(position - 1):
if not current:
return head
current = current.next
new_node.next = current.next
current.next = new_node
return head
b) Deletion: Deleting an Existing Item from the Linked List
Deletion involves removing a node with a specific value or from a particular position:
- Deleting by Value: Traverse the list, find the node with the desired value, and adjust pointers to skip the node.
def delete_by_value(head, value):
current = head
if current and current.data == value:
return current.next
while current.next:
if current.next.data == value:
current.next = current.next.next
return head
current = current.next
return head
- Deleting at a Specific Position: Traverse the list to the position, and adjust pointers to skip the node.
def delete_at_position(head, position):
current = head
if position == 0:
return current.next
for _ in range(position - 1):
if not current:
return head
current = current.next
if not current or not current.next:
return head
current.next = current.next.next
return head
c) Traversal: Accessing Each Element of the Linked List
Traversal is the process of visiting each node in the linked list and performing some operation:
def traverse_linked_list(head):
current = head
while current:
# Perform operation on current node (print, process, etc.)
print(current.data, end=” “)
current = current.next
In this function, “head” is the starting point of the linked list. We traverse through the list, accessing and processing each element until we reach the end.
These basic operations form the foundation of linked list manipulations, enabling the dynamic and flexible handling of data within a linked list structure.
Read the Top 50 Data Structures Interview Questions to ace your next interview!
Advanced Operations on Linked Lists
There are a lot of advanced operations that can be applied to linked lists. Some of these have been discussed below.
a) Searching – Finding a Node in the Linked List
Searching in a linked list involves traversing through nodes until the desired node is found. Starting from the head node, each subsequent node is checked until the target data is located or the end of the list (null pointer) is reached.
Algorithm
- Begin at the head node.
- Check if the current node’s data matches the target.
- If a match is found, return the node; otherwise, move to the next node.
- Repeat until the target is found or the end of the list is reached.
Complexity
- The time complexity for searching in a linked list is O(n), where n is the number of nodes.
- In the worst-case scenario, the search operation may need to traverse the entire list.
b) Sorting – Sorting the Nodes in the Linked List
Sorting a linked list involves rearranging the nodes in a specific order, commonly in ascending or descending order based on node data. One common algorithm for sorting linked lists is the Merge Sort.
Algorithm (Merge Sort)
- If the list has zero or one node, it is already sorted.
- Divide the unsorted list into two halves.
- Recursively sort each half.
- Merge the sorted halves to produce a single sorted list.
Complexity
Merge Sort applied to linked lists has a time complexity of O(n log n), making it efficient for large datasets. The space complexity is O(n) due to the need for additional memory during the merging step.
c) Merging – Merge Two Sorted Lists
Merging two sorted linked lists involves combining them into a single sorted list while maintaining the order of elements. This operation is crucial in scenarios where multiple sorted lists need to be merged into one.
Algorithm
- Compare the first nodes of both lists.
- Append the smaller node to the merged list.
- Move to the next node in the list from which the smaller node was taken.
- Repeat until one of the lists is exhausted.
- Append the remaining nodes from the non-empty list to the merged list.
Complexity
- Merging two sorted lists has a time complexity of O(n), where n is the total number of nodes in both lists.
- This linear complexity arises from the need to compare and merge each node exactly once.
Comparing Different Types of Linked Lists in Data Structure
Understanding the differences between the different types of linked lists is crucial. Each type comes with its own advantages and challenges. Let us have a look at how some of the features differentiate them.
Feature | Singly Linked List | Doubly Linked List | Circular Linked List |
Node Structure | Data + Next Pointer | Data + Next Pointer + Previous Pointer | Data + Next Pointer |
Traversal Direction | Unidirectional (forward) | Bidirectional (forward and backward) | Unidirectional (circular) |
Memory Overhead | Lower (only next pointer) | Higher (next and previous pointers) | Lower (only next pointer) |
Insertion/Deletion | Efficient for insertions at the end | Efficient for insertions/deletions | Efficient for insertions at any position |
Memory Efficiency | Less memory is used compared to doubly | More memory is used due to two pointers | Similar to singly, but circular structure |
Implementation Complexity | Simpler | Moderately complex due to two pointers | Similar to singly, with a circular twist |
Use Cases | Common in scenarios with forward traversal | Situations requiring backward traversal | Circular navigation, periodic operations |
Order | A -> B -> C -> null | null <- A <-> B <-> C -> null | A -> B -> C -> A |
Conclusion
Linked lists prove to be versatile data structures, with distinct types catering to diverse needs. Whether it’s the simplicity of a singly linked list, the bidirectional flexibility of a doubly linked list, or the circular continuity of a circularly linked list, each serves specific purposes. Mastering linked list operations, from basic insertions to advanced searches, enhances data manipulation skills. As you delve into data structures, remember that the choice of a linked list type depends on the nature of your data and the operations you intend to perform.
FAQs
What makes linked lists preferable over arrays?
Linked lists excel in scenarios requiring dynamic memory allocation, frequent insertions, and deletions, offering flexibility and efficient use of memory.
How do I choose between singly and doubly linked lists?
Choose a singly linked list for simple and forward traversals. Opt for a doubly linked list when bidirectional traversal or frequent insertions and deletions are essential.
What is the significance of the head pointer in a linked list?
The head pointer marks the starting point of a linked list, providing access to the entire structure. It’s crucial for navigation and manipulation of linked list elements.
When should I use a circular linked list?
Circular linked lists are ideal for scenarios requiring continuous navigation, such as periodic tasks or operations that need to loop through the elements seamlessly.
Can linked lists be used for large datasets?
While linked lists offer dynamic memory allocation, their pointers can introduce overhead. For large datasets with fixed sizes, arrays might be more efficient in terms of memory usage.