Scribd
Upload
114 views3 pages

Data Structures Complexity CheatSheet

The document outlines the time and space complexities for various data structures including arrays, stacks, queues, linked lists, trees, hash tables, heaps, tries, and graphs. Each data structure is presented with its operations and corresponding complexities, providing a quick reference for performance characteristics. This information is essential for understanding the efficiency of different data structures in algorithm design.

Uploaded by

sahnipallavi771
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
114 views3 pages

Data Structures Complexity CheatSheet

The document outlines the time and space complexities for various data structures including arrays, stacks, queues, linked lists, trees, hash tables, heaps, tries, and graphs. Each data structure is presented with its operations and corresponding complexities, providing a quick reference for performance characteristics. This information is essential for understanding the efficiency of different data structures in algorithm design.

Uploaded by

sahnipallavi771
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Data Structures - Time and Space Complexities

1. Array

Operation Time Complexity Space Complexity

Access (arr[i]) O(1) O(n)

Insert (end) O(1) O(n)

Insert (middle) O(n) O(n)

Delete (end) O(1) O(n)

Delete (middle) O(n) O(n)

Search (unsorted) O(n) O(n)

Search (sorted) O(log n) O(n)

2. Stack (Array or Linked List)

Operation Time Complexity Space Complexity

Push O(1) O(n)

Pop O(1) O(n)

Peek/Top O(1) O(n)

Search O(n) O(n)

3. Queue (FIFO)

Operation Time Complexity Space Complexity

Enqueue (add) O(1) O(n)

Dequeue O(1) O(n)

Peek/Front O(1) O(n)

4. Circular Queue

Operation Time Complexity Space Complexity

Enqueue O(1) O(n)

Dequeue O(1) O(n)

Front O(1) O(n)

5. Singly Linked List

Operation Time Complexity Space Complexity

Insert (head) O(1) O(n)


Insert (end) O(n) O(n)

Delete O(n) O(n)

Search O(n) O(n)

Access O(n) O(n)

6. Doubly Linked List

Operation Time Complexity Space Complexity

Insert/Delete (head/tail) O(1) O(n)

Insert/Delete (middle) O(n) O(n)

Search O(n) O(n)

7. Binary Search Tree (BST)

Operation Time Complexity Space Complexity

Insert O(log n) O(n)

Delete O(log n) O(n)

Search O(log n) O(n)

8. AVL / Red-Black Tree

Operation Time Complexity Space Complexity

Insert O(log n) O(n)

Delete O(log n) O(n)

Search O(log n) O(n)

9. Hash Table / HashMap

Operation Time Complexity Space Complexity

Insert O(1) O(n)

Delete O(1) O(n)

Search O(1) O(n)

10. Heap (Min/Max)

Operation Time Complexity Space Complexity

Insert (push) O(log n) O(n)

Delete (pop) O(log n) O(n)

Peek (Top) O(1) O(n)


11. Trie

Operation Time Complexity Space Complexity

Insert O(L) O(AL)

Search O(L) O(AL)

Delete O(L) O(AL)

12. Graph (Adj List/Matrix)

Operation Time Complexity Space Complexity

Add Vertex O(1) O(V + E)

Add Edge O(1) O(V + E)

Search (BFS/DFS) O(V + E) O(V + E)

13. Priority Queue (Heap)

Operation Time Complexity Space Complexity

Insert O(log n) O(n)

Delete Max/Min O(log n) O(n)

Peek O(1) O(n)

You might also like