Data Structures

Welcome

This page is the permanent home of our Data Structures course. Bookmark it. Everything I teach in class — notes, complete programs, assignments and deadlines — will be published here, lesson by lesson, as we reach each topic.

You do not need to buy a book, and you do not need a laptop. What you need is a phone, the willingness to type out every program yourself, and the patience to sit with an idea until it makes sense. I will supply the rest.

A data structure is not a definition to memorise. It is a decision you make about how to arrange your data — and every decision has a price.

Set up CxxDroid before the next class

We will write and run real C++ throughout this course. So that no student is held back by equipment, all of our programs are designed to compile and run on an Android phone using a free app called CxxDroid.

1. Open the Google Play Store on your Android phone.
2. Search for CxxDroid — C/C++ compiler IDE and install it.
3. Open the app once and let it finish downloading its compiler package — it needs internet only for this first step, and only once.
4. Tap New file, choose a C++ source file, and type the program below.
5. Press the Run button (the ▶ icon). If you see the greeting printed, your setup is complete.

#include <iostream>
using namespace std;

int main() {
    cout << "Data Structures - ready to begin." << endl;
    return 0;
}

How to submit your work

Every assignment in this course is submitted as a C++ source file — that is, a file ending in .cpp. Never send a screenshot, a photograph of your screen, a Word document, or a PDF. I need to compile and run what you wrote.

• In CxxDroid, save your program with the exact file name I ask for in the assignment.
• Find the file on your phone (CxxDroid keeps its files in an easily accessible folder — the app shows you the path when you save).
• Write your name and roll number in a comment at the top of the file, before any code.
• Submit it in the manner I announce in class — the submission method for each assignment will be given during the lecture, along with the deadline.

What is a data structure?

A data structure is a deliberate way of organising data in a computer's memory so that the operations you care about become cheap.

Notice the last part of that sentence, because it is the whole subject in miniature: the operations you care about. There is no best data structure. There is only the structure that suits what you intend to do.

Think of a library. If the books are arranged alphabetically by title, finding The Republic takes seconds — but shelving a new book means shifting hundreds of others along. If instead you simply place each new book wherever there is space, shelving becomes instant, and finding anything becomes a nightmare. Same books, same shelves. A different arrangement, and a completely different set of costs.

That trade — fast lookup versus fast insertion, memory versus speed, simplicity versus flexibility — is what we will study for the whole semester.

What we will cover this term

• Arrays — fixed, contiguous, instantly indexable. Our starting point.
• Linked lists — flexible in size, but you must walk to reach anything.
• Stacks and queues — restricted access, used everywhere in real systems.
• Trees — hierarchy, and searching by repeatedly halving the problem.
• Graphs — relationships, networks, and paths between them.
• Hashing, sorting and searching — the workhorse algorithms that tie it all together.

Why we use C++

Many languages will hide memory from you. C++ will not, and that is precisely why it is the right language for this course. When you write int marks[5]; in C++, you are asking for five integers laid out side by side in memory — and you can see the consequences of that request in the behaviour of your program.

• Memory is visible. Arrays, addresses and pointers behave the way the machine actually behaves.
• Nothing is done for you. You will implement each structure yourself, which is the only way to truly learn it.
• It is the standard. C++ remains the common language of data structures courses, competitive programming and university examinations.

You are expected to already know the basics from your programming course: variables, the if statement, loops, and functions. If any of that is shaky, revise it this week — we build directly on top of it.

Topic 1 — Arrays

An array is a fixed-size collection of elements of the same type, stored in one unbroken block of memory, one after another.

Three words in that sentence do all the work:

• Fixed-size — you decide the length when you create it, and it cannot grow afterwards.
• Same type — an array of int holds only integers. No mixing.
• Contiguous — element 0, element 1, element 2 sit next to each other in memory, with no gaps.

Why contiguity is the whole trick

Because every element is the same size and they are packed together, the computer can calculate the exact location of any element with one piece of arithmetic:

address of marks[i]  =  address of marks[0]  +  ( i × size of one element )

It does not matter whether you ask for element 2 or element 2,000 — it is the same single multiplication and addition. This is why we say array access takes constant time. It is also, as you will see, the source of everything an array is bad at.

Indexing starts at zero

In C++, the first element of an array is at index 0, not 1. An array of size 5 therefore has valid indices 0, 1, 2, 3, 4 — and index 5 does not exist.

