October 17, 2026

Module 1: Introduction to Data Structures

Introduction

Data Structures and Algorithms (DSA) is a fundamental subject in computer science and programming. It explains how data is organized, stored, accessed, and processed efficiently.

Every software application works with data. For example, a college management system stores student records, an e-commerce website manages products and orders, and a banking application maintains customer accounts and transactions.

When data becomes large, managing it efficiently becomes challenging. Data structures provide systematic ways to organize information, while algorithms define the steps required to process that information.

In this module, you will learn the fundamentals of data structures, their types, Abstract Data Types (ADTs), time and space complexity, and Big O notation.

1. What Is a Data Structure?

A data structure is a way of organizing and storing data in a computer so that it can be accessed, processed, modified, and managed efficiently.

In simple terms, a data structure determines how data elements are arranged and how operations can be performed on them.

For example, suppose a teacher wants to store the marks of five students. Creating five separate variables can work, but managing a larger number of marks becomes inconvenient. An array allows multiple values of the same data type to be stored under a single variable name.

Example: Using an Array in C

#include 

int main(void) {
    int marks[5] = {85, 90, 78, 88, 92};

    for (int i = 0; i < 5; i++) {
        printf("Student %d: %d\n", i + 1, marks[i]);
    }

    return 0;
}

Output:

Student 1: 85
Student 2: 90
Student 3: 78
Student 4: 88
Student 5: 92

Explanation

• int marks[5] declares an array capable of storing five integers.

• The five values are initialized when the array is declared.

• The for loop accesses each element using its index.

• marks[i] retrieves the value at the current index.

Array indexing in C starts from zero. Therefore, the first element is marks[0], and the last element is marks[4].

This example demonstrates how a data structure can organize related values and make them easier to process.

Common Operations on Data Structures

Most data structures support some combination of the following operations:

• Traversal: Visiting each element.

• Insertion: Adding a new element.

• Deletion: Removing an element.

• Searching: Finding a particular element.

• Updating: Modifying an existing value.

• Sorting: Arranging elements in a specified order.

• Merging: Combining two collections of data.

The available operations and their efficiency depend on the data structure being used.

2. Why Are Data Structures Used?

Data structures are used to organize data and perform operations efficiently. Choosing the right structure can improve a program's performance, readability, and maintainability.

2.1 Efficient Data Access

Different data structures provide different ways to retrieve information.

For example, an array supports direct access to an element when its index is known. A linked list generally requires traversal from a node to reach an element at a particular position.

2.2 Efficient Insertion and Deletion

Some structures make certain insertion and deletion operations easier than others.

For example, inserting an element at the beginning of a linked list can take constant time when a pointer to the head is available. Inserting at the beginning of an array may require shifting existing elements.

2.3 Better Memory Utilization

Different data structures use memory in different ways.

Arrays store elements in contiguous memory locations, whereas linked lists typically use separately allocated nodes connected through pointers.

The appropriate choice depends on the size of the data, allocation requirements, and operations performed.

2.4 Improved Searching and Processing

Suitable data structures can reduce the amount of work required to find or process information.

For example, binary search can find an element in a sorted array in (O(\log n)) time, whereas linear search may require examining every element and takes (O(n)) time in the worst case.

2.5 Managing Complex Relationships

Some applications contain hierarchical or interconnected information.

• Trees represent hierarchical relationships.

• Graphs represent networks and connections.

• Queues manage items waiting for processing.

• Stacks manage operations that follow the Last In, First Out principle.

• Hash tables support efficient average-case lookup using keys.

2.6 Real-World Applications

Data structures are used in:

• Student and employee management systems

• Banking and financial applications

• Inventory and e-commerce systems

• Operating systems and process scheduling

• Web browsers and undo functionality

• Maps, navigation, and route planning

• Databases and search systems

The main objective is not simply to store data, but to store it in a form that supports the operations an application needs.

3. Types of Data Structures

Data structures can be classified in several ways. A common introductory classification distinguishes primitive and non-primitive structures, followed by linear and non-linear structures.

3.1 Primitive Data Structures

Primitive data types are the basic types provided by a programming language.

Examples in C include:

• char — represents a character.

• int — represents an integer.

• float — represents a floating-point value.

• double — represents a floating-point value with greater precision than float.

Pointers are also a fundamental C language type used to store memory addresses.

These types provide the building blocks for creating more complex data structures.

3.2 Non-Primitive Data Structures

Non-primitive data structures organize data using multiple elements or relationships.

They are commonly divided into linear and non-linear structures.

Linear data structures arrange elements in a sequence.

Examples:

• Arrays

• Linked lists

• Stacks

• Queues

Non-linear data structures organize elements hierarchically or through more complex connections.

Examples:

• Trees

• Graphs

Hash tables are another important data structure, organized around keys and hash functions.

3.3 Static and Dynamic Data Structures

Data structures can also be discussed in terms of how their storage is allocated and managed.

