Unit 1: Introduction to Data Structures and

Algorithms
Data structures are systematic ways to organize and manage data so that it can be used efficiently. An
algorithm is a step-by-step procedure to solve a problem. Together, they form the backbone of efficient
programs 1 2 . Data structures determine how data is stored and accessed, while algorithms specify
how that data is processed. For example, a program can be thought of as Algorithm + Data Structure.
Effective use of data structures and algorithms leads to faster, more efficient software 1 .

Classification of Data Structures

Data structures are classified into two broad categories:

• Primitive Data Structures are basic built-in types provided by a language. Examples include
int , float , char , etc. Each holds a single value and is operated on directly by machine
instructions 3 .

• Non-Primitive Data Structures are derived from primitive types and can hold multiple values.
These include composite types like arrays, lists, files, etc. Non-primitive structures are further
divided into linear and non-linear structures 4 5 .

• Linear structures (e.g., arrays, linked lists, stacks, queues) arrange data sequentially. Each element
(except first and last) has a single predecessor and successor 5 .

• Non-linear structures (e.g., trees, graphs) do not arrange data in a single sequence; elements can
have multiple relationships (like branches in a tree) 6 .

Each type has its own use-cases and performance characteristics. For instance, an array is a fixed-size
sequence of elements of the same type, stored in contiguous memory locations 7 8 , while a tree or
graph represents hierarchical or network relationships.

Common Operations on Data Structures

Most data structures support a common set of operations that manipulate data. The main operations
include 9 10 :

• Search: Find a specific element in the structure.

• Traversal: Visit or iterate through all elements (e.g., printing all items in order).
• Insert: Add new elements (e.g., appending to a list or pushing onto a stack).
• Update: Modify existing elements’ values.
• Delete: Remove elements from the structure.
• Merge: Combine two data structures of the same type into one.
• Sort: Arrange elements in a defined order (ascending/descending).

These operations may be implemented differently depending on the structure. For example, adding an
element to a stack is called push, and removing one is pop. Likewise, queues allow enqueue (add) and

1
dequeue (remove) following FIFO order. Correct choice and implementation of these operations (and the
underlying structure) are crucial to program performance and correctness.

Arrays
An array is a fundamental linear data structure: it is a fixed-size sequenced collection of elements of the
same type 7 8 . Arrays are stored in contiguous memory locations, which means each element
immediately follows the previous in memory. This layout allows constant-time (O(1)) access to any
element via its index. For example, accessing arr[i] involves computing the address
base_address + i * sizeof(element_type) 7 11 .

For example, consider an integer array arr[5] = {10, 20, 30, 40, 50} starting at address
0x1000 . Each int might occupy 4 bytes, so element addresses would be:

arr[0] @ 0x1000 = 10
arr[1] @ 0x1004 = 20
arr[2] @ 0x1008 = 30
arr[3] @ 0x100C = 40
arr[4] @ 0x1010 = 50

Because of this contiguous layout, calculating the address of arr[i] is straightforward, and both
arr[i] and *(arr + i) access the same value 11 7 . The image above illustrates this
contiguous storage (indices on the left, memory addresses and values on the right) 7 .

Arrays have advantages like efficient indexing and cache performance, but also drawbacks: fixed size,
and expensive insertions/deletions in the middle (requiring shifts) 7 12 . In C, arrays are declared
simply (e.g., int arr[10]; ) and can be iterated with loops:

#include <stdio.h>
int main() {
int arr[3] = {5, 10, 15};
// Accessing elements
printf("%d\n", arr[0]); // 5
printf("%d\n", arr[2]); // 15
return 0;
}

This code defines a static array of 3 integers and prints its first and last elements.

Structures
A structure ( struct ) in C is a composite data type that groups variables of possibly different types
under a single name 13 . It allows heterogeneous data to be stored together as one unit. For example:

#include <stdio.h>
#include <string.h>

2
 // Define a structure to hold a person's data
struct Person {
char name[50];
int age;
float salary;
};

int main() {
struct Person person1;
// Assign values to person1
strcpy(person1.name, "Alice");
person1.age = 30;
person1.salary = 55000.0;
// Access and print structure members
printf("Name: %s\nAge: %d\nSalary: %.2f\n",
person1.name, person1.age, person1.salary);
return 0;
}

In this code, struct Person has three members: a char array, an int , and a float . One
Person instance person1 is created, its fields are set, and then printed. The structure members are
stored consecutively in memory (subject to padding), and accessed via the . operator (or -> if
through a pointer). Structures are useful for grouping related data (like database records, complex
objects, etc.) under one variable. Unlike arrays, structures can mix types and don’t require contiguous
memory for the same-type constraints 14 .

