1. Trees
1.1. Binary Search Tree
1.1.1. Insertion
1.1.1.1. O(log h), h=height of the tree
1.1.2. Deletion
1.1.2.1. O(log h), h= height of the tree
1.1.3. Search
1.1.3.1. O(log h), H=height of the tree
1.1.4. Access
1.1.4.1. O(1), if address is known
1.1.4.2. O(h) if address is not known
1.1.5. Should be balanced
1.1.6. NOTE
1.1.6.1. Creating the tree would take O( nlogh ) time
1.1.6.2. Although, the complexity for this is similar to sorted arrays or better, there is not concept of index. Hence, based on algorithm we are trying to implement, the data structure would vary over that as well.
1.1.7. Storage
1.1.7.1. Dynamic
1.2. Heaps
1.2.1. Special Use : Quick access to smallest / largest elements
1.2.2. Insertion
1.2.2.1. O(h)
1.2.3. Deletion
1.2.3.1. O(h)
1.2.4. Search
1.2.4.1. Largest / smallest elem - O(1)
1.2.5. Should be balanced
1.2.6. Storage
1.2.6.1. Dynamic memory
1.3. TRIE
1.3.1. Special Use : Efficient information retrieval
1.3.2. Usually used to store keys referring to some data / all the data starting with a prefix of key given. Eg., all words start with characters, 'he'
1.3.3. Insertion
1.3.3.1. O(h)
1.3.4. Deletion
1.3.4.1. O(h)
1.3.5. Search
1.3.5.1. O(k), k is the length of the key
1.3.6. Should be balanced
1.3.7. Storage
1.3.7.1. Dynamic allocation
1.4. Markle Trees
2. Graphs
2.1. These are used for many real world problems to denote a network
2.2. These should be looked from a point of view that it would help us understanding the problem and visualize it better rather than checking if insertion/deletion/etc would be fast
3. Hash Map
3.1. Insertion
3.1.1. O (1) asymptotically
3.2. Deletion
3.2.1. O(1) asymptotically
3.3. Search
3.3.1. O(n)
3.4. Access
3.4.1. O(1) asymptotically
3.5. Implementation
3.5.1. Using Array. Each element is saved in the array, if the current calculated index has the value, then next space free is used. This uses static memory
3.5.2. Using array and list. Array is used to stored the key, but values are stored in list. Hence storage would be dynamic
3.6. Note
3.6.1. Hash function should be good enough to avoid maximum collisions
3.6.2. The more the size of the array is, the better is the complexity as that would avoid collisions
4. Linked List
4.1. Insertion
4.1.1. O (1)
4.1.2. Considering the node to be added after is known
4.2. Deletion
4.2.1. O (1)
4.2.2. Considering that we know the node present before the node to be deleted
4.3. Dynamic Length
4.4. Search
4.4.1. O (n)
4.5. Access
4.5.1. No dynamic access using index. Need address of node to access it.
4.6. Storage
4.6.1. These are stored in dynamic memory or heap. Hence, the constant factor might be more than that of array. But still it would be constant
5. Sorted Array
5.1. Insertion
5.1.1. O (n)
5.2. Deletion
5.2.1. O (n)
5.3. Search
5.3.1. O (log n)
5.4. Access
5.4.1. O (1)
5.5. Dynamic length
5.5.1. Depends highly on programming language
5.5.2. Usually the one with dynamic length is not implemented as an array underneath
5.6. Note
5.6.1. Creating an sorted array from a normal array is O (n log n)
5.6.2. Contiguous memory allocation
6. Array
6.1. Insertion
6.1.1. O (n)
6.2. Deletion
6.2.1. O (n)
6.3. Search
6.3.1. O (n)
6.4. Access
6.4.1. O (1)
6.4.2. Direct access via index
6.5. Dynamic length
6.5.1. Depends highly on programming language
6.5.2. Usually the one with dynamic length is not implemented as an array underneath
6.6. Note
6.6.1. Contiguous memory allocation
7. Queue
7.1. Simulates FIFO
7.2. Limited operation search
7.3. Insertion
7.3.1. O(1) at the end of the data structure
7.4. Deletion
7.4.1. O (1) at the start of the data structure
7.5. Search
7.5.1. O(1) for the first element
7.6. Access
7.6.1. O(1) for first element
7.7. Implementation types
7.7.1. Circular Queue - Using Arrays
7.7.1.1. Fixed Memory.
7.7.1.2. Although the operations are O(1), but the constant factor would be fast since the allocation of this data structure is happening in stack
7.7.2. Doubly Linked list queue
7.7.2.1. Dynamic memry
7.7.2.2. Operations are O(1). But each operation constant factor might be more since the allocation in happening in heap.
8. Stack
8.1. Simulates LIFO
8.2. Limited Operation Search
8.3. Insertion
8.3.1. O(1) for insertion at the last
8.4. Deletion
8.4.1. O(1) for deletion of last element
8.5. Search
8.5.1. O(1) for last element added
8.6. Access
8.6.1. O(1) to get the last element added
8.7. Implementation types
8.7.1. Circular Stack - Using Arrays
8.7.1.1. Fixed Memory.
8.7.1.2. Although the operations are O(1), but the constant factor would be fast since the allocation of this data structure is happening in stack
8.7.2. Linked list stack
8.7.2.1. Dynamic memry
8.7.2.2. Operations are O(1). But each operation constant factor might be more since the allocation in happening in heap.