Static-size structures: Their capacity is fixed for the lifetime of the structure. A typical fixed-size array in C is an example.

Dynamic structures: Their storage can be allocated and released during program execution. Linked lists built using dynamically allocated nodes are a common example.

A dynamically allocated array in C can also be created, although its allocated size does not automatically grow when more elements are added.

3.4 Overview of Common Data Structures

No single data structure is best for every problem. Its suitability depends on the operations, memory requirements, and constraints of the application.

4. Linear vs Non-Linear Data Structures

One of the most important classifications in DSA is the difference between linear and non-linear data structures.

Linear Data Structures

A linear data structure organizes elements in a sequence. Each element generally has a predecessor and successor, except at the boundaries, although some implementations may have additional links.

Examples include arrays, linked lists, stacks, and queues.

Characteristics:

• Elements follow a sequential organization.

• Traversal often follows a predictable order.

• The structure is suitable for lists, sequences, and ordered processing.

• Access methods depend on the specific implementation.

Non-Linear Data Structures

A non-linear data structure organizes elements hierarchically or through multiple relationships rather than one simple sequence.

Examples include trees and graphs.

Characteristics:

• An element can be connected to multiple other elements.

• Hierarchical or network relationships can be represented.

• Traversal may require specialized algorithms.

• The structure can represent complex relationships efficiently.

Comparison

Example

Consider a list of student marks:

85 → 90 → 78 → 88

This sequence can be represented using an array or linked list.

Now consider an organization with a manager, department heads, and employees. This hierarchy can be represented using a tree.

The difference lies in how the data elements are related, rather than simply in how many elements are stored.

5. Abstract Data Types (ADT)

An Abstract Data Type (ADT) is a logical description of a data type that defines the data it represents and the operations supported on that data, without requiring a particular implementation.

In simple terms, an ADT specifies what operations are available, while the implementation determines how those operations work internally.

For example, a stack ADT typically supports:

• push — add an element.

• pop — remove the top element.

• peek — inspect the top element.

• isEmpty — check whether the stack contains elements.

The stack can be implemented using an array or a linked list. Both implementations can provide the same logical behavior.

ADT vs Data Structure

Example: Stack ADT in C

The following code demonstrates a simple stack implemented using an array.

#include 

#define MAX 5

typedef struct {
    int data[MAX];
    int top;
} Stack;

void initialize(Stack *s) {
    s->top = -1;
}

int isEmpty(const Stack *s) {
    return s->top == -1;
}

int isFull(const Stack *s) {
    return s->top == MAX - 1;
}

int push(Stack *s, int value) {
    if (isFull(s)) {
        return 0;
    }

    s->data[++s->top] = value;
    return 1;
}

int pop(Stack *s, int *value) {
    if (isEmpty(s)) {
        return 0;
    }

    *value = s->data[s->top--];
    return 1;
}

int main(void) {
    Stack s;
    int value;

    initialize(&s);

    push(&s, 10);
    push(&s, 20);

    if (pop(&s, &value)) {
        printf("Removed: %d\n", value);
    }

    return 0;
}

Output:

Removed: 20

This example illustrates the stack's LIFO behavior: the last element inserted, 20, is removed first.

The ADT defines the stack's expected behavior. The array, top variable, and functions provide one possible implementation.

6. Time and Space Complexity

When analyzing an algorithm, it is important to understand how its resource requirements change as the input size increases.

Time complexity describes how the number of computational steps grows with the input size.

Space complexity describes how memory requirements grow with the input size.

Both are commonly expressed using asymptotic notation, such as Big O.

6.1 Time Complexity

Suppose an algorithm processes (n) elements.

An algorithm that examines each element once generally performs work proportional to (n), resulting in (O(n)) time.

An algorithm that uses two nested loops, each running approximately (n) times, may perform work proportional to (n^2), resulting in (O(n^2)) time.

Example: Linear Traversal

#include 

int main(void) {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

The loop visits every element exactly once. If the array contains (n) elements, the loop performs (n) iterations.

Therefore:

• Time complexity: (O(n))

• Auxiliary space complexity: (O(1)), because the loop uses a constant amount of extra memory.

The array itself occupies (O(n)) space, but it is the input in this example. When analyzing auxiliary space, input storage is normally excluded.

6.2 Space Complexity

Space complexity concerns the memory used by an algorithm as input size grows.

For practical analysis, it is useful to distinguish total space from auxiliary space.

Total space complexity includes the memory required to represent the input as well as the additional memory used by the algorithm.

Auxiliary space complexity refers to the additional memory used by the algorithm, excluding the input storage.

For example, an algorithm that creates a second array of (n) elements uses (O(n)) auxiliary space. An algorithm that uses only a few additional variables uses (O(1)) auxiliary space.

Example: Constant Auxiliary Space

int sumArray(const int arr[], int n) {
    int sum = 0;

    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }

    return sum;
}

