A data structure is a way of organizing, storing, and managing data in a computer so that it can be accessed and used efficiently. It provides a systematic way to store and organize data to perform various operations like searching, insertion, deletion, and updating data quickly and effectively.

In simple terms, data structures are like containers for data. Just like how you might store items in different types of boxes or containers depending on the items (e.g., a stack for plates, a queue for customers), data structures define how data should be stored and accessed in a program.

Common Types of Data Structures:

1. Array: A collection of elements stored in a contiguous memory block. Elements are accessed by their index.
   • Example: [1, 2, 3, 4, 5]
2. Linked List: A collection of elements (nodes) where each node points to the next one in the sequence. It allows for efficient insertion and deletion of elements.
   • Example: 1 → 2 → 3 → 4 → 5
3. Stack: A collection that follows the “Last In, First Out” (LIFO) principle. The last element added is the first to be removed.
   • Example: Plates stacked on top of each other.
4. Queue: A collection that follows the “First In, First Out” (FIFO) principle. The first element added is the first to be removed.
   • Example: People standing in line.
5. Tree: A hierarchical structure with a root element and child nodes. It’s often used to represent hierarchical data like file systems.
   • Example: A family tree.
6. Graph: A collection of nodes (vertices) connected by edges. It’s used to represent relationships like social networks, road maps, etc.
   • Example: A network of friends, where each person (node) is connected to others (edges).
7. Hash Table: A structure that stores key-value pairs, providing fast lookups based on the key. It’s commonly used in database indexing.
   • Example: A dictionary where you look up a word (key) to get its meaning (value).

Importance of Data Structures:

• Efficiency: The right data structure can optimize the performance of various operations like searching, insertion, and deletion.
• Organization: Data structures help in organizing data in a way that makes it easier to work with and manipulate.
• Resource Management: Efficient data structures help in managing memory and other system resources effectively.

Advantages of data structures

• Data structures like stacks and queues make it easy to add, remove, or find data quickly.
• Using the right data structure makes programs run faster by improving tasks like searching, adding, or deleting data.
• Data structures like trees and graphs organize data in a way that makes it easy to understand connections or relationships.
• Some data structures, like linked lists, only use memory when needed, which helps save space.

Data Structure Terminology

• Data Structure: A data structure is a way to store and organize data so that we can use it efficiently. Think of it as a container or a system for organizing and managing data in a program.
• Element: An element is a single piece of data stored in a data structure. For example, in an array, each number or word is an element.
• Array: An array is a collection of elements that are stored in a continuous block of memory. All elements in an array are of the same type, like a list of numbers or words.
• Linked List: A linked list is a data structure where each element (called a node) contains data and a reference (or link) to the next element in the sequence. It’s like a chain where each link points to the next.
• Node: A node is an individual element in a data structure like a linked list or tree. It contains data and sometimes links to other nodes.
• Stack: A stack is a type of data structure where data is added and removed in a “last in, first out” (LIFO) order. It’s like a stack of plates; you add and remove plates from the top.
• Queue: A queue is a data structure where data is added and removed in a “first in, first out” (FIFO) order. It’s like a line at a grocery store, where the first person in line is the first to be served.
• Tree: A tree is a data structure that consists of nodes connected by edges. It starts with a root node and branches out to child nodes. It’s often used to represent hierarchical relationships, like a family tree.
• Binary Tree: A binary tree is a type of tree where each node has at most two children (left and right). It’s like a decision tree with two options at each level.
• Graph: A graph is a collection of nodes (vertices) and edges (connections between nodes). It’s used to represent networks, like social media connections or road maps.
• Hash Table: A hash table is a data structure that stores key-value pairs. It allows fast retrieval of data using a key. It’s like a dictionary where you look up a word (key) to get its definition (value).
• Key: A key is a unique identifier used in a hash table to access the corresponding value. For example, in a phonebook, the person’s name is the key, and their phone number is the value.
• Value: A value is the data that is stored in a data structure. In a hash table, the value is the information that corresponds to a key.
• Algorithm: An algorithm is a step-by-step process or set of rules used to perform a task, like searching for an element in an array or sorting a list.

Classification of Data Structure

This diagram shows the different types of data structures, which are ways to organize and store data in a computer.

1. Primitive Data Structures (Basic types)
2. Non-Primitive Data Structures (Advanced types)

1. Primitive Data Structures (Basic Data Types)

• Primitive data structures are the simplest types of data used in programming. These are the basic building blocks for storing information.
• Some common types of primitive data:

• Integer (Int) → Used to store whole numbers like 1, 10, -50.
• Float → Used to store decimal numbers like 3.14, 2.5.
• Double → Similar to float but can store more precise decimal numbers.

These are simple data types because they store only one value at a time.

