Back to course home
0% completed
Vote For New Content
Linked List
A Linked List is a data structure where each element (node) contains a value and a reference (or link) to the next node in the sequence. Linked lists are dynamic and can grow or shrink easily by adding or removing nodes. Let’s explore the time and space complexities for common linked list operations.
Basic Operations on Linked List
Python3
Python3
. . . .
Time Complexity Analysis for Linked List Operations
- Access Element: O(n) – Traversing each node from the head is necessary to reach a specific node.
- Insertion:
- Beginning: O(1) – Adding a node to the head is immediate.
- End: O(n) – Reaching and inserting after the last node takes linear time.
- Middle: O(n) – Requires traversal to the desired position.
- Deletion:
- Beginning: O(1) – Removing the head node is efficient.
- End: O(n) – Reaching and removing the last node takes time.
- Middle: O(n) – Requires traversal to reach the node to delete.
- Searching: O(n) – Each node might need checking to find a specific value.
- Sorting: - It takes O(nlogn) time, same as array
Space Complexity for Linked Lists
The space complexity for a linked list depends on the number of nodes. Each node stores:
- Data: The actual value of the element.
- Pointer: A reference to the next node (or in doubly linked lists, pointers to both the next and previous nodes).
- Space Complexity: O(n), where
n
is the number of nodes in the linked list. Each node requires constant space, making the overall space proportional to the list’s length.
Array Vs. Dynamic Array Vs. Linked List
Operation | Static Array | Dynamic Array | Linked List |
---|---|---|---|
Access by Index | O(1) | O(1) | O(n) |
Insertion (end) | O(n) (fixed size) | Average O(1), Worst O(n) | O(n) |
Insertion (beginning) | O(n) | O(n) | O(1) |
Insertion (middle) | O(n) | O(n) | O(n) |
Deletion (end) | O(n) | O(1) | O(n) |
Deletion (beginning) | O(n) | O(n) | O(1) |
Deletion (middle) | O(n) | O(n) | O(n) |
Searching | O(n) | O(n) | O(n) |
Space Complexity | O(n) | O(n) (with resizing overhead) | O(n) |
.....
.....
.....
Like the course? Get enrolled and start learning!
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible