Data Structures – Comprehensive Study
Notes
Educational reference material prepared for study and learning.
1. Introduction to Data Structures
A data structure is a way of organizing and storing data so that a program can access and
modify it efficiently. Choosing an appropriate structure affects the speed, memory use, and
clarity of an algorithm. Common structures include arrays, linked lists, stacks, queues, hash
tables, trees, graphs, and heaps.
2. Arrays and Lists
An array stores elements in an ordered sequence and traditionally provides fast access by
index. Python lists behave like dynamic arrays: they support indexing, slicing, insertion,
deletion, and iteration. Access by index is typically constant time, while inserting or deleting
near the beginning can require shifting many elements.
3. Linked Lists
A linked list consists of nodes where each node stores data and a reference to another node.
In a singly linked list, each node points to the next node. Linked lists can efficiently insert or
remove nodes when the appropriate position is already known, but accessing an arbitrary
position requires traversal from the beginning.
4. Stacks
A stack follows the Last In, First Out principle. The most recently added item is removed
first. Typical operations are push, which adds an item, and pop, which removes an item.
Stacks are useful for function calls, undo operations, expression evaluation, and depth-first
search.
5. Queues
A queue follows the First In, First Out principle. The earliest inserted item is removed first.
Queues are useful for scheduling, buffering, breadth-first search, and task processing. A
double-ended queue can support efficient insertion and removal at both ends.
6. Hash Tables and Dictionaries
A hash table stores key-value associations using a hash function to determine where data is
stored. Python dictionaries are implemented using a hash-table-based approach and
normally provide very fast average-case insertion, lookup, and deletion. Keys must be
hashable.
7. Sets
A set stores unique elements and is useful when duplicate values are not meaningful.
Membership tests are usually very efficient. Set operations include union, intersection,
difference, and symmetric difference. Sets are widely used for deduplication and
relationship comparisons.
8. Trees
A tree is a hierarchical data structure made of nodes connected by edges. A binary tree
allows each node to have at most two children. Trees are useful for representing
hierarchical information such as file systems, organization structures, and expression trees.
9. Binary Search Trees
A binary search tree maintains an ordering in which values in the left subtree are smaller
and values in the right subtree are larger, assuming the usual unique-key formulation.
Searching, insertion, and deletion can be efficient when the tree is balanced, but a highly
unbalanced tree can behave similarly to a linked list.
10. Balanced Trees
Balanced trees maintain height close to logarithmic in the number of nodes. Examples
include AVL trees and red-black trees. Balancing prevents a sequence of unfavorable
insertions from making tree operations unnecessarily slow.
11. Heaps and Priority Queues
A heap is a specialized tree-based structure that maintains a priority relationship. In a min-
heap, the smallest element is at the root; in a max-heap, the largest is at the root. Heaps are
commonly used to implement priority queues and are central to heap sort.
12. Graphs
A graph consists of vertices and edges. Graphs may be directed or undirected and may have
weighted or unweighted edges. They can represent road networks, social connections,
computer networks, dependencies, and many other relationships.
13. Graph Representations
Two common representations are adjacency matrices and adjacency lists. An adjacency
matrix uses a table and can make edge lookup direct, but it may require large amounts of
memory for sparse graphs. An adjacency list stores the neighbors of each vertex and is
usually more memory-efficient for sparse graphs.
14. Breadth-First Search
Breadth-first search, or BFS, explores a graph level by level. It commonly uses a queue. For
an unweighted graph, BFS can find the shortest path in terms of number of edges from a
starting vertex to reachable vertices.
15. Depth-First Search
Depth-first search, or DFS, explores one path as deeply as possible before backtracking. It
can be implemented recursively or with an explicit stack. DFS is useful for connectivity,
cycle detection, topological reasoning, and exploring search spaces.
16. Searching Algorithms
Linear search checks elements one by one and works on unsorted data. Binary search
repeatedly divides a sorted search interval in half and therefore requires ordered data.
Binary search typically takes logarithmic time, while linear search takes linear time in the
worst case.
17. Sorting Algorithms
Sorting rearranges elements according to an ordering. Common algorithms include bubble
sort, insertion sort, selection sort, merge sort, quicksort, and heap sort. Their time and
space characteristics differ, so algorithm choice depends on the problem and constraints.
18. Big-O Complexity
Big-O notation describes how resource requirements grow as input size increases. O(1) is
constant time, O(log n) grows logarithmically, O(n) linearly, O(n log n) commonly appears
in efficient comparison sorting, and O(n²) is quadratic. Complexity analysis helps compare
algorithms independently of machine speed.
19. Recursion
Recursion occurs when a function calls itself. A recursive algorithm needs a base case that
stops recursion and a recursive case that reduces the problem toward that base case. Trees
and divide-and-conquer algorithms are natural applications of recursion.
20. Dynamic Programming
Dynamic programming solves problems by storing results of overlapping subproblems
instead of recomputing them. It can be implemented using memoization or tabulation.
Typical examples include Fibonacci variants, knapsack problems, and certain shortest-path
problems.
21. Choosing a Data Structure
The best structure depends on required operations. Use a list when ordered indexed data is
useful, a set for uniqueness and membership, a dictionary for key-based lookup, a stack for
last-in-first-out behavior, a queue for first-in-first-out behavior, and specialized trees or
graphs for hierarchical or network relationships.
22. Practice Questions
1. Explain LIFO and FIFO. 2. When is binary search applicable? 3. What is the difference
between a stack and a queue? 4. Why can a hash table provide fast average lookup? 5. What
is the difference between BFS and DFS? 6. Why does a balanced tree matter? 7. Compare an
adjacency list with an adjacency matrix. 8. Explain O(n) and O(log n). 9. Give an example
where a set is better than a list. 10. Explain the purpose of dynamic programming.
Conclusion
These notes provide a structured foundation for further study. The most effective way to
learn is to combine reading with exercises, examples, projects, and regular review.