2. Non-Primitive Data Structures (Advanced Data Types)

• Non-primitive data structures are more complex. They can store multiple values and organize data efficiently.
• There are two types of non-primitive data structures: They are linear and non-linear

Linear Data Structures (Data in a Sequence)

• Linear data structures store data in a straight line or sequence. You can imagine them like a queue at a store or a stack of books.

Types of Linear Data Structures:

• There are 4 types of linear data these are Array, Linked List, Queue, and Stack

1. Array → A collection of items stored in a fixed order.
   • Example: A list of student names [John, Sarah, Alex, Emma].
   • Arrays have a fixed size, meaning once you set the number of items, you can’t change it easily.
2. Linked List → A series of connected items where each item points to the next one.
   • Example: Think of a chain where each link is connected to the next.
   • Unlike an array, a linked list can grow or shrink as needed.
3. Queue → A structure that follows the First In, First Out (FIFO) rule.
   • Example: A queue at a ticket counter. The first person who joins the line is the first to leave.
   • Used in job scheduling, customer service systems, etc.
4. Stack → A structure that follows the Last In, First Out (LIFO) rule.
   • Example: A stack of plates. The last plate placed on top is the first one you remove.
   • Used in undo-redo functions, browser history, etc.

Nonlinear Data Structure and Its Types 

A nonlinear data structure is one where data elements are not stored in a sequential manner (like arrays or linked lists). Instead, they are arranged in hierarchical or interconnected relationships. These structures help in efficient searching, sorting, and data organization in complex applications.

• There are two types of nonlinear data structures, and these are tree and graphs.

1. Trees

• A tree is a non-linear data structure consisting of nodes connected by edges. 
• Each node contains a value or data, and each edge represents a relationship between nodes.
• The topmost node is called the root node, through which all other nodes are accessed.
• Trees represent hierarchical relationships like family trees or organizational charts.
• They are used for efficient data searching; binary search trees are used for large databases.
• Trees have applications in computer science and programming.

Tree-Type Data Structure: Basic Terminologies

1. Tree
   A tree is a way to organize data that looks like a tree in nature—starting from the top (called the root) and branching down.
2. Node
   Each point in a tree is called a node. It can hold some data.
3. Root Node
   The root is the very top node in a tree. It doesn’t have any parent. It’s like the starting point.
4. Child Node
   A child is a node that comes from another node (its parent). A node can have one or more children.
5. Parent Node
   A parent is any node that has a branch to one or more child nodes.
6. Leaf Node
   A leaf is a node that has no children. It’s like the last stop on a branch.
7. Subtree
   A subtree is any smaller tree within a bigger tree. If you pick any node and its children, that’s a subtree.
8. Edge
   An edge is the line or connection between two nodes (like between parent and child).
9. Level
   The level of a node means how far it is from the root. The root is level 0, its children are level 1, and so on.
10. Height
    The height of a tree is the number of levels from the root to the lowest leaf.
11. Depth
    The depth of a node is how far down it is from the root. It’s the same as its level.
12. Binary Tree
    A binary tree is a special tree where each node can have up to 2 children (left and right).

2.Graphs

A graph is a nonlinear data structure that consists of a set of nodes (also called vertices) connected by edges. Graphs are powerful tools used to represent and solve problems involving networks, relationships, and connections.

• We can represent every edge by two elements of the set. A graph is represented by G(V, E) where V= set of vertices and E= set of edges. Vertices are also known as nodes.
• For example, the following diagram depicts a graph:

• Here, V = {a, b, c, d, e} and E = {e1, e2, e3, e4, e5, e6} or E = {ab, bc, bd, ad, de, ce}.
• A graph can be unidirectional or directional. In unidirectional graph, edge do not have dirctions whereas in directional graph edges do have directions.
•  Undirected graph: An undirected graph is the one in which there is no direction associated with the edges. In an undirected graph, traversal from A→B is the same as that of B→A. the following graph is undirected:

• Directional graphgraph: a directed graph is the one in which we have ordered pairs and the direction matters. Thus, in a directed graph, A→B is not the same as B→A. The following graph is a directed graph.

Comparison between Linear and Non-Linear Data Structures.

 Basic Operations on Data Structures

Basic operations on data structures refer to fundamental actions that help in managing and processing data efficiently. These operations are common to almost all data structures, including arrays, linked lists, stacks, queues, trees, graphs, and hash tables.

 1. Insertion:Definition:

Insertion refers to adding a new element to the data structure. The location where the new element is inserted depends on the type of data structure.

Examples:

• Array: Insert an element at a specific index.
• Linked List: Insert a node at the beginning, middle, or end.
• Stack: Push a new element onto the top.
• Queue: Enqueue an element at the rear.
• Tree: Insert a node following the tree’s insertion rules (e.g., Binary Search Tree).

