Introduction to Data Structures

Introduction to Data Structures What Is a Data Structure? A data structure is a systematic way of organizing and storing data in a computer's memory. Think of it as a specialized container that not only holds your data, but also defines the rules for how you can add, remove, find, and modify items within it. Just like choosing the right filing system affects how quickly you can retrieve a document, choosing the right data structure affects how efficiently your program runs. Why Data Structures Matter The choice of data structure can dramatically affect your program's performance. Consider a simple task: finding a specific value in a collection of data. Using a simple list: You'd have to scan through items one by one, taking linear time $O(n)$ where $n$ is the number of items. Using a binary search tree: You could eliminate half the remaining items with each comparison, taking logarithmic time $O(\log n)$. Using a hash table: You could find the item almost instantly in constant time $O(1)$ on average. This isn't a minor difference—with one million items, a linear scan might require one million operations, while a hash table would need just one or two. Data structures also influence memory usage and implementation difficulty. The fundamental trade-off is this: faster operations often require additional memory, and simpler structures may use less memory but have slower operations. Part of programming skill is recognizing these trade-offs and choosing wisely for your specific problem. Fundamental Data Structures Arrays An array is a collection of elements stored in a contiguous block of memory, where each element can be accessed by its numerical position or index. Key characteristics: Access by index: $O(1)$ — you can instantly reach any element if you know its position Insert or delete at the end: $O(1)$ — quick operation Insert or delete elsewhere: $O(n)$ — requires shifting all subsequent elements Fixed size: once created, an array's size typically cannot change (though some languages provide dynamic arrays that handle this automatically) When to use arrays: Simple lists, static lookup tables, or situations where you frequently need random access by position. Linked Lists A linked list is a chain of nodes, where each node contains data and a pointer (reference) to the next node in the sequence. Instead of storing elements in contiguous memory, linked lists store them wherever memory is available and link them together. Key characteristics: Insert or delete at the front: $O(1)$ — just update the pointer at the beginning Insert or delete elsewhere: $O(n)$ — must traverse the list to find the position Access by position: $O(n)$ — must follow pointers from the start Dynamic size: easily grows or shrinks as needed Memory overhead: requires extra memory for pointers When to use linked lists: Queues, stacks, or any situation where you're frequently adding/removing from the front and don't need random access by position. Stacks A stack is a specialized data structure that follows last-in, first-out (LIFO) order. Imagine a stack of plates: the last plate you put on is the first one you remove. Key operations: Push (add): $O(1)$ — add an element to the top Pop (remove): $O(1)$ — remove the top element Peek: $O(1)$ — view the top element without removing it When to use stacks: Managing function calls in programming languages, implementing undo features in applications, or solving problems requiring backtracking. Queues A queue is a specialized data structure that follows first-in, first-out (FIFO) order. Think of a line at a store: the first person in line is the first person served. Key operations: Enqueue (add): $O(1)$ — add an element to the back Dequeue (remove): $O(1)$ — remove the front element When to use queues: Processing items in order (like print job scheduling), breadth-first search in graphs, or any situation where fairness demands "first come, first served." Binary Search Trees A binary search tree (BST) is a hierarchical structure where each node has up to two children (left and right), and follows an ordering rule: all values in the left subtree are less than the node's value, and all values in the right subtree are greater. Key characteristics: Search, insert, delete: $O(\log n)$ when the tree is balanced (roughly equal branches) Search, insert, delete: $O(n)$ when the tree becomes unbalanced (like a linked list) Ordered iteration: you can traverse the tree to get values in sorted order When to use binary search trees: Problems requiring both fast lookup and the ability to retrieve data in sorted order. Balanced variants (like AVL trees or red-black trees) guarantee logarithmic performance. Hash Tables A hash table uses a hash function to convert keys into array indices. This allows direct access to data without searching through it. Here's how it works: when you insert a key-value pair, the hash function processes the key and produces an index. The value is then stored at that index (or in a bucket at that index if multiple keys hash to the same location). Key characteristics: Insert, search, delete: $O(1)$ average case — the hash function ideally maps each key to a unique index Insert, search, delete: $O(n)$ worst case — occurs when many keys hash to the same location (a collision) No ordering: hash tables don't maintain sorted order Memory: typically uses more memory than needed for the actual data When to use hash tables: Dictionary-like structures where you need fast lookup by key, caching frequently-accessed data, or counting occurrences of items. They're one of the most practically useful data structures. Graphs A graph is a collection of vertices (nodes) connected by edges (links). Graphs can be directed (edges have direction) or undirected (edges go both ways), and weighted (edges have values) or unweighted. Graphs are typically represented using either an adjacency list (each vertex maintains a list of its neighbors) or an adjacency matrix (a grid showing which vertices are connected). Key operations: Add/remove vertices or edges: $O(1)$ to $O(V)$ depending on representation Traverse using depth-first search or breadth-first search: $O(V + E)$ where $V$ is vertices and $E$ is edges When to use graphs: Modeling networks (social networks, computer networks), route planning, dependency tracking, or any problem involving connections between entities. Choosing the Right Data Structure The key to selecting an appropriate data structure is understanding the problem you're solving and matching it to a structure's strengths: Need fast lookup by key? Use a hash table Need ordered data or range queries? Use a binary search tree Need LIFO behavior? Use a stack Need FIFO behavior? Use a queue Need to model connections? Use a graph Need to frequently modify the beginning? Use a linked list Need fast random access? Use an array Always learn the Big-O time and space costs for each operation of the data structures in your toolbox. This knowledge allows you to make informed decisions that keep your algorithms running efficiently, even as the size of your data grows.