Data Structures Overview
Characteristics of Data Structures
| Data Structure | Advantages | Disadvantages |
|---|---|---|
| Array | Quick insertion, very fast access if index known. | Slow search, slow deletion, fixed size. |
| Ordered array | Quicker search than unsorted array. | Slow insertion and deletion, fixed size. |
| Stack | Provides last-in, first-out access. | Slow access to other items. |
| Queue | Provides first-in, first-out access. | Slow access to other items. |
| Linked list | Quick insertion, quick deletion. | Slow search. |
| Binary tree | Quick search, insertion, deletion (if tree remains balanced). | Deletion algorithm is complex. |
| Red-black tree | Quick search, insertion, deletion. Tree always balanced. | Complex. |
| 2-3-4 tree | Quick search, insertion, deletion. Tree always balanced. Similar trees good for disk storage. | Complex. |
| Hash | Very fast access table if key known. Fast insertion. | Slow deletion, access slow if key not known, inefficient memory usage. |
| Heap | Fast insertion, deletion, access to the largest item. | Slow access to other items. |
| Graph | Models real-world situations. | Some algorithms are slow and complex. |
Data Structures Comparison
| Data Structure | Time Complexity | Space Complexity | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||||
| 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) | ||
| Queue | 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(nlog(n)) | ||
| Hash Table | N/A | O(1) | O(1) | O(1) | N/A | 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 | N/A | O(log(n)) | O(log(n)) | O(log(n)) | N/A | 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 | N/A | O(log(n)) | O(log(n)) | O(log(n)) | N/A | 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) | ||
| KD Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) | ||
Basic Operations on Data Structures
The basic operations that are performed on data structures are as follows:
- Insertion: Insertion means addition of a new data element in a data structure.
- Deletion: Deletion means removal of a data element from a data structure if it is found.
- Searching: Searching involves searching for the specified data element in a data structure.
- Traversal: Traversal of a data structure means processing all the data elements present in it.
- Sorting: Arranging data elements of a data structure in a specified order is called sorting.
- Merging: Combining elements of two similar data structures to form a new data structure of the same type, is called merging.