What is a data structure?

A data structure is a specialized format for organizing, processing, retrieving, and storing data in computer memory. It defines the relationships between data items and the operations that can be performed on them, ensuring efficient CPU and memory utilization.

1. Linear Data Structures

Definition

A linear data structure arranges elements sequentially in a single line, where each element is connected directly to its previous and next adjacent elements.

Types

• Arrays: Fixed-size sequential collections of elements stored in contiguous memory locations.

• Linked Lists: Collections of nodes linked via pointers, stored non-contiguously in memory.

• Stacks: Last-In, First-Out (LIFO) structures where insertion and deletion occur at a single end (top).

• Queues: First-In, First-Out (FIFO) structures where elements enter at the rear and exit from the front.

Detailed Breakdown

In linear structures, data traversal is straight and predictable—elements are processed in a single run. Accessing an element in a static array takes O(1) constant time using an index formula:

In dynamic lists like linked lists, elements contain data along with memory addresses pointing to the next node, allowing dynamic resizing at the cost of O(n) access time.

Code Examples (Linear Structures)

C++ (Array Implementation)

#include <iostream>

int main() {
    int numbers[5] = {10, 20, 30, 40, 50};
    
    // Direct O(1) index access
    std::cout << "Element at index 2: " << numbers[2] << std::endl; 
    return 0;
}

Python (Linked List Node Definition)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Creating linked nodes
head = Node(10)
head.next = Node(20)
print(f"Head: {head.data}, Next: {head.next.data}")

Java (Stack Implementation)

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(100);
        stack.push(200);
        
        System.out.println("Popped element (LIFO): " + stack.pop()); // 200
    }
}

2. Non-Linear Data Structures

Definition

A non-linear data structure connects elements hierarchically or in interconnected networks, where a single element can link to multiple other elements without a direct sequential order.

Types

• Trees: Hierarchical, acyclic structures with a root node, parent nodes, and child nodes (e.g., Binary Search Trees, Heaps).

• Graphs: Networks composed of vertices (nodes) connected by edges (relationships), which can be directed, undirected, weighted, or unweighted.

Detailed Breakdown

Non-linear structures reflect complex relationships such as file systems, network routing tables, and social graphs. Elements cannot be traversed in a single pass; instead, traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS) are required. Searching in a balanced Binary Search Tree (BST) achieves logarithmic time complexity:

Code Examples (Non-Linear Structures)

C++ (Binary Tree Node)

#include <iostream>

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    
    std::cout << "Root: " << root->data << ", Left: " << root->left->data << std::endl;
    return 0;
}

Python (Graph via Adjacency List)

# Representing a graph network
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

print("Nodes connected to A:", graph['A'])

Java (Binary Search Tree Node)

class BSTNode {
    int value;
    BSTNode left, right;

    public BSTNode(int item) {
        value = item;
        left = right = null;
    }
}

public class Main {
    public static void main(String[] args) {
        BSTNode root = new BSTNode(50);
        root.left = new BSTNode(30);
        System.out.println("Root Value: " + root.value);
    }
}

3. Abstract Data Types (ADTs)

Definition

An Abstract Data Type (ADT) is a theoretical model for data structures that defines what operations can be performed on the data without specifying how those operations are implemented in code.

Types

• List ADT: Defines operations like add(), get(), remove().

• Map / Dictionary ADT: Defines key-value association operations like put(key, value), get(key).

• Priority Queue ADT: Defines queueing where elements are removed based on priority order using insert() and deleteMin().

Detailed Breakdown

ADTs act as contracts between the programmer and the underlying implementation. For instance, the Map ADT guarantees that keys map to unique values. Internally, a Map can be implemented using a Hash Table (O(1) average access time) or a Red-Black Tree (O(log n) guaranteed access time).

Explore More IT Terms