A Comprehensive Guide for Building Efficient Data Structures in Dart

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 utilize 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 Binary Search Tree (BST) Red-Black Tree Conclusion Introduction Data structures are fundamental building blocks in computer science and play a crucial role in organizing 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. Queue A Queue is a linear that follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front. data structure 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. 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. Use case: class Queue { List _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. Used when the Last-In-First-Out (LIFO) principle needs to be followed, such as in function call stacks or depth-first search algorithms. Use case: class Stack { List _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. Used when frequent insertion and deletion of elements at the beginning or end of the list is required Use case: class Node { T value; Node next; Node(this.value); } class LinkedList { Node head; void insertAtBeginning(T value) { var newNode = Node (value); newNode.next = head; head = newNode; } void insertAtEnd(T value) { var newNode = Node (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. Used when frequent insertion and deletion of elements at the beginning or end of the list is required Use case: class Node { T value; Node next; Node previous; Node(this.value); } class DoublyLinkedList { Node head; void insertAtBeginning(T value) { var newNode = Node (value); if (head != null) { head.previous = newNode; } newNode.next = head; head = newNode; } void insertAtEnd(T value) { var newNode = Node (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. Used for fast lookup of values based on keys when the relationship between keys and values is not necessarily ordered. Use case: class HashMap { int _capacity; List >> _buckets; HashMap({int capacity = 16}) { _capacity = capacity; _buckets = List >>.filled(_capacity, []); } int _hashCode(K key) { return key.hashCode % _capacity; } void put(K key, V value) { int index = _hashCode(key); List > bucket = _buckets[index]; for (Entry entry in bucket) { if (entry.key == key) { entry.value = value; return; } } bucket.add(Entry (key, value)); } V get(K key) { int index = _hashCode(key); List > bucket = _buckets[index]; for (Entry entry in bucket) { if (entry.key == key) { return entry.value; } } return null; } void remove(K key) { int index = _hashCode(key); List > bucket = _buckets[index]; for (Entry entry in bucket) { if (entry.key == key) { bucket.remove(entry); return; } } } bool containsKey(K key) { int index = _hashCode(key); List > bucket = _buckets[index]; for (Entry entry in bucket) { if (entry.key == key) { return true; } } return false; } } class Entry { 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). Used to efficiently retrieve the minimum or maximum element in constant time or perform efficient sorting of elements. Use case: class MinHeap { List _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 , the following changes need to be done: max heap into a min-heap 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. 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. Used to represent relationships between entities or to solve problems related to graph theory, such as pathfinding algorithms. Use case: class Graph { Map > _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 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 organized in a specific way to allow efficient data manipulation and retrieval. tree Types of Trees: Binary Tree: A 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 tree 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 organization 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 Utilization: Balanced trees optimize space utilization by minimizing 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 value; Node left; Node right; Node(this.value); } class BinarySearchTree > { Node _root; void insert(T value) { _root = _insertRecursive(_root, value); } Node _insertRecursive(Node node, T value) { if (node == null) { return Node (value); } if (value.compareTo(node.value) node, T value) { if (node == null) { return false; } if (value.compareTo(node.value) == 0) { return true; } if (value.compareTo(node.value) _deleteRecursive(Node node, T value) { if (node == null) { return node; } 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 node) { while (node.left != null) { node = node.left; } return node.value; } void inOrderTraversal() { _inOrderTraversalRecursive(_root); } void _inOrderTraversalRecursive(Node 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 value; RBNode left; RBNode right; RBNode parent; NodeColor color; RBNode(this.value) { color = NodeColor.red; } } class RedBlackTree > { RBNode _root; void insert(T value) { var newNode = RBNode (value); _insertNode(newNode); _fixViolation(newNode); } void _insertNode(RBNode newNode) { if (_root == null) { _root = newNode; _root.color = NodeColor.black; return; } var current = _root; RBNode parent; while (current != null) { parent = current; if (newNode.value.compareTo(current.value) node) { RBNode parent; RBNode 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 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 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, optimizing efficiency and achieving scalable solutions.