Data Structures

Data Structures and Abstract Data Types (ADT) Explained Simply

If you have ever searched for a file on a messy desktop and then found it in two seconds on a tidy one, you already understand the main idea of this lecture. The files did not change. Only the way they were arranged changed.

That is what data structures are about. By the end of this article you will know:

what a data structure is and why the choice matters,
what an Abstract Data Type (ADT) is, and how it differs from a data structure,
how one Stack ADT can be built in two different ways without the user noticing,
how data structures are divided into linear and non-linear types.

Grab a notebook. The Stack code below is worth typing out yourself.

What is a data structure?

A data structure is a way of organizing and storing data so that we can use it efficiently.

Think of a bookshop. The same 5,000 books can be dumped in a pile in the middle of the floor, or placed on shelves sorted by subject and then by author. The books are identical. But finding “Introduction to Algorithms” takes ten seconds in one shop and ten minutes in the other.

Programs work the same way. Data is rarely the problem. How you arrange it decides whether your program is quick or painfully slow.

You already know one data structure: the array. Here are the four we will meet in this course, with a picture to keep in mind for each:

Structure	Picture it as
Array	Boxes in a row, each with a number
Linked list	Items chained together, each one pointing to the next
Stack	A pile of plates: you only touch the top one
Queue	People standing in a line at a bank

Why the choice of structure matters

Let’s make it concrete with your phone’s contact list. Say you have 1,000,000 contacts (a big business, or a very social person).

How contacts are stored	How you find “Usman”	Speed
Random order	Check every contact one by one	Slow
Sorted by name	Jump to roughly the right place	Fast
Sorted, using the “dictionary trick”	Open in the middle, decide left or right, repeat	Very fast

In the worst case, the random list needs up to 1,000,000 checks. The dictionary trick (which you will meet later as binary search) needs about 20. Same data, same phone, 50,000 times fewer steps.

So a good data structure gives you two things: faster programs and less memory use. Choosing the right one for the job is the single most important skill in this course.

Exam tip: When a question says “justify your choice of data structure”, it wants you to talk about the operations the problem needs (searching? adding at the end? removing from the top?) and which structure does those cheaply.

What is an Abstract Data Type (ADT)?

This is the idea students most often mix up, so let’s go slowly.

An Abstract Data Type (ADT) describes what you can do with data, not how it is done inside. It is basically a list of operations: a contract.

Your TV remote is the perfect example. You know that the red button switches the TV off and that “+” raises the volume. You have no idea what circuit sits inside the remote. And you don’t need to. If the company redesigns the inside tomorrow, your remote still works the same way in your hand.

That is the power of an ADT:

The ADT is the WHAT. The list of operations the user is allowed to call.
The implementation is the HOW. The actual array, linked list or whatever sits underneath.
The inside can change without the user ever noticing.

A second example: a bank ATM. The ADT is “check balance, withdraw, deposit”. Whether the bank stores your account in an old system or a new cloud database is none of your business, and the ATM screen stays the same.

Data structure vs ADT: the difference in one line

An ADT tells you what operations exist. A data structure is how you actually store the data to make those operations work.

A Stack is an ADT. An array or a linked list can be the data structure that implements it.

Example: the Stack ADT

Imagine a pile of plates in a canteen. You add a plate on top, and you take a plate from the top. Nobody pulls one from the middle. That is a stack.

The same idea is all around you:

the Undo button in a text editor (the last change you made is the first one undone),
the Back button in a browser (the last page you opened is the first you go back to).

The Stack ADT promises exactly four operations:

Operation	What it does
`push(x)`	Add `x` on top
`pop()`	Remove and return the top item
`peek()`	Look at the top item without removing it
`isEmpty()`	Tell whether the stack has nothing in it

In C++, the “contract” looks like this:

cpp

class Stack {
public:
    void push(int x);
    int  pop();
    int  peek();
    bool isEmpty();
};
// WHAT, not HOW

Notice there is nothing in it about arrays or pointers. It only says what the stack can do.

One ADT, two implementations

Now the interesting part. Let’s build the same Stack in two different ways and then use both with exactly the same code.

Version 1: using an array

cpp

#include <iostream>
using namespace std;

class ArrayStack {
    int data[100];
    int top;                       // index of the top item, -1 means empty
public:
    ArrayStack() : top(-1) {}

    void push(int x) {
        if (top == 99) { cout << "Stack is full\n"; return; }
        data[++top] = x;
    }
    int pop() {
        if (isEmpty()) { cout << "Stack is empty\n"; return -1; }
        return data[top--];
    }
    int peek() {
        return isEmpty() ? -1 : data[top];
    }
    bool isEmpty() { return top == -1; }
};

Version 2: using a linked list

cpp

struct Node {
    int value;
    Node* next;
};

class ListStack {
    Node* head;                    // head is always the top of the stack
public:
    ListStack() : head(nullptr) {}
    ~ListStack() { while (!isEmpty()) pop(); }

    void push(int x) {
        head = new Node{x, head};  // new node points to the old top
    }
    int pop() {
        if (isEmpty()) { cout << "Stack is empty\n"; return -1; }
        Node* old = head;
        int v = old->value;
        head = old->next;
        delete old;
        return v;
    }
    int peek() {
        return isEmpty() ? -1 : head->value;
    }
    bool isEmpty() { return head == nullptr; }
};

