I represented this data structures and put each file in its own folder and test this data structures in the main file using C++ language.
- Data Structures :-
- Dynamic Array
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Stack Using Array
- Stack Using Linked List
- Queue Using Array
- Queue Using Linked List
- Binary Tree
- Binary Search Tree
- Hash Table (Open Addressing)
- Hash Table (Separate Chaining)
- Min Heap
- Graph (Adjacency List)
- Graph Traversal (BFS & DFS)
- Union-Find (Disjoint Set)
- Trie
- Description of each data structure :-
- Dynamic Array : A resizable array that can grow or shrink dynamically, unlike static arrays with fixed size.
- Singly Linked List : A list where each node contains a value and a pointer to the next node only , Efficient for insertion and deletion in the middle of the list without shifting elements.
- Doubly Linked List : Each node contains pointers to both the previous and next nodes , Allows traversal in both directions and faster insertion/deletion.
- Circular Linked List : The last node points back to the head instead of NULL, forming a circle , Commonly used in operating systems.
- Stack Using Array : A LIFO (Last In, First Out) data structure implemented using arrays , using for Function call management, undo operations.
- Stack Using Linked List : A stack implemented with a linked list, making it dynamic in size , Useful when the maximum size of the stack is unknown.
- Queue Using Array : A FIFO (First In First Out) data structure implemented using arrays , using for Task scheduling, buffering, handling requests in order.
- Queue Using Linked List : A queue implemented using a linked list, removing the fixed-size limitation , Dynamic queue management where the number of elements varies.
- Binary Tree : A hierarchical data structure where each node has at most two children (left and right).
- Binary Search Tree : A special binary tree where: All nodes in the left subtree are smaller than the root. All nodes in the right subtree are larger than the root.
- Hash Table (Open Addressing) : Stores key-value pairs directly in an array and resolves collisions using probing (linear or quadratic).
- Hash Table (Separate Chaining) : Uses linked lists (buckets) at each index to handle collisions.
- Min Heap : A binary heap where the root is always the smallest element, and each parent ≤ its children.
- Graph (Adjacency List) : A graph representation where each vertex stores a list of its neighbors.
- Graph Traversal (BFS & DFS) : Algorithms for visiting all vertices of a graph:- BFS: Level-order traversal using a queue. DFS: Depth-first traversal using recursion or a stack.
- Union-Find (Disjoint Set) : A structure to manage disjoint sets with two main operations:- Find: Locate the representative of a set. Union: Merge two sets into one.
- Trie : A prefix tree used for storing strings efficiently by sharing common prefixes.
- Time/Space complexity analysis :-
- Dynamic Array : Accessing elements is fast with O(1), but inserting or deleting from the middle or beginning takes O(n) due to shifting elements. Space complexity is O(n).
- Singly Linked List : Insertion or deletion at the head is fast O(1), but accessing or modifying elements in the middle requires O(n). Space complexity is O(n).
- Doubly Linked List : Similar to singly linked list but allows deletion from the end or beginning in O(1) due to backward pointers. Accessing elements still takes O(n). Space complexity is O(n).
- Circular Linked List : Similar to doubly linked list, operations at the head or tail can be done in O(1), but accessing arbitrary elements is O(n). Space complexity is O(n).
- Stack Using Array : Core operations (push, pop, peek) are all O(1). Space complexity is O(n).
- Stack Using Linked List : Core operations (push, pop, peek) are all O(1). Space complexity is O(n).
- Queue Using Array : Operations (enqueue, dequeue, peek) are O(1). Space complexity is O(n).
- Queue Using Linked List : Operations (enqueue, dequeue, peek) are O(1). Space complexity is O(n).
- Binary Tree : Operations like insertion, searching, and deletion can take O(n) in the worst case when the tree is skewed, but O(log n) if the tree is balanced. The space complexity is O(n) since each node stores a value and pointers to its children.
- Binary Search Tree : Searching, inserting, and deleting take O(h), where h is the height of the tree; this is O(n) in the worst case for a skewed tree and O(log n) for a balanced tree. Space complexity is O(n), plus O(h) additional space for recursive calls.
- Hash Table (Open Addressing) : Insertion, search, and deletion are O(1) on average but can degrade to O(n) in the worst case if many collisions occur. Space complexity is O(n + m), where n is the number of elements and m is the table size.
- Hash Table (Separate Chaining) : Average time complexity for insertion, search, and deletion is O(1), but in the worst case, if all keys collide, it can be O(n). Space complexity is O(n + m), with n elements and m buckets, plus memory for the chains.
- Min Heap : Insertion and extracting the minimum element take O(log n), while building a heap from n elements takes O(n). Space complexity is O(n), with each element stored in an array.
- Graph (Adjacency List) : Space complexity is O(V + E). Adding an edge is O(1), but searching for a specific edge may take O(E).
- Graph Traversal (BFS & DFS) : Both require O(V + E) time and O(V) space to track visited nodes and store the queue or stack.
- Union-Find (Disjoint Set) : With path compression and union by rank, operations are nearly constant O(alpha(n)), where alpha is a very slowly growing function. Space complexity is O(n).
- Trie : The time complexity for insertion, search, deletion, and prefix checking depends on the length of the word, O(m). The space complexity can be large, O(c × n), where c is the number of possible characters for each node and n is the number of words stored in the Trie.
- How to run tests of these Data Structures in file (main) :-
- g++ -o program main.cpp
- ./program