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

Contents are not accessible

Contents are not accessible

Contents are not accessible

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.

Image

Basic Operations on Linked List

Python3
Python3

. . . .

Time Complexity Analysis for Linked List Operations

Image
  • 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:

  1. Data: The actual value of the element.
  2. 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

OperationStatic ArrayDynamic ArrayLinked List
Access by IndexO(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)
SearchingO(n)O(n)O(n)
Space ComplexityO(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