We have presented different types of Data Structures along with the advantage and examples of each type. This is a must list to understand which type of Data Structures you want to research about.
The different types of Data Structures are:
- Static Data Structures
- Dynamic Data Structures
- Persistent Data Structures
- Partially Persistent Data Structure
- Ephemeral Data Structures
- Geometric Data Structures
- Graph Data Structures
- Probabilistic Data Structures
- String Data Structures
- Succinct Data Structures
Let us get started.
1. Static Data Structures
Static Data Structure is a Data Structure that once created, cannot insert or decrease the size / total number of elements supported. Such data structures support insert and delete operations but only till the point that the total number of elements is within the given limit. The memory of such data structure are allocated statically.
Advantages of using Static Data Structures:
- Memory requirement is fixed. Memory can be allocated statically during compile time.
Examples of Static Data Structures:
- Fractional Cascading
2. Dynamic Data Structures
Dynamic Data Structure is a Data Structure that can grow in size / total number of elements during runtime as new elements are inserted into the data structure. It is an improvement to Dynamic Data Structure.
Advantages of Dynamic Data Structures:
- Can insert any number of elements.
- Memory increases as the total number of elements increase. There is no wastage in the form of unused memory.
Examples of Dynamic Data Structures are:
- Dynamic Array (The Dynamic version of Array)
- Linked List and all its variants
- Binary Tree
3. Persistent Data Structures
Persistent Data Structure is a data structure which stores the state of the data structure at every timestamp whenever an operation (like insert or delete) is done which modifies the structure of the Data Structure.
Operations on a Persistent Data Structure can be done on any of the saved versions of the Data Structure.
Advantages of Persistent Data Structure:
- Keeps track of all changes made on the Data Structure
- Easy to roll back to a previous state
Examples of Persistent Data Structures are:
- Persistent Segment Tree
4. Partially Persistent Data Structure
Partially Persistent Data Structure is a restricted variant of Persistent Data Structure where the previous versions are available but operations are not permitted on them. Operations are allowed only on the latest version.
Advantages of Partially Persistent Data Structure:
- Simplified version of Persistent Data Structure
Examples of Partially Persistent Data Structure:
- Partially Persistent Segment Tree
5. Ephemeral Data Structures
Ephemeral Data Structure is a Data Structure which is neither persistent nor partially persistent. It does not store previous versions of the Data Structure. Only the current state of Data Structure is maintained.
Advantages of Ephemeral Data Structure:
- Does not keep track of previous operations / state and makes the overall structure simplier.
Examples of Ephemeral Data Structures:
- Linked List
- Hash Map
- Self-Balancing Binary Search Tree
6. Geometric Data Structures
Geometric Data Structure is a Data Structure that is used to represent multi-dimensional data. It separates geometry from connectivity/ topology. These data structures are mainly used in Computer Graphics and Space related problems.
Advantages of Geometric Data Structure:
- Efficient representation of Multi-dimensional data
- Data Structures suited for range/ interval based problems
Examples of Geometric Data Structures:
- R Tree
- Range Trees
- Interval Tree
7. Graph Data Structures
Graph Data Structure is a Data Structure that represents a 2D data in form of a graph where nodes are data and edges are properties of the data set. A special case of Graph Data Structure is Tree Data Structure where no loop (through edges) are present.
Advantages of Graph Data Structures:
- Efficient representation for Graph based problems
- Tree based data structures are best suited for 2D data.
Examples of Graph Data Structures:
- Adjacency list
- Adjacency matrix
- SPQR tree
8. Probabilistic Data Structures
Probabilistic Data Structure is a Data Structure which has a probabilistic nature towards the answer generated using it. The answer will be close to the reason answer within a given limit. The probability may not be with the answer but also with the structure or related to the steps taken by an internal operation.
Advantages of Probabilistic Data Structures:
- Efficient in terms of space and time in constrast to its deterministic counter-part.
Examples of Probabilistic Data Structures:
- Skip List
- Bloom Filter
- Hash Map
- LogLog data structure
9. String Data Structures
String Data Structure is a Data structure that is specially designed to handle strings. It supports string based operations efficiently.
Advantages of String Data Structures:
- Efficient representation of Strings
Examples of String Data Structures:
- Suffix array
- Suffix tree
- Radix Tree
10. Succinct data structure
Succinct data structure is a Data Structure which uses the theoretically lowest possible space for a given problem and also, acheives the optimal time complexity unlike other approaches where either space or time complexity is optimized.
Advantages of Succinct data structures:
- Both Space and Time Complexity is optimized to the theoretical limit for the given problem.
Examples of Succinct data structures:
- Wavelet tree
- Fractional Cascading
With this article at OpenGenus, you must have a strong idea of different types of Data Structures that are available. Enjoy.