In this article, we explore the main data structures such as trees, hash maps, linked lists, queues, stacks, heaps, and undirected graphs. We discuss their functionalities, space and time complexities, and provide code examples in Dart. Whether you're a beginner or an experienced developer, this comprehensive guide will equip you with the knowledge to effectively utilise data structures in your programming endeavors.
Content Overview
- Introduction
- Queue
- Stack
- Single Linked List
- Double Linked List
- Hash Map (Hash Table)
- Min/Max Heap
- Undirected Graph
- Trees
- Trees: Binary Search Tree (BST)
- Trees: Red-Black Tree
- Conclusion
Introduction
Data structures are fundamental building blocks in computer science and play a crucial role in organising and manipulating data efficiently. Whether you're a beginner learning programming or an experienced developer looking to refresh your knowledge, understanding how different data structures work is essential. We will dive into the world of data structures and explore their inner workings, space and time complexities, and best use cases. We will provide code examples in Dart, a versatile programming language, to help you grasp the concepts and see them in action. By the end of this article, you'll have a solid understanding of various data structures and be ready to apply them to solve real-world problems.In the Dart language, there is no specific data type called "array" in the traditional sense. Instead, the List class is used as the fundamental data structure to hold a collection of elements. It serves as a versatile container that provides array-like functionality and operations.
Queue
A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front.
Space Complexity:
O(n), where n is the number of elements in the queue.
Time Complexity:
Enqueue: O(1) - Adding an element to the queue.
Dequeue: O(1) - Removing an element from the queue.
Use case: Used when the First-In-First-Out (FIFO) principle needs to be followed, such as in a task scheduling system or breadth-first search algorithms.
class Queue<T> {
List<T> _items = [];
void enqueue(T item) {
_items.add(item);
}
T dequeue() {
if (isEmpty()) {
throw StateError("Cannot dequeue from an empty queue.");
}
return _items.removeAt(0);
}
bool isEmpty() {
return _items.isEmpty;
}
}
Stack
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, known as the top.
Space Complexity:
O(n), where n is the number of elements in the stack.
Time Complexity:
Push: O(1) — Adding an element to the stack.
Pop: O(1) — Removing an element from the stack.
Use case: Used when the Last-In-First-Out (LIFO) principle needs to be followed, such as in function call stacks or depth-first search algorithms.
class Stack<T> {
List<T> _items = [];
void push(T item) {
_items.add(item);
}
T pop() {
if (isEmpty()) {
throw StateError("Cannot pop from an empty stack.");
}
return _items.removeLast();
}
bool isEmpty() {
return _items.isEmpty;
}
}
Single Linked List
Linked Lists are linear data structures where each element (node) contains a value and a reference to the next node.
Space Complexity:
O(n), where n is the number of nodes in the linked list.
Time Complexity:
Insertion at the beginning: O(1) — Adding a new node at the beginning of the linked list.
Insertion at the end: O(1) — Adding a new node at the end of the linked list.
Deletion: O(1) — Removing a node from the linked list.
Searching: O(n) — In the worst case, visiting all nodes in the linked list.
Use case: Used when frequent insertion and deletion of elements at the beginning or end of the list is required
class Node<T> {
T value;
Node<T> next;
Node(this.value);
}
class LinkedList<T> {
Node<T> head;
void insertAtBeginning(T value) {
var newNode = Node<T>(value);
newNode.next = head;
head = newNode;
}
void insertAtEnd(T value) {
var newNode = Node<T>(value);
if (head == null) {
head = newNode;
} else {
var current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
void delete(T value) {
if (head == null) {
return;
}
if (head.value == value) {
head = head.next;
return;
}
var current = head;
while (current.next != null) {
if (current.next.value == value) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
}
Double Linked List
Double Linked Lists are similar to single-linked lists, but each node has references to both the next and previous nodes.
Space Complexity:
O(n), where n is the number of nodes in the linked list.
Time Complexity:
Insertion at the beginning: O(1) — Adding a new node at the beginning of the linked list.
Insertion at the end: O(1) — Adding a new node at the end of the linked list.
Deletion: O(1) — Removing a node from the linked list.
Searching: O(n) — In the worst case, visiting all nodes in the linked list.
Use case: Used when frequent insertion and deletion of elements at the beginning or end of the list is required
class Node<T> {
T value;
Node<T> next;
Node<T> previous;
Node(this.value);
}
class DoublyLinkedList<T> {
Node<T> head;
void insertAtBeginning(T value) {
var newNode = Node<T>(value);
if (head != null) {
head.previous = newNode;
}
newNode.next = head;
head = newNode;
}
void insertAtEnd(T value) {
var newNode = Node<T>(value);
if (head == null) {
head = newNode;
} else {
var current = head;
while (current.next != null) {
current = current.next;
}
newNode.previous = current;
current.next = newNode;
}
}
void delete(T value) {
if (head == null) {
return;
}
if (head.value == value) {
head = head.next;
if (head != null) {
head.previous = null;
}
return;
}
var current = head;
while (current != null) {
if (current.value == value) {
current.previous.next = current.next;
if (current.next != null) {
current.next.previous = current.previous;
}
return;
}
current = current.next;
}
}
}
Hash Map (Hash Table)
Hash Maps store key-value pairs in an array, using a hash function to determine the index where each key-value pair should be stored.
Space Complexity:
O(n), where n is the number of key-value pairs stored.
Time Complexity:
Insertion: O(1) — Adding a key-value pair to the hash map.
Deletion: O(1) — Removing a key-value pair from the hash map.
Searching: O(1) — Retrieving the value associated with a given key.
Use case: Used for fast lookup of values based on keys when the relationship between keys and values is not necessarily ordered.
class HashMap<K, V> {
int _capacity;
List<List<Entry<K, V>>> _buckets;
HashMap({int capacity = 16}) {
_capacity = capacity;
_buckets = List<List<Entry<K, V>>>.filled(_capacity, []);
}
int _hashCode(K key) {
return key.hashCode % _capacity;
}
void put(K key, V value) {
int index = _hashCode(key);
List<Entry<K, V>> bucket = _buckets[index];
for (Entry<K, V> entry in bucket) {
if (entry.key == key) {
entry.value = value;
return;
}
}
bucket.add(Entry<K, V>(key, value));
}
V get(K key) {
int index = _hashCode(key);
List<Entry<K, V>> bucket = _buckets[index];
for (Entry<K, V> entry in bucket) {
if (entry.key == key) {
return entry.value;
}
}
return null;
}
void remove(K key) {
int index = _hashCode(key);
List<Entry<K, V>> bucket = _buckets[index];
for (Entry<K, V> entry in bucket) {
if (entry.key == key) {
bucket.remove(entry);
return;
}
}
}
bool containsKey(K key) {
int index = _hashCode(key);
List<Entry<K, V>> bucket = _buckets[index];
for (Entry<K, V> entry in bucket) {
if (entry.key == key) {
return true;
}
}
return false;
}
}
class Entry<K, V> {
final K key;
V value;
Entry(this.key, this.value);
}
Min/Max Heap
A Heap is a binary tree-based data structure in which the parent nodes have a specific ordering (e.g., minimum or maximum value) with respect to their children.
Space Complexity:
O(n), where n is the number of elements in the heap.
Time Complexity:
Insertion: O(log n) — Adding an element to the heap.
Removal: O(log n) — Removing the root element from the heap.
Peek (accessing the minimum/maximum element): O(1).
Use case: Used to efficiently retrieve the minimum or maximum element in constant time or perform efficient sorting of elements.
class MinHeap {
List<int> _heap;
MinHeap() {
_heap = [];
}
// Insert an element into the min heap
void insert(int value) {
// Add the new value to the end of the heap
_heap.add(value);
// Restore the min heap property
// by moving the value up if necessary
_moveUp(_heap.length - 1);
}
// Extract the minimum element from the heap
int extractMin() {
if (isEmpty()) {
throw Exception("Heap is empty");
}
// The minimum value is always at the root (index 0)
final minValue = _heap[0];
// Remove the last element from the heap
final lastValue = _heap.removeLast();
if (!isEmpty()) {
// Move the last value to the root
_heap[0] = lastValue;
// Restore the min heap property
// by moving the value down if necessary
_moveDown(0);
}
return minValue;
}
bool isEmpty() {
return _heap.isEmpty;
}
// Get the index of the parent node of a given index
int _parentIndex(int index) {
return (index - 1) ~/ 2;
}
// Get the index of the left child node of a given index
int _leftChildIndex(int index) {
return 2 * index + 1;
}
// Get the index of the right child node of a given index
int _rightChildIndex(int index) {
return 2 * index + 2;
}
// Move a value up the heap
// to restore the min heap property
void _moveUp(int index) {
while (index > 0 && _heap[index] < _heap[_parentIndex(index)]) {
final parentIndex = _parentIndex(index);
_swap(index, parentIndex);
index = parentIndex;
}
}
// Move a value down the heap to restore the min heap property
void _moveDown(int index) {
while (true) {
var smallest = index;
final lChildIdx = _leftChildIndex(index);
final rChildIdx = _rightChildIndex(index);
if (lChildIdx < _heap.length
&& _heap[lChildIdx] < _heap[smallest]) {
// Update the smallest index if the left child is smaller
smallest = lChildIdx;
}
if (rChildIdx < _heap.length
&& _heap[rChildIdx] < _heap[smallest]) {
// Update the smallest index if the right child is smaller
smallest = rChildIdx;
}
if (smallest == index) {
break;
}
// Swap the value with the smallest child
_swap(index, smallest);
// Move down to the smallest child index
index = smallest;
}
}
void _swap(int i, int j) {
final temp = _heap[i];
_heap[i] = _heap[j];
_heap[j] = temp;
}
}
To convert a max heap into a min-heap, the following changes need to be done:
- Change the comparison operator: In a max heap, the comparison operator used for comparing elements is typically “greater than” (>). To convert it into a min heap, you need to change the comparison operator to “less than” (<) or “less than or equal to” (<=).
- Adjust the heapify operation: The heapify operation is responsible for maintaining the heap property. In a max heap, it ensures that the maximum element is at the root. In a min heap, it needs to be modified to ensure that the minimum element is at the root.
- Update any relevant code that relies on the assumption of a max heap: If there are any other parts of your code that assume a max heap, such as extraction of maximum element or operations based on the max heap property, you may need to modify them accordingly to work with a min heap.
Undirected Graph
An Undirected Graph consists of a set of vertices connected by edges, where the edges have no direction. Check this for different types of Graph data structure
Space Complexity:
O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Time Complexity:
Add Vertex: O(1) — Adding a vertex to the graph.
Add Edge: O(1) — Adding an edge between two vertices.
Remove Vertex: O(V + E) — Removing a vertex and all associated edges.
Remove Edge: O(1) — Removing an edge between two vertices.
Use case: Used to represent relationships between entities or to solve problems related to graph theory, such as pathfinding algorithms.
class Graph {
Map<String, List<String>> _adjacencyList = {};
void addVertex(String vertex) {
if (!_adjacencyList.containsKey(vertex)) {
_adjacencyList[vertex] = [];
}
}
void addEdge(String vertex1, String vertex2) {
_adjacencyList[vertex1]?.add(vertex2);
_adjacencyList[vertex2]?.add(vertex1);
}
void removeVertex(String vertex) {
_adjacencyList.remove(vertex);
_adjacencyList.forEach((key, value) => value.remove(vertex));
}
void removeEdge(String vertex1, String vertex2) {
_adjacencyList[vertex1]?.remove(vertex2);
_adjacencyList[vertex2]?.remove(vertex1);
}
}
Trees
In computer science, a tree is a widely used data structure that represents a hierarchical structure. Just like a real-life tree, it consists of nodes connected by edges. Each node in a tree can have zero or more child nodes, except for the root node, which has no parent. The nodes in a tree are organised in a specific way to allow efficient data manipulation and retrieval.
Types of Trees:
- Binary Tree: A binary tree is a tree structure in which each node has at most two child nodes, referred to as the left child and the right child. Binary trees are commonly used as the basis for more complex tree structures.
- Binary Search Tree (BST): A binary search tree is a binary tree where the values in the left subtree of a node are less than the node’s value, and the values in the right subtree are greater than or equal to the node’s value. BSTs are commonly used for efficient searching, insertion, and deletion operations.
- AVL Tree: An AVL (Adelson-Velskii and Landis) tree is a self-balancing binary search tree. It maintains a balance factor for each node, ensuring that the heights of the left and right subtrees differ by at most one. AVL trees guarantee efficient logarithmic time complexity for various operations.
- Red-Black Tree: A red-black tree is another self-balancing binary search tree. It ensures balanced properties by assigning colors (red or black) to nodes and performing rotations and color adjustments during insertion and deletion operations. Red-black trees provide efficient logarithmic time complexity for operations and are widely used in various applications.
- B-Tree: A B-tree is a self-balancing tree structure designed for efficient disk access. It allows for multiple keys and child pointers per node, enabling efficient data storage and retrieval in external storage systems.
- Trie: A trie, also known as a prefix tree, is a tree structure commonly used for efficient retrieval of strings or sequences. It stores characters of a string in a tree-like structure, making it efficient for prefix-based searches.
Common Tree Applications:
- File systems: Directory structures in operating systems are often represented using trees.
- Database systems: Indexing structures like B-trees are used for efficient data retrieval.
- Compiler design: Syntax trees are used to represent the structure of programs.
- Artificial Intelligence: Decision trees and search trees are used in various AI algorithms.
- Networking: Routing algorithms use tree-based data structures for efficient packet routing.
- Hierarchical data representation: Trees are used to represent hierarchical relationships in data, such as organisation charts or family trees.
Balanced Trees
A balanced tree is a type of tree data structure where the heights of the subtrees of any node differ by at most a constant factor. This balance ensures that the tree remains relatively symmetrical and avoids the creation of long paths that can lead to inefficient operations. Balanced trees are designed to provide optimal performance for various operations, such as searching, insertion, and deletion.
Some examples of balanced trees include AVL trees, red-black trees, and B-trees. These trees employ specific balancing mechanisms, such as rotations and color adjustments, to maintain their balanced properties.
Benefits of Balanced Trees:
- Efficient Operations: Balanced trees offer efficient time complexities for operations like searching, insertion, and deletion. These operations typically have logarithmic time complexity, ensuring fast access to elements even as the size of the tree increases.
- Stable Performance: By maintaining balance, these trees prevent worst-case scenarios where the tree becomes highly skewed and performance degrades significantly. Balanced trees provide stable and predictable performance across a wide range of inputs.
- Optimal Space Utilisation: Balanced trees optimise space utilisation by minimising the height of the tree. This ensures that the tree structure occupies a reasonable amount of memory, regardless of the number of elements it contains.
Unbalanced Trees
Unbalanced trees, on the other hand, do not maintain the balance property. As a result, the heights of the subtrees of a node can differ significantly, leading to a skewed or elongated tree structure.
In an unbalanced tree, certain operations can become inefficient. For example, searching for an element may require traversing a long path, resulting in a time complexity closer to linear rather than logarithmic. Similarly, inserting or deleting nodes may disrupt the tree’s structure, making subsequent operations less efficient.
Unbalanced trees can occur due to various reasons, such as improper insertion and deletion operations or a specific pattern of data that causes the tree to become lopsided.
Impact of Unbalanced Trees:
- Reduced Performance: Unbalanced trees can lead to poor performance for operations such as searching, insertion, and deletion. The time complexity may no longer be logarithmic, and the efficiency of the tree decreases as the number of elements grows.
- Increased Memory Consumption: In some cases, unbalanced trees may require more memory than balanced trees to store the same number of elements. This is because unbalanced trees may have longer paths and higher heights.
It is important to note that unbalanced trees are not inherently bad or inappropriate in all scenarios. There are specific situations where unbalanced trees can still offer acceptable performance, especially if the tree remains relatively shallow or the number of elements is small.
Binary Search Tree (BST)
A Binary Search Tree is a binary tree-based data structure in which the left child node has a value smaller than its parent node, and the right child node has a value greater than or equal to its parent node.
Space Complexity:
O(n), where n is the number of nodes in the BST.
Time Complexity:
Search: O(log n) — Searching for a value in the BST.
Insertion: O(log n) — Inserting a value into the BST.
Deletion: O(log n) — Deleting a value from the BST.
In-order Traversal: O(n) — Visiting all nodes in ascending order.
Use case:
Searching for an element in a sorted collection efficiently.
Maintaining a collection of elements in sorted order.
Efficiently performing range queries (finding elements within a given range).
Implementing associative arrays with efficient key-value lookup.
class Node<T> {
T value;
Node<T> left;
Node<T> right;
Node(this.value);
}
class BinarySearchTree<T extends Comparable<T>> {
Node<T> _root;
void insert(T value) {
_root = _insertRecursive(_root, value);
}
Node<T> _insertRecursive(Node<T> node, T value) {
if (node == null) {
return Node<T>(value);
}
if (value.compareTo(node.value) < 0) {
node.left = _insertRecursive(node.left, value);
} else {
node.right = _insertRecursive(node.right, value);
}
return node;
}
bool search(T value) {
return _searchRecursive(_root, value);
}
bool _searchRecursive(Node<T> node, T value) {
if (node == null) {
return false;
}
if (value.compareTo(node.value) == 0) {
return true;
}
if (value.compareTo(node.value) < 0) {
return _searchRecursive(node.left, value);
} else {
return _searchRecursive(node.right, value);
}
}
void delete(T value) {
_root = _deleteRecursive(_root, value);
}
Node<T> _deleteRecursive(Node<T> node, T value) {
if (node == null) {
return node;
}
if (value.compareTo(node.value) < 0) {
node.left = _deleteRecursive(node.left, value);
} else if (value.compareTo(node.value) > 0) {
node.right = _deleteRecursive(node.right, value);
} else {
if (node.left == null && node.right == null) {
node = null;
} else if (node.left == null) {
node = node.right;
} else if (node.right == null) {
node = node.left;
} else {
var minValue = _findMinValue(node.right);
node.value = minValue;
node.right = _deleteRecursive(node.right, minValue);
}
}
return node;
}
T _findMinValue(Node<T> node) {
while (node.left != null) {
node = node.left;
}
return node.value;
}
void inOrderTraversal() {
_inOrderTraversalRecursive(_root);
}
void _inOrderTraversalRecursive(Node<T> node) {
if (node != null) {
_inOrderTraversalRecursive(node.left);
print(node.value);
_inOrderTraversalRecursive(node.right);
}
}
}
Red-Black Tree
A Red-Black Tree is a self-balancing binary search tree that ensures the tree remains balanced by enforcing certain properties (such as colorings) on the nodes.
Space Complexity:
O(n), where n is the number of nodes in the Red-Black Tree.
Time Complexity:
Search: O(log n) — Searching for a value in the Red-Black Tree.
Insertion: O(log n) — Inserting a value into the Red-Black Tree.
Deletion: O(log n) — Deleting a value from the Red-Black Tree.
In-order Traversal: O(n) — Visiting all nodes in ascending order.
Use case:
Maintaining a sorted collection efficiently while supporting efficient insertion and deletion operations.
Implementing ordered data structures such as interval trees or augmented search trees.
Database indexing and storage systems where efficient searching, insertion, and deletion are essential.
enum NodeColor { red, black }
class RBNode<T extends Comparable<T>> {
T value;
RBNode<T> left;
RBNode<T> right;
RBNode<T> parent;
NodeColor color;
RBNode(this.value) {
color = NodeColor.red;
}
}
class RedBlackTree<T extends Comparable<T>> {
RBNode<T> _root;
void insert(T value) {
var newNode = RBNode<T>(value);
_insertNode(newNode);
_fixViolation(newNode);
}
void _insertNode(RBNode<T> newNode) {
if (_root == null) {
_root = newNode;
_root.color = NodeColor.black;
return;
}
var current = _root;
RBNode<T> parent;
while (current != null) {
parent = current;
if (newNode.value.compareTo(current.value) < 0) {
current = current.left;
} else {
current = current.right;
}
}
newNode.parent = parent;
if (newNode.value.compareTo(parent.value) < 0) {
parent.left = newNode;
} else {
parent.right = newNode;
}
}
void _fixViolation(RBNode<T> node) {
RBNode<T> parent;
RBNode<T> grandparent;
while (node != _root && node.color == NodeColor.red
&& node.parent.color == NodeColor.red) {
parent = node.parent;
grandparent = parent.parent;
if (parent == grandparent.left) {
var uncle = grandparent.right;
if (uncle != null && uncle.color == NodeColor.red) {
parent.color = NodeColor.black;
uncle.color = NodeColor.black;
grandparent.color = NodeColor.red;
node = grandparent;
} else {
if (node == parent.right) {
_rotateLeft(parent);
node = parent;
parent = node.parent;
}
_rotateRight(grandparent);
var temp = parent.color;
parent.color = grandparent.color;
grandparent.color = temp;
node = parent;
}
} else {
var uncle = grandparent.left;
if (uncle != null && uncle.color == NodeColor.red) {
parent.color = NodeColor.black;
uncle.color = NodeColor.black;
grandparent.color = NodeColor.red;
node = grandparent;
} else {
if (node == parent.left) {
_rotateRight(parent);
node = parent;
parent = node.parent;
}
_rotateLeft(grandparent);
var temp = parent.color;
parent.color = grandparent.color;
grandparent.color = temp;
node = parent;
}
}
}
_root.color = NodeColor.black;
}
void _rotateLeft(RBNode<T> node) {
var rightChild = node.right;
node.right = rightChild.left;
if (rightChild.left != null) {
rightChild.left.parent = node;
}
rightChild.parent = node.parent;
if (node.parent == null) {
_root = rightChild;
} else if (node == node.parent.left) {
node.parent.left = rightChild;
} else {
node.parent.right = rightChild;
}
rightChild.left = node;
node.parent = rightChild;
}
void _rotateRight(RBNode<T> node) {
var leftChild = node.left;
node.left = leftChild.right;
if (leftChild.right != null) {
leftChild.right.parent = node;
}
leftChild.parent = node.parent;
if (node.parent == null) {
_root = leftChild;
} else if (node == node.parent.right) {
node.parent.right = leftChild;
} else {
node.parent.left = leftChild;
}
leftChild.right = node;
node.parent = leftChild;
}
bool search(T value) {
var current = _root;
while (current != null) {
if (value.compareTo(current.value) == 0) {
return true;
} else if (value.compareTo(current.value) < 0) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
}
Conclusion
In this article, we explored a wide range of data structures and their implementations in Dart. We covered various fundamental data structures, including sets, queues, linked lists, doubly-linked lists (deques), hash maps, undirected graphs, heaps, binary search trees (BST), and red-black trees.
Sets allow for storing unique elements efficiently and performing set operations such as union, intersection, and difference. Queues and deques are used for managing elements in a first-in-first-out (FIFO) manner, with deques also allowing efficient insertion and deletion at both ends.
Linked lists provide flexibility for dynamic element insertion and deletion, while hash maps enable fast key-value lookups based on a hash function. Undirected graphs were introduced as a way to represent relationships between entities, and we explored different graph traversal algorithms. Heaps, specifically the min heap and max heap variants, were discussed as tree-like structures useful for maintaining the minimum or maximum element at the root.
Finally, we delved into binary search trees (BST) and red-black trees, which are self-balancing binary search trees. We examined their properties, operations such as insertion, deletion, and searching, and their advantages in maintaining ordered collections efficiently.
By covering these diverse data structures, readers gained a comprehensive understanding of their functionalities, performance characteristics, and best use cases. Armed with this knowledge, developers are equipped to select and implement the most appropriate data structure for their specific problem domains, optimising efficiency and achieving scalable solutions.
Top comments (0)