Time Complexity:

• O(1) for stack, queue (when inserted at the end without shifting).
• O(n) for arrays (when inserting in the middle, due to shifting).
• O(log n) for balanced trees (Binary Search Tree insertion).

Example Code: (Insert in an array at a specific position)

#include <iostream>
using namespace std;
void insertAtPosition(int arr[], int &size, int element, int pos) {
    for (int i = size; i > pos; i--)
        arr[i] = arr[i - 1]; // Shift elements to the right
    arr[pos] = element;
    size++;
}
int main() {
    int arr[10] = {1, 2, 3, 5, 6}, size = 5, element = 4, pos = 3;
    insertAtPosition(arr, size, element, pos);
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
}

Output: 1 2 3 4 5 6

2 Deletion:Definition:

Deletion removes an element from a data structure. The method of deletion varies depending on the structure being used.

Examples:

• Array: Remove an element by shifting the rest.
• Linked List: Remove a node and adjust the links.
• Stack: Pop the top element.
• Queue: Dequeue the front element.
• Tree: Delete a node, possibly restructuring the tree.

Time Complexity:

• O(n) for arrays (shifting needed).
• O(1) for stack and queue.
• O(log n) for balanced trees (deleting a node).

Example Code: (Delete from an array at a specific position)

#include <iostream>
using namespace std;
void deleteAtPosition(int arr[], int &size, int pos) {
    for (int i = pos; i < size - 1; i++)
        arr[i] = arr[i + 1]; // Shift elements to the left
    size--;
}
int main() {
    int arr[10] = {1, 2, 3, 4, 5}, size = 5, pos = 2;
    deleteAtPosition(arr, size, pos);
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
}

Output: 1 2 4 5

3 Traversal:Definition:

Traversal means visiting each element in a data structure. It is used to process data, display values, or search for elements.

Examples:

• Array: Access elements sequentially using a loop.
• Linked List: Move through each node using pointers.
• Tree: Use in-order, pre-order, or post-order traversal.
• Graph: Use Breadth-First Search (BFS) or Depth-First Search (DFS).

Time Complexity:

• O(n) for arrays, linked lists.
• O(n) for tree traversals.
• O(V + E) for graphs (where V = vertices, E = edges).

Example Code: (Traverse a linked list and print elements)

#include <iostream>
using namespace std;
struct Node {
    int data;
    Node* next;
};
void printList(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
int main() {
    Node* head = new Node{1, new Node{2, new Node{3, NULL}}};
    printList(head);
}

Output: 1 2 3

4 Searching:Definition:
Searching finds an element in a data structure. The method of searching depends on how the data is organized.

Types:

• Linear Search: Check each element sequentially (O(n)).
• Binary Search: Works on sorted data, and divides the array in half each time (O(log n)).

Example Code: (Binary Search in a Sorted Array)

#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return mid;
        else if (arr[mid] < key) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
int main() {
    int arr[] = {1, 3, 5, 7, 9}, size = 5, key = 5;
    int result = binarySearch(arr, 0, size - 1, key);
    cout << (result != -1 ? "Found" : "Not Found");
}

Output: Found

5 Sorting:Definition:

Sorting arranges elements in a specific order (ascending/descending).

Common Algorithms:

• Bubble Sort – O(n²)
• Selection Sort – O(n²)
• Insertion Sort – O(n²)
• Merge Sort – O(n log n)
• Quick Sort – O(n log n)

Example Code: (Bubble Sort in C++)

#include <iostream>
using namespace std;
void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++)
        for (int j = 0; j < size - i - 1; j++)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}
int main() {
    int arr[] = {5, 1, 4, 2, 8}, size = 5;
    bubbleSort(arr, size);
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
}
Output: 1 2 4 5 8

6 Updating:Definition:

Updating modifies an existing element’s value in a data structure.

Example: (Update an array element at a given index)

#include <iostream>
using namespace std;
void updateElement(int arr[], int pos, int newValue) {
    arr[pos] = newValue;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    updateElement(arr, 2, 10);
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
}
Output: 1 2 10 4 5

Application of data Structure

• Data structures are fundamental for organizing and manipulating data efficiently, which is crucial for building complex software systems. 
• Data structures like linked lists are used to implement other data structures like stacks, trees, queues, and graphs. 
• Stacks are used for managing memory allocation for temporary variables and function calls. 
• Data structures are essential for designing efficient algorithms for various tasks, such as searching, sorting, and graph traversal. 
• Data structures like hash tables and trees are used to organize and store data efficiently in databases, enabling fast retrieval and manipulation. 
• Data structures like queues are used in operating systems for managing processes, handling interrupts, and controlling I/O operations.