1.1 ~30 min easy

What Is a Data Structure?

A data structure is a way of organising data in memory so the operations you need are fast. Learn how they are classified and what makes a good one.

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental model

Think of a kitchen. You could throw every ingredient into one big box, but then finding the salt takes forever. So you use a spice rack (quick to grab by position), a fridge with shelves (grouped by type) and a stack of plates (you only ever take the top one). Same food, different organisation, and each one makes a different job fast.

A data structure is exactly that for a program: a way of storing and organising data in memory so that the operations we need are efficient.

How we classify them

Primitive: built into the language, holds one value: int, float, char, bool.
Non-primitive: built from primitives, holds a collection.
- Linear: items form a sequence; each has at most one “next”: arrays, linked lists, stacks, queues.
- Non-linear: one item can connect to many: trees, graphs.
Static vs dynamic (a separate question): is the size fixed when the program is compiled (array), or can it change while running (linked list, vector)?

Characteristics: what we do with a data structure

Every structure is judged by how well it supports a few standard operations: traversing (visit every item), searching, inserting, deleting, sorting and merging. When we analyse a structure, we ask “how much time and memory does each of these cost?”

Data structure vs algorithm

A data structure is the shelf; an algorithm is the recipe. Binary search (an algorithm) only works because the data sits in a sorted array (a data structure). Good programs pick both together.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

one of each kind35 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct Node {           // building block of a linked list (dynamic, linear)
    int data;
    Node* next;
};

int main() {
    int age = 20;                    // primitive
    char grade = 'A';                // primitive
    int marks[5] = {70, 85, 90, 65, 88};  // static, linear: size fixed at compile time

    vector<int> scores;              // dynamic, linear: grows at run time
    for (int m : marks) scores.push_back(m);
    scores.push_back(95);

    Node* second = new Node{2, nullptr};
    Node* head = new Node{1, second};  // 1 -> 2 -> nullptr

    stack<int> s;  s.push(1); s.push(2);   // linear ADT: last in, first out
    queue<int> q;  q.push(1); q.push(2);   // linear ADT: first in, first out

    cout << "age=" << age << " grade=" << grade << "\n";
    cout << "marks has fixed size " << sizeof(marks) / sizeof(marks[0]) << "\n";
    cout << "scores grew to " << scores.size() << "\n";
    cout << "list: " << head->data << " -> " << head->next->data << "\n";
    cout << "stack top=" << s.top() << ", queue front=" << q.front() << "\n";

    delete second;
    delete head;
}

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct Node {           // building block of a linked list (dynamic, linear)
    int data;
    Node* next;
};

int main() {
    int age = 20;                    // primitive
    char grade = 'A';                // primitive
    int marks[5] = {70, 85, 90, 65, 88};  // static, linear: size fixed at compile time

vector<int> scores;              // dynamic, linear: grows at run time
    for (int m : marks) scores.push_back(m);
    scores.push_back(95);

Node* second = new Node{2, nullptr};
    Node* head = new Node{1, second};  // 1 -> 2 -> nullptr

stack<int> s;  s.push(1); s.push(2);   // linear ADT: last in, first out
    queue<int> q;  q.push(1); q.push(2);   // linear ADT: first in, first out

cout << "age=" << age << " grade=" << grade << "\n";
    cout << "marks has fixed size " << sizeof(marks) / sizeof(marks[0]) << "\n";
    cout << "scores grew to " << scores.size() << "\n";
    cout << "list: " << head->data << " -> " << head->next->data << "\n";
    cout << "stack top=" << s.top() << ", queue front=" << q.front() << "\n";

delete second;
    delete head;
}

Expected output

age=20 grade=A
marks has fixed size 5
scores grew to 6
list: 1 -> 2
stack top=2, queue front=1

05Complexity

Array: read item i	O(1)
Array: insert at the front	O(n): shift everything
Linked list: insert at the front	O(1)
Linked list: read item i	O(n): walk from the head

There is no "best" data structure, only the best one for the operations you do most. This table is the whole reason the course exists.

06Watch

Introduction to data structures

mycodeschool · 6:33

Why this one: Six minutes that set up the whole course, including the ADT idea you meet next.

Watched

Original class slides (Python, by the course's lecture authors):Basic Data Structures

07Exam lens

Likely questions

Define a data structure. Give two examples of linear and two of non-linear data structures.
Differentiate between primitive and non-primitive data structures with examples.
What is the difference between static and dynamic data structures? Classify array and linked list.
List the characteristics (operations) of a data structure.

Common mistakes

Calling a stack "non-linear". Stacks and queues are linear; only trees and graphs are non-linear here.
Saying an array is dynamic. A C++ array has a fixed size; vector and linked lists are dynamic.
Confusing a data structure (how data is stored) with an algorithm (the steps that use it).

08Quick check

1.Which of these is a non-linear data structure?
2.An int marks[50]; in C++ is best described as:
3.Which structure can grow and shrink at run time one item at a time without copying?
4.Choosing a data structure mainly depends on…

09Practice

🟢 Trace by hand

Classify each as primitive/non-primitive, linear/non-linear, static/dynamic: char, int a[10], vector<string>, a family tree, a road map between cities, a printer queue.

Show answer

char: primitive
int a[10]: non-primitive, linear, static
vector<string>: non-primitive, linear, dynamic
family tree: non-primitive, non-linear (tree), usually dynamic
road map: non-primitive, non-linear (graph)
printer queue: non-primitive, linear (queue)

🟡 Implement it

Write a program that stores 5 temperatures in an array and the same values in a vector. Then add a 6th value to both. What happens with the array?

Hint

You cannot add a 6th element to double t[5]; writing t[5] is out of bounds. The vector just calls push_back.

🔴 Solve problems

Contains Duplicate easyleetcode.com
Hint
Compare a double loop over an array (O(n²)) with a set that remembers what you have seen (O(n)). Same problem, different data structure.

Solution idea
Insert each number into an unordered_set<int>; if it is already there, return true.
Two Sum easyleetcode.com
Hint
For each number x you need to know quickly whether target - x appeared before. Which structure answers "have I seen this?" in O(1)?

Solution idea
Use an unordered_map<int,int> from value to index while scanning once.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

I can define a data structure in one sentence.
I can draw the classification tree from memory.
I can classify any structure as linear/non-linear and static/dynamic.
I can explain why there is no single best data structure.

0/4 ticked

My notes

View as Markdown · Chapter cheat sheet