# Types of Data Structures

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:

1. Static Data Structures
2. Dynamic Data Structures
3. Persistent Data Structures
4. Partially Persistent Data Structure
5. Ephemeral Data Structures
6. Geometric Data Structures
7. Graph Data Structures
8. Probabilistic Data Structures
9. String Data Structures
10. 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:

• Array

# 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.

• 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
• Trie
• 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.

• 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.

• Does not keep track of previous operations / state and makes the overall structure simplier.

Examples of Ephemeral Data Structures:

• Array
• 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.

• Efficient representation of Multi-dimensional data
• Data Structures suited for range/ interval based problems

Examples of Geometric Data Structures:

• R Tree
• Range Trees
• KD-Tree
• 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.

• Efficient representation for Graph based problems
• Tree based data structures are best suited for 2D data.

Examples of Graph Data Structures:

• 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.

• 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.

• Efficient representation of Strings

Examples of String Data Structures:

• Trie
• Suffix array
• Suffix 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.