Data Structures and Algorithms in Dart, with examples(In simple words)
Data Structures: Your Toy Boxes and Shelves
List (The Toy Box - Order Matters):
Analogy: Think of a regular toy box where you throw toys in. They are in the order you put them in, and you can have duplicates (like multiple toy cars).
Simple Definition: An ordered collection of items. You can access items by their position (index), and duplicates are allowed.
Dart Example:
void main() { List<String> toyBox = ["Car", "Doll", "Car", "Blocks", "Puzzle"]; print("Toy box contents: $toyBox"); // Output: Toy box contents: [Car, Doll, Car, Blocks, Puzzle] print("First toy: ${toyBox[0]}"); // Output: First toy: Car print("Third toy: ${toyBox[2]}"); // Output: Third toy: Car toyBox.add("Teddy Bear"); // Add to the end print("Toy box after adding Teddy Bear: $toyBox"); // Output: [Car, Doll, Car, Blocks, Puzzle, Teddy Bear] }content_copy download
Use code with caution.Dart
Set (The Unique Toy Shelf - No Duplicates):
Analogy: Imagine a special shelf for your unique toys. You only put one of each type of toy on this shelf. If you try to put another "Car" on it, it just stays as one "Car".
Simple Definition: An unordered collection of unique items. No duplicates are allowed. Good for checking if something is present and ensuring uniqueness.
Dart Example:
void main() { Set<String> uniqueToys = {"Car", "Doll", "Car", "Blocks"}; // "Car" added twice, but Set will store it only once print("Unique toys shelf: $uniqueToys"); // Output: Unique toys shelf: {Car, Doll, Blocks} (Order might vary) uniqueToys.add("Puzzle"); print("Shelf after adding Puzzle: $uniqueToys"); // Output: {Car, Doll, Blocks, Puzzle} bool hasCar = uniqueToys.contains("Car"); print("Does the shelf have a Car? $hasCar"); // Output: Does the shelf have a Car? true }content_copy download
Use code with caution.Dart
Map (The Labeled Boxes - Key and Value):
Analogy: Think of labeled boxes. Each box has a label (the key), and inside the box are toys (the value). You find a box by its label.
Simple Definition: A collection of key-value pairs. Each key is unique, and it points to a value. Like a dictionary or phonebook.
Dart Example:
void main() { Map<String, String> toyLocations = { "Car": "Red Box", "Doll": "Pink Box", "Blocks": "Blue Bin" }; print("Toy locations map: $toyLocations"); // Output: Toy locations map: {Car: Red Box, Doll: Pink Box, Blocks: Blue Bin} print("Where is the Doll? ${toyLocations["Doll"]}"); // Output: Where is the Doll? Pink Box toyLocations["Puzzle"] = "Green Shelf"; // Add a new toy and location print("Map after adding Puzzle location: $toyLocations"); // Output: {Car: Red Box, Doll: Pink Box, Blocks: Blue Bin, Puzzle: Green Shelf} }content_copy download
Use code with caution.Dart
Stack (The Stack of Plates - Last In, First Out - LIFO):
Analogy: Imagine a stack of plates. You put new plates on top (push), and you take plates off the top (pop). The last plate you put on is the first one you take off.
Simple Definition: A collection where you can only add and remove items from the top. Last In, First Out (LIFO). Useful for undo/redo operations, function call stacks.
Dart Example (using a List to simulate a Stack):
void main() { List<String> plateStack = []; // Using a List as a stack plateStack.add("Plate 1"); // Push onto the stack plateStack.add("Plate 2"); plateStack.add("Plate 3"); print("Plate stack: $plateStack"); // Output: Plate stack: [Plate 1, Plate 2, Plate 3] String topPlate = plateStack.removeLast(); // Pop from the stack print("Removed plate: $topPlate"); // Output: Removed plate: Plate 3 print("Stack after pop: $plateStack"); // Output: Stack after pop: [Plate 1, Plate 2] print("Top plate now: ${plateStack.last}"); // Peek at the top (without removing) - Output: Top plate now: Plate 2 }content_copy download
Use code with caution.Dart
Queue (The Waiting Line - First In, First Out - FIFO):
Analogy: Think of a waiting line at a store or a bus stop. The first person who gets in line is the first person to be served or get on the bus.
Simple Definition: A collection where you add items to the back (enqueue) and remove items from the front (dequeue). First In, First Out (FIFO). Useful for task scheduling, processing in order.
Dart Example (using a List to simulate a Queue):
void main() { List<String> toyQueue = []; // Using a List as a queue toyQueue.add("Toy A"); // Enqueue (add to the back) toyQueue.add("Toy B"); toyQueue.add("Toy C"); print("Toy queue: $toyQueue"); // Output: Toy queue: [Toy A, Toy B, Toy C] String firstToy = toyQueue.removeAt(0); // Dequeue (remove from the front) print("Served toy: $firstToy"); // Output: Served toy: Toy A print("Queue after dequeue: $toyQueue"); // Output: Queue after dequeue: [Toy B, Toy C] print("Next toy in line: ${toyQueue[0]}"); // Peek at the front (without removing) - Output: Next toy in line: Toy B }content_copy download
Use code with caution.Dart
Linked List (The Chain of Toys - Flexible Connections):
Analogy: Imagine toys linked together in a chain. Each toy points to the next toy in the chain. You can easily add or remove toys in the middle without rearranging everything.
Simple Definition: A sequence of nodes, where each node contains data and a link (pointer) to the next node. Flexible for insertions and deletions, but accessing a specific element can be slower than in a List.
Dart Example (Simplified Linked List):
class Node { String data; Node? next; // Pointer to the next node (can be null if it's the last node) Node(this.data); } class LinkedList { Node? head; // Head of the list (first node) void addFirst(String data) { Node newNode = Node(data); newNode.next = head; // New node points to the current head head = newNode; // New node becomes the new head } void printList() { Node? current = head; while (current != null) { print(current.data); current = current.next; // Move to the next node } } } void main() { LinkedList toyChain = LinkedList(); toyChain.addFirst("Toy C"); toyChain.addFirst("Toy B"); toyChain.addFirst("Toy A"); // "Toy A" is now at the front print("Toy chain:"); toyChain.printList(); // Output: // Toy chain: // Toy A // Toy B // Toy C }content_copy download
Use code with caution.Dart
Tree (The Family Tree - Hierarchical Structure):
Analogy: Think of a family tree. There's a root (the ancestor), and branches extend down to children, grandchildren, etc. Data is organized in a hierarchical way.
Simple Definition: A hierarchical data structure made of nodes connected by edges. A tree has a root node, and each node can have child nodes. Binary Trees (each node has at most two children) are common. Useful for representing hierarchies, searching, sorting.
Dart Example (Simplified Binary Tree - just showing basic structure):
class TreeNode { String data; TreeNode? leftChild; // Pointer to the left child TreeNode? rightChild; // Pointer to the right child TreeNode(this.data); } void main() { TreeNode root = TreeNode("Grandparent"); root.leftChild = TreeNode("Parent 1"); root.rightChild = TreeNode("Parent 2"); root.leftChild?.leftChild = TreeNode("Child 1A"); // Child of Parent 1 root.leftChild?.rightChild = TreeNode("Child 1B"); // Child of Parent 1 print("Family Tree Structure (simplified):"); print("Root: ${root.data}"); print(" Left Child: ${root.leftChild?.data}"); print(" Right Child: ${root.rightChild?.data}"); print(" Left Grandchild (of Parent 1): ${root.leftChild?.leftChild?.data}"); print(" Right Grandchild (of Parent 1): ${root.leftChild?.rightChild?.data}"); // Output (structure visualization): // Family Tree Structure (simplified): // Root: Grandparent // Left Child: Parent 1 // Right Child: Parent 2 // Left Grandchild (of Parent 1): Child 1A // Right Grandchild (of Parent 1): Child 1B }content_copy download
Use code with caution.Dart
Algorithms: What You Do With Your Toys
Linear Search (Finding a Toy in a Messy Box - One by One):
Analogy: You are looking for a specific toy (e.g., a blue block) in a big, messy toy box. You have to look at each toy one by one until you find it or you've checked all toys.
Simple Definition: Go through each item in a list or collection sequentially until you find the target item or reach the end.
Dart Example (same as before):
int linearSearch(List list, dynamic target) { for (int i = 0; i < list.length; i++) { if (list[i] == target) { return i; // Found it! } } return -1; // Not found } void main() { List<String> toys = ["Doll", "Car", "Blocks", "Puzzle", "Teddy"]; String targetToy = "Blocks"; int index = linearSearch(toys, targetToy); if (index != -1) { print("$targetToy found at position $index."); // Output: Blocks found at position 2. } else { print("$targetToy not found."); } }content_copy download
Use code with caution.Dart
Binary Search (Finding a Toy in Sorted Boxes - Divide and Conquer):
Analogy: Imagine your toys are sorted into boxes by type (e.g., all cars in one box, all dolls in another, and the boxes are in alphabetical order). You want to find the "Doll" box. You can open the middle box. If it's "Blocks" (which comes after "Doll" alphabetically), you know the "Doll" box must be in the boxes before the middle one. You repeat this process, narrowing down the search area quickly.
Simple Definition: Efficiently search for an item in a sorted list. Repeatedly divide the search interval in half. Much faster than linear search for large sorted lists.
Dart Example (same as before - remember the list must be sorted!):
int binarySearch(List sortedList, dynamic target) { int low = 0; int high = sortedList.length - 1; while (low <= high) { int mid = (low + high) ~/ 2; dynamic guess = sortedList[mid]; if (guess == target) { return mid; } else if (guess < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } void main() { List<String> sortedToys = ["Blocks", "Car", "Doll", "Puzzle", "Teddy"]; // Sorted list! String targetToy = "Doll"; int index = binarySearch(sortedToys, targetToy); if (index != -1) { print("$targetToy found at position $index."); // Output: Doll found at position 2. } else { print("$targetToy not found."); } }content_copy download
Use code with caution.Dart
Bubble Sort (Sorting Toys by Size - Step by Step Swapping):
Analogy: You want to sort your toys by size from smallest to largest. You go through the toys, comparing each toy with the one next to it. If they are in the wrong order (bigger toy before a smaller one), you swap them. You keep doing this pass after pass until all toys are in the correct size order. Smaller toys "bubble up" to the beginning of the list.
Simple Definition: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Not very efficient for large lists, but easy to understand.
Dart Example:
void bubbleSort(List list) { int n = list.length; bool swapped; // To optimize - if no swaps in a pass, list is sorted do { swapped = false; for (int i = 0; i < n - 1; i++) { if (list[i] > list[i + 1]) { // Compare adjacent elements // Swap list[i] and list[i+1] var temp = list[i]; list[i] = list[i + 1]; list[i + 1] = temp; swapped = true; } } n--; // Last element is now in its correct sorted position } while (swapped); // Continue passes as long as swaps happened } void main() { List<int> toySizes = [5, 2, 8, 1, 9, 4]; print("Unsorted toy sizes: $toySizes"); // Output: Unsorted toy sizes: [5, 2, 8, 1, 9, 4] bubbleSort(toySizes); print("Sorted toy sizes: $toySizes"); // Output: Sorted toy sizes: [1, 2, 4, 5, 8, 9] }content_copy download
Use code with caution.Dart
In Summary:
Data Structures are ways to organize your data (like different types of toy boxes and shelves). Choosing the right one makes your program more efficient and easier to manage.
Algorithms are sets of instructions to perform tasks (like finding a toy, sorting toys). They are the steps you take to solve problems using data.
Learning about these basic data structures and algorithms is fundamental to programming. They provide you with the tools to organize and process information effectively in your Dart programs!