Linked List

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

Vote For New Content

Linked List

Table of Contents

Contents are not accessible

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

. . . .

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