The vocabulary of data structures
Before building anything, learn the words: what a data structure is, how they are classified, what an ADT hides, and how to choose one.
After this lesson
You should be able to
- Name the standard operations performed on data structures.
- Classify a data structure as linear or non-linear, static or dynamic.
- Explain what an abstract data type hides and why that matters.
A data structure is data plus the operations on it
You already know one data structure well: the array from your C course. A data structure is any way of arranging data in memory together with the operations that work on that arrangement. The arrangement alone is not enough — an array without the idea of indexing is just bytes.
Six operations come up again and again across every structure you will meet this semester: traversing (visiting every element), searching (finding one), inserting, deleting, sorting, and merging. Learning a new structure mostly means learning how it does these six differently from the last one.
Two classifications worth knowing early
Linear versus non-linear: in a linear structure, each element has at most one predecessor and one successor — an array, a linked list, a stack, a queue. In a non-linear structure, an element can connect to several others — a tree, a graph. This unit stays entirely linear; trees and graphs are Units II and IV.
Static versus dynamic: an array's size is fixed once allocated. A linked list can grow and shrink one node at a time while the program runs. That single difference is what the next three lessons are really about.
The abstract data type: what, not how
An ADT specifies what operations are available and what they do, without saying how they are implemented. A stack ADT promises push, pop, and peek with last-in-first-out behaviour. Whether push is implemented with an array or a linked list is an implementation detail the ADT deliberately hides.
This hiding is the entire point. Code written against the stack ADT — call push, call pop — keeps working unchanged if you later swap the array implementation for a linked-list one. You will build exactly that swap across the next several lessons.
/* The ADT: what a stack promises */
void push(int value);
int pop(void);
int peek(void);
int is_empty(void);
/* Two different "how"s could sit behind these four signatures:
an array with a top index, or a linked list with a head pointer.
Calling code never needs to know which. */Choosing a structure
Ask which operations you need often. If you mostly look up values by position and rarely insert or delete, an array's direct indexing wins. If you insert and delete constantly and rarely need a specific position, a linked list avoids the shifting an array would require.
Also ask whether the final size is known in advance. Known and fixed favours an array; unknown or frequently changing favours a dynamic structure. Every remaining lesson in this unit is really an answer to 'what if the size is not known'.
Try it yourself
A college wants to store roll numbers for a fixed class of 60 students, read frequently by position and never resized. A separate system stores a live queue of support tickets that grows and shrinks all day. Which structure family fits each, and why?
Need a hint?
Match each scenario against the static/dynamic and frequent-operation questions from this lesson.
Check the worked solution
The roll number list is static and read-heavy by position, which is exactly an array's strength — direct indexing, no wasted pointer memory. The ticket queue is dynamic with unpredictable size and constant insertion/removal at the ends, which is what the rest of this unit builds towards. Neither answer requires code yet; naming the right structure family is the actual skill being practised.
Quick check
What does an abstract data type deliberately hide from the code that uses it?
Why this lesson exists
Syllabus mapping
Basic Terminology · Classification of Data Structures · Operation on Data Structures · abstract data types · selecting a Data Structure
Maps to course outcome CO1.