Declaring and initialising an array

Type this program into CxxDroid and run it. Do not copy it mentally — type it. Then change a number and run it again, and see what happens.

#include <iostream>
using namespace std;

int main() {
    // 1. Declare and initialise together
    int marks[5] = {85, 92, 78, 64, 90};

    // 2. Declare first, assign later
    int scores[3];
    scores[0] = 10;
    scores[1] = 20;
    scores[2] = 30;

    // 3. Let the compiler count the elements for you
    int values[] = {4, 8, 15, 16, 23, 42};

    // 4. Fill every element with zero
    int empty[5] = {0};

    // Reading a single element is instant, whatever the index
    cout << "First mark : " << marks[0] << endl;
    cout << "Third mark : " << marks[2] << endl;
    cout << "Last mark  : " << marks[4] << endl;

    // Writing to an element is just as cheap
    marks[1] = 95;
    cout << "Updated second mark : " << marks[1] << endl;

    // The other three arrays work exactly the same way
    cout << "scores[2] : " << scores[2] << endl;
    cout << "values[5] : " << values[5] << endl;
    cout << "empty[0]  : " << empty[0]  << endl;

    return 0;
}

How big is my array, really?

C++ does not store the length of a plain array for you, so a common trick is to ask the compiler how many bytes it occupies and divide by the size of one element.

#include <iostream>
using namespace std;

int main() {
    int values[] = {4, 8, 15, 16, 23, 42};

    int totalBytes = sizeof(values);      // whole array, in bytes
    int oneBytes   = sizeof(values[0]);   // one element, in bytes
    int length     = totalBytes / oneBytes;

    cout << "Bytes in array   : " << totalBytes << endl;
    cout << "Bytes per int    : " << oneBytes << endl;
    cout << "Number of items  : " << length << endl;

    return 0;
}

Traversing an array

Traversal means visiting every element exactly once. It is the foundation of almost everything else you will do with an array: printing, summing, searching, finding the largest value.

#include <iostream>
using namespace std;

int main() {
    int marks[5] = {85, 92, 78, 64, 90};
    int n = 5;                  // number of elements we are using

    // --- Print every element ---
    cout << "All marks: ";
    for (int i = 0; i < n; i++) {
        cout << marks[i] << " ";
    }
    cout << endl;

    // --- Sum and average ---
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum = sum + marks[i];
    }
    double average = (double) sum / n;

    cout << "Sum     : " << sum << endl;
    cout << "Average : " << average << endl;

    // --- Highest and lowest ---
    int highest = marks[0];
    int lowest  = marks[0];

    for (int i = 1; i < n; i++) {
        if (marks[i] > highest) highest = marks[i];
        if (marks[i] < lowest)  lowest  = marks[i];
    }

    cout << "Highest : " << highest << endl;
    cout << "Lowest  : " << lowest << endl;

    return 0;
}

Arrays and pointers

There is a second way to walk an array, and it explains what indexing has been doing all along. Before we write it, let us settle a sentence you will hear repeated in every classroom: "the name of an array is a pointer to its first element."

That is almost right — right enough to be useful, wrong in exactly the places that cause bugs. Here is the accurate version.

What the array name really is

The name marks is the name of the whole block of five integers. Its type is "array of 5 int", not "pointer to int". An array is an object of its own; a pointer is a separate variable that stores an address.

However — and this is the part everyone remembers — whenever you use an array name in an expression, C++ automatically converts it into a pointer to its first element. The rule has a name: array-to-pointer conversion, informally called decay. So in nearly every line you will ever write:

marks   becomes   &marks[0]   of type   int*

The array name is not a pointer; it turns into one on use. Keep that distinction and the exceptions below stop being surprises.

Indexing is pointer arithmetic in disguise

The C++ standard defines the subscript operator in terms of pointers. The expression marks[i] is defined to mean *(marks + i) — "start at the first element, move forward i elements, and read what is there". Every time you have written marks[2] in this lesson, that is what the compiler produced.

Crucially, marks + 1 does not add one byte. Pointer arithmetic counts in elements: the compiler knows each int is 4 bytes, so marks + 1 moves 4 bytes, and marks + 3 moves 12. The type of the pointer decides the size of the step.