The function processes each element once and uses a fixed number of additional variables.

• Time complexity: (O(n))

• Auxiliary space complexity: (O(1))

6.3 Common Complexity Classes

These are common growth rates, not guarantees for every algorithm with a particular name. Actual complexity depends on the algorithm and its input conditions.

6.4 Best, Average, and Worst Cases

An algorithm's performance may vary depending on the input.

• Best case: The minimum amount of work required for an input of size (n).

• Average case: The expected amount of work under a specified input distribution.

• Worst case: The maximum amount of work required for an input of size (n).

For example, linear search has:

• Best-case time: (O(1)), when the target is the first element.

• Worst-case time: (O(n)), when the target is at the end or absent.

• Average-case time: (O(n)) under the usual assumption that the target is equally likely to occur at any position.

Complexity analysis helps programmers compare algorithms and choose appropriate solutions.

7. Big O Notation

Big O notation describes an asymptotic upper bound on the growth of an algorithm's resource requirements as the input size increases.

It is widely used to discuss time and space complexity. In introductory algorithm analysis, it is often used to express an algorithm's worst-case growth rate.

Big O focuses on the dominant growth term rather than exact execution time. It ignores constant factors and lower-order terms when describing asymptotic growth.

7.1 Examples of Big O

Consider the following expressions:

• (O(1)): Constant growth.

• (O(n)): Linear growth.

• (O(n^2)): Quadratic growth.

• (O(\log n)): Logarithmic growth.

For example, if an algorithm performs approximately (3n + 5) operations, its asymptotic growth is (O(n)).

Similarly, an expression such as (4n^2 + 3n + 10) has a dominant quadratic term, so its growth is (O(n^2)).

7.2 Example: Constant Time

int getFirst(const int arr[]) {
    return arr[0];
}

Assuming the array is valid and non-empty, the function accesses a single element regardless of the array's length.

Time complexity: (O(1)).

7.3 Example: Linear Time

int findValue(const int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }

    return -1;
}

The function checks elements sequentially until the target is found or the array ends.

• Best case: (O(1)).

• Worst case: (O(n)).

• Auxiliary space: (O(1)).

7.4 Example: Quadratic Time

void printPairs(const int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("(%d, %d)\n", arr[i], arr[j]);
        }
    }
}

The outer loop runs (n) times, and for every outer iteration, the inner loop also runs (n) times.

The total number of pairs printed is (n \times n = n^2).

Time complexity: (O(n^2)).

The function uses (O(1)) auxiliary space, excluding output and runtime buffering.

7.5 Rules for Simplifying Big O Expressions

Rule 1: Ignore constant factors

(O(5n)) simplifies to (O(n)).

Rule 2: Keep the dominant term

(O(n^2 + n + 1)) simplifies to (O(n^2)).

Rule 3: Add sequential operations

If one operation takes (O(n)) and another takes (O(n^2)), their combined complexity is (O(n + n^2) = O(n^2)).

Rule 4: Analyze nested loops carefully

Two independent loops that each run (n) times usually perform (2n) iterations in total, giving (O(n)) time. Two nested loops that each run (n) times usually perform (n^2) iterations, giving (O(n^2)) time.

7.6 Big O, Big Omega, and Big Theta

Big O is not the only asymptotic notation used in algorithm analysis.

For example, the function (3n + 5) is in (O(n)), (\Omega(n)), and (\Theta(n)) for sufficiently large (n).

Big Theta is useful when both upper and lower bounds grow at the same rate. Big O is especially common when discussing worst-case performance.

7.7 Why Big O Matters in DSA

Big O notation helps programmers:

• Compare algorithms independently of specific hardware.

• Estimate how an algorithm will scale with larger inputs.

• Identify inefficient solutions.

• Choose suitable data structures and algorithms.

• Understand the trade-offs between running time and memory usage.

For example, linear search has (O(n)) worst-case time, while binary search has (O(\log n)) worst-case time on a sorted array. As input size grows, binary search generally requires far fewer comparisons, provided its sorted-input requirement is satisfied.

Summary

In this module, we covered the fundamental concepts required to begin studying Data Structures and Algorithms.

• A data structure organizes and manages data.

• Data structures support operations such as traversal, insertion, deletion, searching, and updating.

• Common structures include arrays, linked lists, stacks, queues, trees, graphs, and hash tables.

• Linear structures arrange elements sequentially, while non-linear structures represent hierarchical or interconnected relationships.

• An Abstract Data Type defines behavior and supported operations independently of a specific implementation.

• Time complexity describes how computational work grows with input size.

• Space complexity describes memory requirements, including the distinction between total and auxiliary space.

• Big O notation expresses an asymptotic upper bound on growth and helps compare algorithm efficiency.

Understanding these concepts provides the foundation for learning arrays, searching, sorting, linked lists, stacks, queues, trees, graphs, hashing, and algorithm design.