Explore tens of thousands of sets crafted by our community.
Data Structures and Their Operations
15
Flashcards
0/15
Queue
Complexity: Access - O(n), Search - O(n), Insertion - O(1), Deletion - O(1)
AVL Tree
Complexity: Access - O(log n), Search - O(log n), Insertion - O(log n), Deletion - O(log n)
Red-Black Tree
Complexity: Access - O(log n), Search - O(log n), Insertion - O(log n), Deletion - O(log n)
Graph
Complexity: Varies widely based on representation and algorithm.
Fenwick Tree (Binary Indexed Tree)
Complexity: Query - O(log n), Update - O(log n)
Linked List
Complexity: Access - O(n), Search - O(n), Insertion - O(1)*, Deletion - O(1)*
Array
Complexity: Access - O(1), Search - O(n), Insertion - O(n), Deletion - O(n)
Binary Search Tree (BST)
Complexity: Access - O(log n), Search - O(log n), Insertion - O(log n), Deletion - O(log n) - Average case
B-Tree
Complexity: Access - O(log n), Search - O(log n), Insertion - O(log n), Deletion - O(log n)
Stack
Complexity: Access - O(n), Search - O(n), Insertion - O(1), Deletion - O(1)
Segment Tree
Complexity: Query - O(log n), Update - O(log n)
Priority Queue
Complexity: Access - O(1) for max/min element, Insertion - O(log n), Deletion of max/min - O(log n)
Hash Table
Complexity: Average Access - O(1), Search - O(1), Insertion - O(1), Deletion - O(1); Worst case O(n)
Heap
Complexity: Access max/min - O(1), Insertion - O(log n), Deletion max/min - O(log n)
Trie
Complexity: Access - O(length of key), Insertion - O(length of key), Deletion - O(length of key)
© Hypatia.Tech. 2024 All rights reserved.