#include <iostream>
using namespace std;

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

    // Used in an expression, the array name gives the address of element 0.
    cout << "marks     : " << marks     << endl;
    cout << "&marks[0] : " << &marks[0] << endl;   // the very same address

    // Indexing is defined as pointer arithmetic
    cout << "marks[2]     : " << marks[2]     << endl;
    cout << "*(marks + 2) : " << *(marks + 2) << endl;   // identical

    // Adding 1 moves one ELEMENT, not one byte
    cout << "Bytes per int : " << sizeof(int) << endl;
    cout << "marks     : " << marks     << endl;
    cout << "marks + 1 : " << marks + 1 << endl;   // 4 bytes further on

    // But the name is NOT a pointer, and sizeof proves it
    int *p = marks;                       // p is a real pointer variable
    cout << "sizeof(marks) : " << sizeof(marks) << endl;   // 20 - the whole array
    cout << "sizeof(p)     : " << sizeof(p)     << endl;   // 4 or 8 - one pointer

    return 0;
}

Traversing with a pointer

Because a pointer variable can be moved, you can walk the array by advancing the pointer itself rather than by counting an index. All four loops below print the same five numbers.

#include <iostream>
using namespace std;

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

    // --- Style 1: move the pointer itself ---
    cout << "Moving pointer      : ";
    for (int *p = marks; p < marks + n; p++) {
        cout << *p << " ";
    }
    cout << endl;

    // --- Style 2: keep a fixed pointer, add an offset ---
    int *base = marks;
    cout << "Fixed base + offset : ";
    for (int i = 0; i < n; i++) {
        cout << *(base + i) << " ";
    }
    cout << endl;

    // --- Style 3: the array name itself, with an offset ---
    cout << "Array name + offset : ";
    for (int i = 0; i < n; i++) {
        cout << *(marks + i) << " ";
    }
    cout << endl;

    // --- Style 4: the ordinary index, which was all of the above anyway ---
    cout << "Plain index         : ";
    for (int i = 0; i < n; i++) {
        cout << marks[i] << " ";
    }
    cout << endl;

    // Summing with a walking pointer
    int sum = 0;
    for (int *p = marks; p != marks + n; p++) {
        sum = sum + *p;
    }
    cout << "Sum : " << sum << endl;

    // Subtracting two pointers gives the number of elements between them
    int *first = marks;
    int *afterLast = marks + n;
    cout << "Length : " << (afterLast - first) << endl;

    return 0;
}

Three places where the name is not a pointer

If an array name were truly a pointer, all three rows below would behave differently. This table is the whole difference, and it is worth memorising.

Why this matters: passing an array to a function

Look back at linearSearch(int arr[], int n, int target) from earlier — and at the fact that we always pass n alongside the array. Now you know why.

When an array is passed to a function, the parameter is adjusted to a pointer. These three declarations are identical to the compiler, and in every one of them arr is a pointer:

• void show(int arr[5], int n)
• void show(int arr[], int n)
• void show(int *arr, int n)

Two consequences follow, and both are important. The array is never copied — only its address travels — so a function can change the caller's data. And the length is lost at the door, which is why it must be handed over as a separate argument.

#include <iostream>
using namespace std;

// 'arr' arrives as a pointer, however we spell the parameter.
void show(int *arr, int n) {
    cout << "Address inside function : " << arr << endl;

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";        // still works: arr[i] is *(arr + i)
    }
    cout << endl;

    arr[0] = 100;                      // this edits the ORIGINAL array
}

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

    cout << "Address inside main     : " << marks << endl;
    cout << "Bytes inside main       : " << sizeof(marks) << endl;

    show(marks, 5);                    // only the address is passed

    cout << "marks[0] afterwards     : " << marks[0] << endl;

    return 0;
}

Run it. The two addresses match, and marks[0] is 100 when the function returns — proof that the function was working on your array, not on a copy of it.

The array name decays to a pointer to the first element. It is not a pointer; it becomes one the moment you use it.

Core operations on an array

Four operations matter: access, search, insert and delete. You have already seen access. Here are the other three, written out in full.

Linear search

To find a value in an unsorted array, you have no choice but to look at the elements one by one until you find it or run out of array.

#include <iostream>
using namespace std;

// Returns the index of 'target', or -1 if it is not present.
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

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

    cout << "Enter the mark to find: ";
    cin >> target;

    int position = linearSearch(marks, 5, target);

    if (position == -1) {
        cout << "Not found in the array." << endl;
    } else {
        cout << "Found at index " << position << endl;
    }

    return 0;
}

