Difficulty: Beginner | Prerequisites: None, though basic programming concepts (variables, loops) will help.
Data structures are the containers you use to organise and store data inside a program. Every piece of software you write will lean on at least one, and choosing the right structure for the job is half of writing efficient code. This set of notes covers the four foundational structures: arrays, linked lists, trees, and graphs. If you understand how each one stores data and what it costs to read, insert, or delete from it, you have the scaffolding for everything else in this course.
Arrays give you instant access to any element by index but are slow to insert into or delete from. Linked lists flip that trade-off: fast inserts and deletes, slow lookups. Trees and graphs generalise these ideas into hierarchical and network-like relationships, and each comes with its own traversal costs.
Data structure
A way of organising and storing data in a computer program so it can be used efficiently. Think of it as a filing system: the structure you pick determines how quickly you can find, add, or remove information.
Array
A collection of elements of the same data type, stored contiguously (side by side) in memory. In simple terms, imagine a row of numbered boxes sitting next to each other in a warehouse. You can jump straight to box #47 because you know exactly where it is.
Linked list
A collection of elements (called nodes), where each node holds a value and a reference (pointer) to the next node in the sequence. Think of it as a chain: each link knows only about the next link. To reach the fifth link, you have to walk through the first four.
Node
A single element in a data structure that contains a value and, depending on the structure, one or more references to other nodes. In simple terms, a node is one "box" in the chain, tree, or graph.
Binary tree
A tree in which every node has at most two children, typically referred to as the left child and the right child. Think of it as a family tree where every person can have at most two direct descendants.
Tree
A hierarchical data structure made up of nodes, where each node holds a value and references to zero or more child nodes. There is a single root node at the top, and no cycles. In simple terms, it is a structure that branches downward, like an upside-down tree.
Graph
A collection of nodes (also called vertices) connected by edges. Unlike a tree, a graph can contain cycles and does not require a single root. Think of it as a map of cities (nodes) connected by roads (edges). Some roads may be one-way (directed), some two-way (undirected).
Contiguous memory
Memory locations that sit directly next to each other, with no gaps. Arrays rely on this property for constant-time access.
Traversal
The process of visiting every element in a data structure, usually to read, search, or process the data it contains.
Breadth-first search (BFS)
A graph traversal algorithm that explores all neighbours of a node before moving on to their neighbours. It works outward in layers. Think of it as dropping a stone in a pond: the ripples expand evenly in all directions.
Depth-first search (DFS)
A graph traversal algorithm that follows one path as far as it goes before backtracking and trying the next. Think of it as exploring a maze by always turning left until you hit a dead end, then retracing your steps.
Elements are stored one after another in memory, and each element is the same data type.
Access by index is O(1), constant time, because the memory address can be calculated directly from the index.
Insertion or deletion at an arbitrary position is O(n), linear time, because every element after the target must shift forward or backward to keep the block contiguous.
Appending to the end of a dynamic array is amortised O(1), but that is a special case.
Arrays are the default choice when you need fast random access and your data size is relatively stable.
Each node contains a value and a pointer to the next node. The nodes can live anywhere in memory.
Insertion or deletion (when you already have a reference to the right spot) is O(1), because you only need to update one or two pointers.
Accessing the kth element is O(n), because you must walk the chain from the head node.
Linked lists are the better pick when your program does frequent inserts and deletes at known positions but rarely needs random access.
A tree is a collection of nodes where each node holds a value and references to its children. There is one root, and no node has more than one parent.
A binary tree restricts each node to at most two children (left and right).
Traversing a tree (visiting every node) takes O(n) time, where n is the number of nodes.
Common traversal orders: in-order, pre-order, post-order (all depth-first), and level-order (breadth-first).
Trees underpin many faster structures you will meet later, such as binary search trees, heaps, and AVL trees.
A graph consists of nodes (vertices) and edges. Edges may be directed (one-way) or undirected (two-way), and may carry weights.
Traversal can take O(V + E) time, where V is the number of vertices and E the number of edges, depending on the algorithm.
The two standard traversal algorithms are BFS and DFS.
BFS uses a queue and explores layer by layer.
DFS uses a stack (or recursion) and explores as deep as possible before backtracking.
Graphs model problems like social networks, route planning, dependency resolution, and web crawling.
Structure | Access | Insert/Delete (arbitrary) | Memory layout |
|---|---|---|---|
Array | O(1) | O(n) | Contiguous |
Linked list | O(n) | O(1)* | Scattered |
Binary tree | O(n) worst case | O(n) worst case | Scattered |
Graph | Depends on representation | Depends on representation | Adjacency list or matrix |
*O(1) insertion/deletion for linked lists assumes you already hold a reference to the relevant node. Finding that node first costs O(n).
Arrays are everywhere: pixel buffers in images, rows in a spreadsheet, the backing storage for most list implementations in standard libraries.
Linked lists appear in undo/redo stacks, music playlists (next/previous track), and memory allocators that manage free blocks.
Trees power file systems (directory hierarchies), HTML/DOM parsing, and database indices (B-trees).
Graphs model the internet (web pages linked by hyperlinks), GPS navigation (roads between intersections), and social networks (people connected by friendships).
"Linked list insertion is always O(1)." Only if you already have a pointer to the insertion point. If you have to search for it first, the search is O(n), making the total operation O(n).
"Arrays are always worse for insertion than linked lists." When you are appending to the end of a dynamic array, amortised cost is O(1). Context matters.
"A tree is a special type of graph." Technically true (a tree is a connected, acyclic, undirected graph), but in most CS courses they are taught with different interfaces and assumptions, so treating them as interchangeable will confuse you on exams.
"BFS and DFS give the same result." They visit nodes in different orders and are suited to different problems. BFS finds the shortest unweighted path; DFS is often simpler for exhaustive exploration or detecting cycles.
⚠️ Know the Big-O complexities for access, insertion, and deletion for both arrays and linked lists. This is one of the most commonly tested comparisons.
⚠️ Be able to explain why array access is O(1) (direct address calculation from base address + index × element size).
⚠️ Understand the difference between BFS and DFS, including which auxiliary data structure each uses (queue vs. stack).
⚠️ Be prepared to identify which data structure is best suited to a given scenario (e.g., "you need fast lookup by position" points to an array).
True or false: Accessing the 100th element of a linked list takes the same time as accessing the 1st.
Fill in the blank: Inserting into the middle of an array is O(___) because elements must be _______.
True or false: A binary tree node can have three children.
Fill in the blank: BFS uses a _______ and DFS uses a _______.
True or false: In a graph, edges must always be bidirectional.
Answers: 1. False (you must traverse from the head). 2. O(n), shifted. 3. False (at most two). 4. Queue, stack. 5. False (edges can be directed).
Q: What is the time complexity of accessing an element by index in an array, and why?
A: O(1), constant time. The memory address is calculated directly: base address + (index × size of each element). No traversal is needed.
Q: Why is inserting into the middle of a linked list faster than inserting into the middle of an array?
A: In a linked list, you update a constant number of pointers (the previous node's next pointer and the new node's next pointer). In an array, every element after the insertion point must be shifted one position, which takes O(n) time.
Q: Name two real-world systems that are best modelled as graphs rather than trees.
A: Social networks (users can have mutual or one-directional connections, forming cycles) and road maps (intersections connected by roads, often with many alternative routes forming loops).
Q: What is the difference between BFS and DFS in terms of traversal order?
A: BFS explores all nodes at the current depth before moving to the next depth level (layer by layer). DFS follows a single path as deep as possible before backtracking to explore other branches.
Q: A program needs to store a playlist where songs are frequently added and removed from arbitrary positions. Which structure is more efficient: an array or a linked list? Why?
A: A linked list, because insertions and deletions at a known position cost O(1) (pointer updates only), whereas an array would require shifting all subsequent elements at O(n) per operation.
Understanding arrays and linked lists is the foundation for stacks, queues, and hash tables, which build directly on top of them.
Tree structures lead into binary search trees, heaps, and balanced trees (AVL, red-black), all of which you will meet in later units.
Graph traversal (BFS/DFS) connects to shortest-path algorithms (Dijkstra, Bellman-Ford) and minimum spanning trees (Prim, Kruskal), which are standard topics in algorithms courses.
data structures, arrays, linked lists, singly linked list, doubly linked list, nodes, pointers, binary tree, tree traversal, in-order, pre-order, post-order, level-order, graph, vertex, edge, directed graph, undirected graph, adjacency list, adjacency matrix, BFS, DFS, breadth-first search, depth-first search, Big-O, time complexity, constant time, linear time, CS101, UCF, Computer Science I, intro to data structures