This repository for data structure (array, stacks, linked list) code in C language.
Note: For best case operations, the time complexities are O(1).
| Data Structure Name | Average Case Time Complexity | Worst Case Time Complexity | Space Complexity | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Accessing nth element | Search | Insertion | Deletion | Accessing nth element | Search | Insertion | Deletion | Worst Case | |
| Arrays | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Singly Linked List | θ(n) | θ(n) | θ(1) | θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Stacks | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queues | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Binary Trees | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Binary Search Trees | O(logn) | O(logn) | O(logn) | O(logn) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Balanced Binary Search Trees | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) |
| Hash Tables | N/A | O(1) | O(1) | O(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| Storting Algorithm Name | Time Complexity | Space Complexity | Is Stable? | Storting Class Type | Remarks | ||
|---|---|---|---|---|---|---|---|
| Best Case | Average Case | Worst Case | Worst Case | ||||
| Bubble Sort | O(n) | O(n2) | O(n2) | O(1) | Yes | Comparison | Not a preferred sorting algorithm |
| Insertion Sort | O(n) | O(n2) | O(n2) | O(1) | Yes | Comparison | In the best case (already sorted), every insert requires constant time. |
| Selection Sort | O(n2) | O(n2) | O(n2) | O(1) | No | Comparison | Even a perfectly sorted array requires scanning the entire array. |
| Merge Sort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Yes | Comparison | On array, it requires O(n) space and on linked lists, it requires constant space. |
| Heap Sort | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | No | Comparison | By using input array as storage for the heap, it is possible to achieve constant space. |
| Quick Sort | O(nlogn) | O(nlogn) | O(n2) | O(logn) | No | Comparison | Randomly picking a pivot value can help avoid worst case scenarios such as a perfectly sorted array. |
| Tree Sort | O(nlogn) | O(nlogn) | O(n2) | O(n) | Yes | Comparison | Performing inorder traversal on the balanced binary search tree. |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes | Linear | Where k is the range of the non-negative key value. |
| Bucket Sort | O(n + k) | O(n + k) | O(n2) | O(n) | Yes | Linear | Bucket sort is stable, if the underlying sorting algorithm is stable. |
| Radix Sort | O(dn) | O(dn) | O(dn) | O(d + n) | Yes | Linear | Radix sort is stable, if the underlying sorting algorithm is stable. |
- Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.
- A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
- The last node of the list contains pointer to the null.
- The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space.
- List size is limited to the memory size and doesn't need to be declared in advance.
- We can store values of primitive types or objects in the singly linked list.