# 1.1 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.

Chapter: Introduction to Data Structures · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/what-is-a-data-structure

## Mental 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.

## C++ code: one of each kind

```cpp
#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:

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

## Complexity

| Case | Cost |
| --- | --- |
| 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.

## Videos

- [Introduction to data structures](https://youtu.be/92S4zgXN17o) (mycodeschool): Six minutes that set up the whole course, including the ADT idea you meet next.

## Exam 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).

## Quick check

1. Which of these is a **non-linear** data structure?
   A. Queue
   B. Stack
   C. Tree
   D. Array
   Answer: C. In a tree, one node can lead to several children. Queue, stack and array are all sequences.

2. An `int marks[50];` in C++ is best described as:
   A. Primitive and dynamic
   B. Non-primitive, linear and static
   C. Non-primitive, non-linear and dynamic
   D. Primitive and static
   Answer: B. An array holds many values (non-primitive), in a sequence (linear), with a size fixed at compile time (static).

3. Which structure can grow and shrink at run time one item at a time without copying?
   A. A plain C++ array
   B. A linked list
   C. A 2-D array
   D. An `int`
   Answer: B. Each linked-list node is created with `new` and removed with `delete` when needed.

4. Choosing a data structure mainly depends on…
   A. how many lines of code it needs
   B. which operations must be fast
   C. the programming language
   D. whether it is linear
   Answer: B. Arrays give O(1) indexing, linked lists give O(1) front insertion, and so on. Pick for your most frequent operations.

## Practice

**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.

Solution:

- `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`.

**Problems:**

- [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) (easy). 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.
- [Two Sum](https://leetcode.com/problems/two-sum/) (easy). 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)?

## Mastery checklist

- [ ] 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.