Insertion — and why it hurts

Here is the price of contiguity. To insert a value in the middle of an array, every element after that position must shift one place to the right to make room. And because the array cannot grow, you must declare it with spare capacity from the start.

#include <iostream>
using namespace std;

int main() {
    const int CAPACITY = 10;              // room for growth
    int arr[CAPACITY] = {10, 20, 30, 40, 50};
    int n = 5;                            // elements currently in use

    int value = 25;                       // value to insert
    int pos = 2;                          // index it should end up at

    // Shift everything from the end down to 'pos' one step right
    for (int i = n; i > pos; i--) {
        arr[i] = arr[i - 1];
    }

    arr[pos] = value;
    n++;                                  // the array is now one longer

    cout << "After inserting " << value << " at index " << pos << ": ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Deletion

Deletion is the mirror image: everything after the removed element shifts one place to the left to close the gap.

#include <iostream>
using namespace std;

int main() {
    int arr[10] = {10, 20, 25, 30, 40, 50};
    int n = 6;

    int pos = 2;                          // index to remove

    // Shift everything after 'pos' one step left
    for (int i = pos; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    n--;                                  // the array is now one shorter

    cout << "After deleting index " << pos << ": ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

What each operation costs

We measure cost by counting how the work grows as the array gets bigger — not in seconds, which depend on the machine. Here n is the number of elements. We will define this notation properly in a later lesson; for now, read O(1) as "instant, whatever the size" and O(n) as "the work grows in step with the size".

Read that table as a personality, not a list. An array is superb at reading and poor at rearranging. So use one when your data is a fixed collection you will read constantly and change rarely — the marks of a class, the pixels of an image, the days of a week. When you need constant insertion and removal instead, you need a different structure, and that is exactly where our next lesson begins.

Five mistakes to avoid

1. Going out of bounds. Writing to marks[5] in an array of five elements. C++ will not stop you — it will quietly corrupt whatever memory sits there, and your program may crash much later, somewhere that looks unrelated.
2. Forgetting that indices start at 0. The third element is arr[2]. Say it aloud a few times this week.
3. Using i <= n in a loop. One extra step, one invalid element, one hard bug.
4. Assuming an array can grow. int a[5]; is five elements forever. If you may need more, declare the capacity you need up front.
5. Reading elements you never assigned. An uninitialised array does not contain zeros; it contains whatever was left in that memory. Always initialise.

Assignment 1 — Arrays

Write a single C++ program that does all of the following, in this order. Use one array and one value of n throughout; do not write six separate programs.

1. Ask the user how many marks they wish to enter (call it n, where n is at most 20).
2. Read n marks from the user into an array.
3. Print all the marks on one line, separated by spaces.
4. Print the sum and the average of the marks.
5. Print the highest and the lowest mark, together with the index at which each was found.
6. Ask the user for a mark to search for, then report either the index where it was found or a clear "not found" message. Use a linearSearch function for this, not a loop inside main.
7. Print the array in reverse order.
8. Count and print how many marks are above the average.

Start from this skeleton, and fill in every section marked TODO:

// Data Structures - Assignment 1: Arrays
// Name    :
// Roll No :
// Class   :

#include <iostream>
using namespace std;

// Returns the index of 'target' in arr, or -1 if it is not present.
int linearSearch(int arr[], int n, int target) {
    // TODO: write the search here
    return -1;
}

int main() {
    int marks[20];
    int n;

    cout << "How many marks? ";
    cin >> n;

    // TODO 1: read n marks from the user

    // TODO 2: print all the marks on one line

    // TODO 3: calculate and print the sum and the average

    // TODO 4: find and print the highest and lowest marks, with their indices

    // TODO 5: ask for a mark to search for and use linearSearch()

    // TODO 6: print the array in reverse order

    // TODO 7: count and print how many marks are above the average

    return 0;
}

How this is marked

What comes next

In the next lesson we take the weakness we uncovered today — that inserting and deleting in an array means shifting everything else — and solve it. That solution is the linked list, and it comes with a cost of its own: you lose instant access by index. Trading one cost for another is the pattern you will see again and again.

Come to class having installed CxxDroid and having run at least the traversal program above. Notes for Lesson 2 will appear on this page after we cover it.