Unions
A union in C is similar to a structure but with a crucial difference: all members share the same
memory location 15 . A union can have multiple members of different types, but only one member can
hold a value at any given time. The size of the union is determined by its largest member 16 . For
example:

#include <stdio.h>

union Data {
int i;
float f;
char str[10];
};

int main() {
union Data data;
data.i = 10;
printf("data.i = %d\n", data.i);
data.f = 220.5;
printf("data.f = %.2f\n", data.f);
// Note: now data.i’s previous value is overwritten

3
 return 0;
}

In this program, setting data.f after data.i overwrites the same memory. Unions save memory
when you need to work with different types in the same variable at different times. They provide an
efficient way of using the same memory location for multiple purposes 17 . Unions are often used in low-
level programming, such as interpreting raw bytes or overlaying different data formats.

Pointers
A pointer is a variable that holds the memory address of another variable. In C, pointers enable direct
memory manipulation and are essential for dynamic data structures. As GfG explains: “A pointer is a
variable that stores the memory address of another variable. Instead of holding a direct value, it holds the
address where the value is stored in memory.” 18 . For example:

#include <stdio.h>

int main() {
int var = 42;
int *ptr = &var; // ptr points to var
printf("Address of var = %p\n", (void*)ptr);
printf("Value at ptr = %d\n", *ptr);
return 0;
}

Here ptr is declared as int * , so it can store the address of an int . The statement ptr =
&var; assigns it the address of var . Printing ptr shows the address, while *ptr (dereferencing)
yields the value 42 stored at that address 19 . Pointers can form complex structures (pointer to pointer,
dynamic allocation, etc.), and they are the backbone of C’s flexibility. The size of a pointer depends on
the system architecture (e.g., 4 bytes on 32-bit, 8 bytes on 64-bit 20 ). Pointers enable features like
dynamic arrays, linked data structures, and passing large data by reference.

Dynamic Memory Allocation

Dynamic memory allocation allows a program to request memory at runtime, rather than at compile
time. In C, the <stdlib.h> functions malloc() , calloc() , realloc() , and free() are used.
The malloc() function (memory allocation) reserves a block of memory of specified size and returns a
void* pointer to it 21 22 . For example:

int *arr = (int*) malloc(5 * sizeof(int));

if (arr != NULL) {
for(int i = 0; i < 5; i++) arr[i] = i+1;
// Use the array...
free(arr); // release when done
}

4
This code allocates space for 5 integers (20 bytes if sizeof(int)==4 ). If allocation fails, malloc
returns NULL , so good practice is to check it 23 22 .

calloc() (contiguous allocation) takes two arguments (number of elements and size of each) and
allocates zero-initialized memory. Its name reflects that it allocates contiguous blocks of memory and
initializes all bits to zero 24 25 . For example:

float *farr = (float*) calloc(10, sizeof(float));

// Allocates space for 10 floats, all initialized to 0.0

This differs from malloc() , which leaves memory uninitialized 26 .

When memory is no longer needed, free() should be called to deallocate it 27 . For instance, in the
malloc example above, free(arr) releases the allocated array. Without free , dynamically
allocated memory would be wasted (a “memory leak”).

If you need to resize a previously allocated block, realloc() is used 28 . For example, if you initially
allocate 5 ints but later need 10, you can do:

arr = (int*) realloc(arr, 10 * sizeof(int));

This attempts to resize the block pointed to by arr to hold 10 ints. If there is room, it expands in place;
otherwise it may move the block and return a new pointer 28 .

These dynamic allocation functions give C programs flexibility to use memory as needed at runtime
(e.g., when you don’t know array sizes beforehand) 22 28 .

Representation of Linear Arrays in Memory

Whether static or dynamic, linear arrays are stored contiguously in memory. This means each element’s
address follows a fixed formula. If an array’s base address is B, then the address of element arr[i] is
B + i*sizeof(type) . For example, if an int array starts at address 0x1000 , then arr[2]
would be at 0x1000 + 2*4 = 0x1008 11 7 . This contiguous layout allows efficient indexing but
also implies a fixed-size block (unless reallocated). A visual representation:

• arr[0] → address 0x1000

• arr[1] → address 0x1004
• arr[2] → address 0x1008
• and so on, if sizeof(int)=4 11 7 .

Using pointer arithmetic, an equivalent access of arr[i] is *(arr + i) . In C, one can allocate such
an array dynamically (as shown above) and access elements with either arr[i] or *(arr + i) 29

7 . Contiguous allocation yields O(1) access time, but growing or shrinking such arrays requires
reallocation or creating new blocks.