(To keep things short, both versions return -1 when the stack is empty. In real projects you would throw an exception instead.)

The user code: identical for both

cpp

template <typename S>
void runDemo(S& s) {
    s.push(10);
    s.push(20);
    s.push(30);
    cout << "Top: "    << s.peek() << "\n";
    cout << "Popped: " << s.pop()  << "\n";
    cout << "Popped: " << s.pop()  << "\n";
    cout << "Empty? "  << (s.isEmpty() ? "yes" : "no") << "\n";
}

int main() {
    ArrayStack a;
    ListStack  l;
    cout << "--- Array version ---\n";
    runDemo(a);
    cout << "--- Linked list version ---\n";
    runDemo(l);
    return 0;
}

(Don’t worry about the template line yet. It only lets us hand either stack to the same function. Focus on the lines inside runDemo.)

Output

--- Array version ---
Top: 30
Popped: 30
Popped: 20
Empty? no
--- Linked list version ---
Top: 30
Popped: 30
Popped: 20
Empty? no

Look carefully at runDemo. It never says “array” or “pointer”. It just calls push, pop, peek and isEmpty. We could swap the whole inside of the stack and this function would not need a single change. That is an ADT doing its job.

From our class: Remember when we studied functions and wrote a square function? We wrote it once, and after that we simply called it. square(4) gave 16, square(9) gave 81. Only the input changed, and we never had to rewrite the code. The caller did not care how the function worked inside (a multiplication, a loop, anything else). It only cared about the promise: give me a number, get its square back.

An ADT is the same idea at a bigger scale. Instead of one function making a promise, a whole set of operations (push, pop, peek, isEmpty) makes the promise. Change what is inside, and the code that uses it stays untouched.

Types of data structures: the map of this course

All data structures fall into two big families.

Linear data structures: items sit one after another, in a line. Examples: array, linked list, stack, queue.

Non-linear data structures: items connect in branches or in a network. Examples: tree, graph.

A simple way to remember it: your queue at a bank counter is linear. Everyone has exactly one person in front and one behind. Your family tree is non-linear: one person connects to several children, who each connect to more. That is a tree. And Google Maps is a graph: a road network where one city connects to many others in many directions.

                 Data Structures
                /               \
            Linear            Non-linear
   (Array, Linked list,        (Tree, Graph)
     Stack, Queue)

Over the next lectures we will go down this map one branch at a time.

Common mistakes students make

Saying “ADT and data structure are the same thing.” They are related, not equal. ADT is the what, data structure is the how.
Thinking an ADT is a piece of code. An ADT is a description of behaviour. Code (a class, for instance) is one way to write it down.
Memorising the Stack operations without the idea. If you understand “only the top is accessible”, you can rebuild push, pop and peek in any exam.
Mixing up linear and non-linear. Linear means arranged in a sequence, not “stored in a straight memory block”. A linked list is linear even though its nodes can be scattered in memory.

From our class: One day I asked a student, “What is an algorithm?” She answered, “Step of plain language.” He knew the idea, but the answer was wrong. The correct definition is “steps in plain language”, meaning a sequence of steps written in simple words. By saying “step of” instead of “steps in”, she changed the meaning of the whole sentence. “Step of plain language” sounds like a single step that belongs to some language, which is not what an algorithm is.

This happens a lot in exams. Changing one word (ADT for data structure, linear for non-linear, “what” for “how”) can turn a correct answer into a wrong one. So do not memorise the sound of a definition. Understand it, and then write it carefully.

Summary

A data structure organises data so it can be used efficiently.
The right choice makes programs faster and lighter.
An ADT defines the operations (what). The implementation decides how.
The Stack ADT has push, pop, peek, isEmpty, and it can be built with an array or a linked list without the user changing a line of code.
Data structures are either linear (array, linked list, stack, queue) or non-linear (tree, graph).

Quick check

Try answering these before you scroll down:

What is the difference between a data structure and an ADT?
Name the four operations of the Stack ADT.
Is a tree linear or non-linear?

Ready to test yourself?

Reading is only half of learning. Now check what you actually remember.

Take the quiz: Data Structures and ADT →

If you get a question wrong, come back to the matching section above. Use the headings as your revision map.

Frequently asked questions

Is a stack an ADT or a data structure? Both views are used. As a list of operations (push, pop, …) it is an ADT. When you build it using an array or linked list, you have a data structure that implements the ADT.

Why do we need ADTs at all? Because they let you change the inside of a program without breaking the rest. Teams can also work in parallel: one person uses the stack, another builds it.

Which is better for a stack, array or linked list? It depends. An array is simple and fast but has a fixed size in our example. A linked list grows as needed but uses extra memory for pointers. We compare them properly in the upcoming lectures on complexity.

Do I need to learn all data structures right now? No. This lecture is the map. We will walk each branch one lecture at a time.

Next lecture: Complexity Analysis and Big-O.

Written by Engnr.Dr. Muhammad Tahir Dlbar.