Difficulty: Intermediate | Prerequisites: Computer Programming and Language Categories notes, Structured Programming notes
Data structures are how you organise and store data so that operations on it (searching, sorting, inserting, deleting) are efficient. This topic builds on your understanding of programming fundamentals and control structures. Nearly every algorithm you will study later in the course operates on one or more data structures, so having a solid grasp of what each structure is, how it works, and when to use it is essential. If arrays, stacks, and linked lists are unfamiliar, this is where to start.
A data structure is a way of collecting and organising data so you can perform operations on it efficiently. The major types include arrays, linked lists, stacks, queues, trees, graphs, heaps, records, strings, lists, and pointers. Each has its own strengths: arrays give fast indexed access, stacks enforce last-in-first-out order, queues enforce first-in-first-out order, and trees allow hierarchical organisation.
Data structure
A way of collecting and organising data so that operations on it can be performed efficiently. Data structures render data elements in terms of some relationship for better organisation and storage. Think of it as the filing system for your data: the choice of system determines how quickly you can find, add, or remove information.
Array
A data structure that stores a fixed-size sequential collection of elements of the same type. Elements are accessed by an index (also called a subscript or key). In simple terms, it is a numbered row of boxes, each holding the same kind of item.
Index (subscript, key)
The identifier used to access a specific element within an array. Indexes map array positions to stored objects.
Tree
A hierarchical data structure with a root value and subtrees of children, each with a parent node, represented as a set of linked nodes. Think of it as an upside-down family tree: one root at the top, branches below.
Stack
A data structure where objects are inserted and removed according to the last-in, first-out (LIFO) principle. Only two operations are defined: push (add to the top) and pop (remove from the top). In simple terms, it is a stack of plates: you can only take the top one off.
Queue
A data structure that follows the first-in, first-out (FIFO) principle. The first element added is the first one removed. Think of it as a queue at a shop: the person who arrived first is served first.
Linked list
A sequence of data structures (nodes) connected together via links (pointers). Each node contains data and a reference to the next node. In simple terms, it is a chain where each link knows where the next link is.
List (abstract)
An abstract data type representing a countable number of ordered values, where the same value may occur more than once.
Pointer
A variable whose value is the memory address of another variable. Think of it as a signpost that points to where the actual data lives.
Record (structure)
A data structure made up of a fixed number of information items that are not necessarily of the same type. In C, records are implemented as struct.
String
A sequence of characters, stored either as a literal constant or as a variable.
Graph
A pictorial (and mathematical) representation of a set of objects (vertices) where some pairs are connected by links (edges). In simple terms, it is a network of dots connected by lines.
Heap
A special case of a balanced binary tree where the root-node key is compared with its children and arranged accordingly (min-heap or max-heap). Used heavily in priority queues and sorting algorithms.
LIFO (last in, first out)
The access principle used by stacks. The most recently added element is the first to be removed.
FIFO (first in, first out)
The access principle used by queues. The earliest added element is the first to be removed.
Every non-trivial program needs to store, retrieve, and manipulate data. The choice of data structure determines how fast these operations are. Choosing an array when you need constant-time indexed access is sensible; choosing a linked list when you need frequent insertions in the middle is also sensible. Picking the wrong structure leads to slow, wasteful code.
Arrays – fixed-size, same-type elements, accessed by index. Fast lookup by position, but resizing is expensive.
Trees – hierarchical parent-child relationships. Used for search trees, file systems, and expression parsing.
Stacks – LIFO. Used for undo mechanisms, function-call tracking (the call stack), and expression evaluation.
Queues – FIFO. Used for task scheduling, print queues, and breadth-first search.
Linked lists – nodes connected by pointers. Easy insertion and deletion anywhere in the list, but no direct index access.
Lists (abstract) – ordered, may contain duplicates. The general concept that arrays and linked lists both implement.
Pointers – variables holding memory addresses. The backbone of linked lists, trees, and graphs in languages like C.
Records / structures – group related fields of different types. A student record might hold a name (string), age (integer), and GPA (float).
Strings – sequences of characters. Fundamental for text processing.
Graphs – vertices connected by edges. Model networks, social connections, maps, and dependencies.
Heaps – balanced binary trees with a heap property. The root is always the minimum (min-heap) or maximum (max-heap).
A collection of elements identified by index.
All elements must be the same type.
The index (also called subscript or key) maps each position to a stored object.
The term "vector" is sometimes used as a synonym for a one-dimensional array.
Arrays have a fixed size at creation in most languages (dynamic arrays and array lists are a separate concept).
Array index access: For a zero-indexed array of size n, valid indices run from 0 to n − 1. Accessing element i is an O(1) operation (constant time).
Stack operations:
push(item) – place item on top. O(1).
pop() – remove and return the top item. O(1).
Queue operations:
enqueue(item) – add item to the rear. O(1).
dequeue() – remove and return the front item. O(1).
Heap property (max-heap): For every node i, the value of i is greater than or equal to the values of its children.
Stacks power the "undo" button in every text editor and the call stack that tracks function calls in your running program. Queues manage print jobs sent to a printer and passengers boarding a plane. Trees structure file systems on your hard drive and the DOM of every web page. Graphs model road networks in mapping software and social connections on platforms like LinkedIn.
Students often confuse stacks and queues. Remember: a stack is a pile of plates (LIFO, last on is first off), a queue is a line at a shop (FIFO, first in line is first served).
Students sometimes think linked lists and arrays are interchangeable. They are not. Arrays give O(1) access by index but are costly to resize. Linked lists allow O(1) insertion or deletion at a known position but require O(n) traversal to find an element by value.
A heap is not the same as the "heap" in memory management. In this context, a heap is a tree-based data structure with a specific ordering property. The memory heap is an unrelated concept that happens to share the name.
Students may think a graph must be drawn visually. A graph is a mathematical structure (vertices and edges) that can be represented in code as an adjacency matrix, an adjacency list, or an edge list, with no picture required.
⚠️ Know the definition of each data structure and be able to give a one-line description from memory.
⚠️ LIFO vs. FIFO is a near-certain exam question. Associate LIFO with stacks and FIFO with queues.
⚠️ Be able to distinguish between an array and a linked list in terms of access speed, insertion cost, and memory layout.
⚠️ Understand the heap property (root is min or max) and know that heaps are a special case of a binary tree.
⚠️ The term "index," "subscript," and "key" are used interchangeably for arrays. Do not be thrown off by alternate wording.
True or False: A stack follows the FIFO principle.
Fill in the blank: In an array, elements are accessed using an _______.
True or False: A linked list allows O(1) access to any element by position.
Fill in the blank: A heap is a special case of a balanced _______ tree.
True or False: A record (struct) can contain fields of different data types.
Answers: 1. False (LIFO). 2. Index (or subscript/key). 3. False (O(n) traversal is needed). 4. Binary. 5. True.
Q: Define a data structure.
A: A data structure is a way of collecting and organising data so that operations such as searching, sorting, inserting, and deleting can be performed efficiently.
Q: What is the difference between a stack and a queue?
A: A stack uses last-in, first-out (LIFO) ordering, so the most recently added item is removed first. A queue uses first-in, first-out (FIFO) ordering, so the earliest added item is removed first.
Q: Name the two fundamental operations of a stack.
A: Push (add an item to the top) and pop (remove the item from the top).
Q: What is a pointer?
A: A pointer is a variable whose value is the memory address of another variable. Pointers are used to build linked lists, trees, and other dynamic data structures.
Q: How does a linked list differ from an array?
A: An array stores elements in a contiguous, fixed-size block and allows O(1) access by index. A linked list stores elements in nodes connected by pointers, allowing efficient insertion and deletion but requiring O(n) traversal to access an element by position.
Q: What is the heap property in a max-heap?
A: In a max-heap, the value of every node is greater than or equal to the values of its children, so the root node always holds the largest value.
Q: Give two real-world uses of a queue data structure.
A: Print-job scheduling (jobs are printed in the order they are submitted) and task scheduling in operating systems (processes are handled in the order they arrive).
Data structures are the foundation for the algorithms unit. Sorting algorithms (bubble sort, quicksort, mergesort) operate on arrays and lists. Search algorithms (linear search, binary search) depend on how data is stored. Trees connect to recursion from the structured programming topic, since tree traversals are naturally recursive. Graphs extend into more advanced courses covering network analysis, shortest-path algorithms, and database query optimisation.
data structure definition, array, stack, queue, linked list, tree, graph, heap, pointer, record, struct, string, LIFO, FIFO, push pop, enqueue dequeue, index subscript key, binary tree, data organisation, CSE 101, Texas A&M, computer science fundamentals, data structures revision