5
Stack and Queue (Linear Data Structures)
Stacks and queues are two important linear data structures that operate on specific insertion/deletion
rules:

• Stack: Follows Last-In First-Out (LIFO). The last element pushed onto the stack is the first one
popped off 30 . Think of a stack of plates – you put new plates on top ( push ), and you take
plates from the top ( pop ). For example, pushing 1, 2, 3 onto an empty stack, then popping once
yields 3 (the last pushed) 30 . The stack operations can be visualized as:
• Push: Add element at the top.
• Pop: Remove element from the top.
• Top/Peek: Look at the top element without removing.

The figure above depicts a stack: elements are stacked one above another, and only the top element is
accessible.

• Queue: Follows First-In First-Out (FIFO). The first element enqueued (inserted) is the first one
dequeued (removed) 31 . It is like a line of people: those who arrive first are served first. For
example, enqueuing 1, 2, 3 into an empty queue and then dequeuing once yields 1. The queue
operations are:
• Enqueue: Add element at the rear.
• Dequeue: Remove element from the front.
• Front/Peek: Look at the front element without removing.

The figure above illustrates a queue: elements enter from one end and leave from the other,
maintaining order of arrival.

Both stacks and queues can be implemented using arrays or linked lists. They are fundamental for
many algorithms (e.g. function call stack, breadth-first search) and have well-known complexity (push/
pop or enqueue/dequeue in O(1) time on average).

Algorithm Analysis
Understanding an algorithm’s efficiency is crucial. Time complexity and space complexity measure
how resource usage grows with input size.

• Time Complexity: The time complexity of an algorithm quantifies the amount of time it takes as
a function of input size 32 . It is usually expressed using Big-O notation (order of growth). For
example, if a loop runs n times, it is O(n). Time complexity ignores machine-specific constants,
focusing on how time grows as input grows 32 .

• Space Complexity: The space complexity of an algorithm quantifies the amount of memory it
uses as a function of input size 33 . This includes any extra space aside from the input. For
example, an algorithm that uses a fixed number of extra variables is O(1) space (constant),
whereas one that allocates an array of size n is O(n) 33 .

6
We also analyze best-case, worst-case, and average-case behavior:

• Worst-case describes the maximum time (upper bound) an algorithm can take on any input of
size n. It is most commonly used, since it guarantees an upper performance bound. For example,
linear search has worst-case O(n) when the item is not found 34 .
• Best-case describes the minimum time (lower bound) taken. For linear search, the best-case O(1)
when the item is at the first position 35 .
• Average-case takes an expected time over all possible inputs (assuming a probability
distribution). It is often difficult to compute. For linear search, under uniform distribution, the
average-case is ~O(n) 36 .

Importantly, we primarily use worst-case (upper bound) and express complexities in order of growth.
Big-O notation captures this growth: e.g., an algorithm taking at most 5n² + 3n + 2 steps is O(n²). The
order of growth abstracts away constants and lower-order terms to compare algorithms in a machine-
independent way 32 .

In summary, choosing the “best” algorithm often means the one with lower time and space complexity
for expected inputs. For exam purposes, focus on understanding how to derive these complexities and
what O(n), O(n²), etc. mean in best/worst contexts.

Important Exam Topics (Unit 1)

Students should pay special attention to the following high-priority topics from this unit:

• Data Structure & Algorithm Basics: Definitions of data, information, data structure, algorithm,
and their interplay (e.g. Program = Algorithm + Data Structure).
• Classification: Differences between primitive vs. non-primitive structures; linear vs. non-linear
data structures. Examples of each category (array, list, tree, graph, etc.) 3 5 .
• Operations on Data Structures: Key operations such as create, insert, delete, search, update,
traverse, sort, merge. Knowing what each operation does conceptually 9 10 .
• Arrays: Definition and properties (fixed size, contiguous memory) 7 8 . How to declare,
initialize, and access array elements in C. Advantages/disadvantages of arrays.
• Structures vs Unions: Structure layout vs union layout in memory. When to use each. Syntax for
defining and accessing struct and union members 14 17 .
• Pointers: Pointer syntax ( * , & ), pointer arithmetic, and dereferencing. Role of pointers in
arrays and dynamic memory 19 .
• Dynamic Memory Allocation: Functions malloc() , calloc() , free() , realloc() :
purposes, syntax, and examples 22 25 27 28 . Understanding of NULL check and memory
leaks.
• Memory Representation: How arrays (especially linear arrays) are laid out in memory;
computing element addresses; concept of contiguous allocation 7 11 .
• Complexity Analysis: Definitions of time and space complexity; Big-O notation; best/worst/
average case examples (e.g., linear search, simple loops) 32 34 . Understanding order of growth.

