Classification of Data Structure

Data structures can be classified into various categories based on different criteria such as their arrangement of data, the way they store data, and how they operate.

1. Linear vs Non-Linear Data Structures

• Linear Data Structures: In linear data structures, elements are stored sequentially, and each element is connected to its previous and next element. Operations are generally performed in a sequence.

  • Examples:

    • Arrays (Lists in Python)

    • Linked Lists

    • Stacks

    • Queues

• Non-Linear Data Structures: In non-linear data structures, elements are not stored sequentially. They have a hierarchical relationship or complex connections.

  • Examples:

    • Trees (e.g., Binary Trees, Binary Search Trees)

    • Graphs

    • Heaps (Binary Heaps)

• 2. Static vs Dynamic Data Structures

  • Static Data Structures: These data structures have a fixed size and the memory required is allocated at compile time. They are less flexible but easy to manage.

    • Examples:

      • Arrays (fixed-length arrays in some languages)

  • Dynamic Data Structures: These can grow and shrink at runtime as needed. Memory is allocated as the program runs, making them more flexible.

    • Examples:

      • Linked Lists

      • Dynamic Arrays (Python lists)

      • Stacks and Queues (implemented with linked lists)

  3. Homogeneous vs Heterogeneous Data Structures

  • Homogeneous Data Structures: All elements in the structure are of the same data type.

    • Examples:

      • Arrays (storing only integers, or only floats, etc.)

      • Stacks of integers or characters

  • Heterogeneous Data Structures: These can store elements of different types within the same structure.

    • Examples:

      • Tuples in Python (can store mixed types, e.g., (1, 'a', 3.14))

      • Dictionaries (mapping different types of keys to values)

  4. Primitive vs Non-Primitive Data Structures

  • Primitive Data Structures: These are the most basic types that store a single value.

    • Examples:

      • Integers (int)

      • Floats (float)

      • Characters (char)

      • Booleans (bool)

  • Non-Primitive Data Structures: These store collections of values and may involve complex relationships between the elements. They can be either linear or non-linear.

    • Examples:

      • Arrays

      • Linked Lists

      • Stacks

      • Queues

      • Trees

      • Graphs

      • Hash Tables (Dictionaries in Python)

  5. Linear Data Structures

  These store elements in a linear or sequential order. Common operations include traversal, insertion, and deletion, which are performed in a linear manner.

  • Examples:

    • Array: Stores elements in contiguous memory locations.

    • Linked List: A series of nodes where each node points to the next one.

    • Stack: Follows Last In, First Out (LIFO) order.

    • Queue: Follows First In, First Out (FIFO) order.

  6. Non-Linear Data Structures

  These store elements in a hierarchical or interconnected manner, often requiring more complex operations for traversal, searching, or modification.

  • Examples:

    • Tree: A hierarchical structure where nodes have parent-child relationships (e.g., binary trees, AVL trees).

    • Graph: A collection of nodes (vertices) and edges where each edge connects two nodes. Can be directed or undirected.

    • Heap: A specialized tree-based data structure that satisfies the heap property (e.g., min-heap or max-heap).

  7. Hierarchical Data Structures

  In these structures, elements are arranged in a hierarchy, with each element having relationships to one or more other elements.

  • Examples:

    • Trees: Each node has a parent (except the root) and zero or more children (e.g., binary tree, n-ary tree).

    • Heaps: A type of tree-based structure used mainly for priority-based algorithms.

  8. Graph-Based Data Structures

  Graphs are a collection of nodes connected by edges, used for representing networks, such as social connections, routing paths, etc.

  • Examples:

    • Directed Graph (Digraph): Edges have a direction, meaning one-way relationships between nodes.

    • Undirected Graph: Edges don’t have direction, meaning two-way relationships.

    • Weighted Graph: Each edge has a weight or cost associated with it.

  9. Hash-Based Data Structures

  These are used for quick lookups, insertions, and deletions, based on a hash function. A key is mapped to a value in these structures.

  • Examples:

    • Hash Tables: Also known as hash maps or dictionaries (as in Python). They map keys to values for quick retrieval.

    • Sets: A collection of unique elements, implemented using hash tables in most languages