Overview:

In computer programming, data structures are a fundamental conecpt that helps us organize and manage data efficiently. Non-primitive data structures, also known as user-defined data structures, are more complex and specialized than primitive data types like integers or characters. They allow us to store and manipulate collections of data in various ways. Lets start by understanding them.

What are Non-Primitive Data Structures?

Non-primitive data structures are user-defined data types that can hold multiple values of different types. They are designed to store and organize data in more complex and meaningful ways, facilitating operations such as insertion, deletion, searching, and traversal.

Unlike primitive data types (e.g., int, float, char, double) that represent single values, non-primitive data structures can represent and manage a collection of values or even complex relationship among them. They play a crucial role in solving real-world problems efficiently.

Non-primitive data structures can be broadly categorized into two main categories based on their organizational structure: linear and non-linear data structures. Each category has its unique characteristics and use cases. Lets explore them.

Linear Data Structures:

Linear data structures are those in which data elements are organized sequentially, where each element has a specific predecessor and successor except for the first and last elements. These structures follow a specific order and easy to traverse in a single pass. Linear Data Structures can be categorized into two main types based on their behavior with to respect to size: static and dynamic linear data structures. Each type has its own characteristics, advantages, and use cases.

Static Linear Data Structures

Static linear data structures have a fixed size or capacity that is determined at the time of creation and cannot be easily changed during program execution. These structures are suitable when know the maximum number of elements you will need in advance, and you want to avoid the overhead of dynamic resizing. Common static linear data structures include:

Static Arrays (Normal Array)

Arrays is used to store multiple values in a single variable of same data type. Data in array is stored in contiguous memory locations. Indexing of arrays in C++ always starts from 0 and ends at one less than the size of the array. We will discuss more in deep in later chapters.

• Static arrays have a fixed size that is defined when the array is declared.
• Once the size is set, it cannot be changed.
• Accessing elements in a static array is fast, as it uses a constant time index.
• Static arrays are suitable when the number of elements is known and does not change.

Dynamic Linear Data Structures

Dynamic linear data structures can grow or shrink in size during program execution as needed. They provide more flexibility and are used when the number of elements is not known in advance, or may change over time. Common dynamic linear data structures include:

1. Dynamic Arrays (Vectors in C++)

A dynamic array is quite similar to a regular array, but its size is modifiable during program runtime. Dynamic array elements occupy a contiguous block of memory.

In normal array once it has been created, its size cannot be changed. However, a dynamic array is different. A dynamic array can expand its size even after it has been filled.

• Dynamic arrays, often called vectors in C++, can dynamically resize themselves.
• They allocate memory needed to accommodate additional elements

2. Linked Lists

A linked list is a linear data structure that includes a series of connected nodes. Here each node stores the data and the address of the next node. As seen in the example below. 

• Linked lists are inherently dynamic data structures.
• They consist of nodes where each node has a data element and a pointer/reference to the next node.
• Linked list can grow or shrink by adding or removing nodes, making them suitable for situations with varying data sizes.

3. Dynamic Queues and Stacks

• Dynamic queues and stacks can expand or shrink to accommodate elements.
• They are often implemented using dynamic arrays or linked lists.
• These structures are used when the number of elements in the queue or stack may change during program execution.

Non-Linear Data Structures

Non-linear data structures do not follow a sequential order for organizing data elements. These structures have more complex relationships among their elements, often forming hierarchies or interconnected networks. Common non-linear data structures include:

1. Trees

• Trees are hierarchical data structures consisting of nodes connected by edges.
• Each node can have multiple child nodes but typically has one parent node (except for the root).
• Trees are used for hierarchical data representation, searching, and sorting.

Common types of trees include:

• Binary Trees
• Binary Search Trees (BST)
• Balanced Trees (e.g., AVL, Red-Black trees)
• Heap Trees (e.g., Min-Heap, Max-Heap)

2. Graphs

• Graphs are collections of nodes (vertices) connected by edges.
• Graphs can represent complex relationships and networks.
• Graphs come in various forms, such as directed and undirected graphs, weighted graphs, and sparse graphs.

3. Hash Tables

• Hash tables are data structues that store key-value pairs.
• They use a hash function to map keys to specific locations in an array.
• Hash tables provide fast average-time complexity for basic operations like insertion, deletion, and retrieval.