Mastery of these concepts, including being able to write and trace simple C code for arrays, structures,
pointers, and dynamic allocation, is essential for exam success.

7
Practice Questions
Theory Questions (define, explain, compare):

1. (Easy) What is a data structure? Explain with one example 2 1 .

2. (Easy) List the primitive data types in C. Why are they called “primitive”? 3
3. (Medium) Differentiate between linear and non-linear data structures. Give two examples of
each 5 6 .
4. (Medium) Name and briefly explain three common operations on data structures. (e.g.,
search, insert, delete) 9 .
5. (Easy) What is an array? List two advantages and two disadvantages of using arrays 7 37 .
6. (Medium) Explain how a structure is defined in C. How does it differ from an array? 14
7. (Medium) Describe a union in C. How does the memory layout of a union differ from that of a
struct? 17
8. (Hard) What is a pointer? Explain the difference between an uninitialized pointer, a NULL
pointer, and a dangling pointer 19 .
9. (Easy) What does malloc do? Contrast it with calloc . Include syntax 22 25 .
10. (Hard) What is the time complexity of accessing an element in an array? Explain using the
concept of contiguous memory 7 11 .
11. (Medium) Define best-case, worst-case, and average-case complexity. Why is worst-case often
used in analysis? 34 35
12. (Hard) Explain Big-O notation (“order of growth”) with an example. Why do we ignore
constant factors? 32 34

Coding Questions (write C code):

1. (Easy) Write a C program that declares an integer array of size 5, initializes it with values 1–5, and
prints each element.
2. (Easy) Define a struct for a 2D point with x and y coordinates. In main , create a point,
assign values to its fields, and print them.
3. (Medium) Write a C snippet that allocates an array of n floats dynamically using malloc , reads
values from the user into the array, then frees the memory. Include error checking for malloc .
4. (Medium) Given the union:

union U { int i; float f; };

Write code that sets i = 100 , then prints i , then sets f = 3.14 and prints f . (Observe
and comment on what happens to i .) 17

5. (Hard) Write a function in C that takes a pointer to the first element of an int array and its
length, and returns the sum of its elements using pointer arithmetic (no array indexing).
6. (Medium) Demonstrate pointer-to-pointer: declare an int , a pointer to it, and a pointer to that
pointer. Print the values and addresses at each level.
7. (Hard) Write a C function that uses realloc to expand an integer array from size n to size
2*n , preserving existing elements. Show how it is called in main .
8. (Medium) Implement a simple stack of integers using an array and functions push and pop .
(Assume a fixed max size and track the top index.) Include a brief test in main that pushes and
pops a few values.

Each question is tagged with difficulty (easy/medium/hard) to help prioritize study. Writing and testing
these code examples will reinforce understanding of the concepts.

8
 1 DSA Tutorial - Learn Data Structures and Algorithms - GeeksforGeeks
https://www.geeksforgeeks.org/dsa/dsa-tutorial-learn-data-structures-and-algorithms/

2 8 11 29 DDS UNIT 1.pdf

file://file-RTsHZ7xA7wSVcAjWxM3knX

3 4 5 6 9 10 Introduction to Data Structures - TechVidvan

https://techvidvan.com/tutorials/introduction-to-data-structures/

7 12 37 Applications, Advantages and Disadvantages of Array - GeeksforGeeks

https://www.geeksforgeeks.org/dsa/applications-advantages-and-disadvantages-of-array-data-structure/

13 14 C struct (Structures)
https://www.programiz.com/c-programming/c-structures

15 16 17 C Unions Explained
https://www.tutorialspoint.com/cprogramming/c_unions.htm

18 19 20 C Pointers - GeeksforGeeks
https://www.geeksforgeeks.org/c/c-pointers/

21 23 24 Dynamic Array in C - GeeksforGeeks

https://www.geeksforgeeks.org/c/dynamic-array-in-c/

22 25 26 27 28 C Dynamic Memory Allocation Using malloc(), calloc(), free() & realloc()

https://www.programiz.com/c-programming/c-dynamic-memory-allocation

30 Stack Data Structure - GeeksforGeeks

https://www.geeksforgeeks.org/dsa/stack-data-structure/

31 Queue Data Structure - GeeksforGeeks

https://www.geeksforgeeks.org/dsa/queue-data-structure/

32 33 Time and Space Complexity - GeeksforGeeks

https://www.geeksforgeeks.org/dsa/time-complexity-and-space-complexity/

34 35 36 Worst, Average and Best Case Analysis of Algorithms - GeeksforGeeks

https://www.geeksforgeeks.org/dsa/worst-average-and-best-case-analysis-of-algorithms/