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

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

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

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:

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