GATE Exam | Aptitude Questions | GATE Syllabus | GATE Result | Mock Test | GATE Preparation
0 votes

Data Structure

Data Structure

Time Complexity

Space Complexity

AverageWorstWorst
AccessSearchInsertionDeletionAccessSearchInsertionDeletion

Array

O(1)O(n)O(n)O(n)O(1)O(n)O(n)O(n)O(n)

Stack

O(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)

Singly-Linked List

O(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)

Doubly-Linked List

O(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)

Skip List

O(log(n))O(log(n))O(log(n))O(log(n))O(n)O(n)O(n)O(n)O(n log(n))

Hash Table

-O(1)O(1)O(1)-O(n)O(n)O(n)O(n)

Binary Search Tree

O(log(n))O(log(n))O(log(n))O(log(n))O(n)O(n)O(n)O(n)O(n)

Cartesian Tree

-O(log(n))O(log(n))O(log(n))-O(n)O(n)O(n)O(n)

B-Tree

O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)

Red-Black Tree

O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)

Splay Tree

-O(log(n))O(log(n))O(log(n))-O(log(n))O(log(n))O(log(n))O(n)

AVL Tree

O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
asked in Asymptotic worst case time and space complexity by anonymous

Related questions

The best answer to any question