Data Structures Reference
This section provides a comprehensive reference for common data structures used in software development. Understanding these structures is fundamental to designing efficient and scalable applications.
Abstract Data Types (ADTs)
Before diving into specific implementations, it's important to understand the concept of Abstract Data Types (ADTs). An ADT defines a set of operations that can be performed on data, independent of its underlying implementation.
Common Data Structures
Arrays
An array is a collection of elements, each identified by an index or key. Elements are stored in contiguous memory locations, allowing for constant-time access to any element given its index.
- Access (by index): O(1)
- Insertion/Deletion (at end): O(1) (if not resizing)
- Insertion/Deletion (at beginning/middle): O(n)
Example (Conceptual)
// Declaration in a hypothetical language
let numbers = new Array(5); // Array of size 5
numbers[0] = 10;
numbers[4] = 50;
print(numbers[1]); // Access element at index 1
Linked Lists
A linked list is a linear data structure where elements are not stored at contiguous memory locations. Elements (nodes) are linked using pointers. Each node contains data and a reference (or link) to the next node in the sequence.
- Insertion/Deletion (at beginning): O(1)
- Insertion/Deletion (at end): O(n) (O(1) with a tail pointer)
- Insertion/Deletion (in middle, given node): O(1)
- Access (by index/value): O(n)
Example (Conceptual)
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
let head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
Stacks
A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. Elements are added and removed from the same end, referred to as the "top" of the stack.
- Push (add element): O(1)
- Pop (remove element): O(1)
- Peek (view top element): O(1)
Example (Conceptual)
let myStack = [];
myStack.push(10); // Stack: [10]
myStack.push(20); // Stack: [10, 20]
let topElement = myStack.pop(); // topElement = 20, Stack: [10]
Queues
A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. Elements are added at one end (rear) and removed from the other end (front).
- Enqueue (add element): O(1)
- Dequeue (remove element): O(1)
- Front (view front element): O(1)
Example (Conceptual)
let myQueue = [];
myQueue.push(10); // Queue: [10]
myQueue.push(20); // Queue: [10, 20]
let firstElement = myQueue.shift(); // firstElement = 10, Queue: [20]
Trees
A tree is a hierarchical data structure consisting of nodes connected by edges. It has a root node, and each node can have zero or more child nodes. Trees are used for representing hierarchical relationships.
- Insertion: O(log n) on average, O(n) worst case
- Deletion: O(log n) on average, O(n) worst case
- Search: O(log n) on average, O(n) worst case
Example (Binary Search Tree)
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// ... (BST insertion/search logic would go here)
Hash Tables (Hash Maps/Dictionaries)
A hash table is a data structure that implements an associative array, mapping keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
- Insertion: O(1) on average, O(n) worst case
- Deletion: O(1) on average, O(n) worst case
- Search: O(1) on average, O(n) worst case
Example (Conceptual)
let userProfile = {
"username": "johndoe",
"email": "john.doe@example.com",
"age": 30
};
print(userProfile.username); // Access value by key
Choosing the Right Data Structure
The choice of data structure significantly impacts the performance and efficiency of an algorithm. Consider the following when making your decision:
- Data Access Patterns: How will you access and modify the data? (e.g., frequent lookups, sequential access, insert/delete at ends).
- Time Complexity: What are the performance requirements for operations?
- Space Complexity: How much memory can the data structure consume?
- Relationships: Does the data have inherent hierarchical or network-like relationships?
Refer to the Algorithms section for how data structures are used in conjunction with algorithmic techniques.