Guided: Foundations of Computing - Working with Data Structures

In this lab, you’ll explore how various fundamental data structures are structured, how they operate, and how they’re applied in real-world scenarios.

Throughout this lab, you will:

• Explore Linked Lists: Understand how singly, doubly, and circular linked lists work and where to use each.
• Study Tree Structures: Learn about binary trees, search trees, and the importance of balancing.
• Dive into Hash Table Design: Understand hashing, collisions, and fast lookup performance.
• Examine Priority Queues and Heaps: Learn how to prioritize tasks efficiently with heaps.
• Explore Advanced Trees: Understand specialized trees like AVL, Red-Black, B-Trees, and Tries for optimized performance and storage.

This lab is structured around detailed explanations, visuals, pseudocode, and real-world examples. After each topic, you will complete a set of validation-based tasks to reinforce your understanding.

info> If you get stuck on a task, you can find the solution in the solution folder in your file tree or by clicking the Task Solution link at the bottom of each task after attempting it.

Let's get started !

Linked List Implementations

In this step, you will learn about Linked Lists, one of the fundamental data structures used to store and manipulate sequences of data.

What is a Linked List?

A linked list is a linear data structure where each element is a separate object, called a node. Each node contains two parts:

1. Data - The value stored in the node.
2. Pointer/Reference - A link to the next node in the sequence.

Linked lists do not require contiguous memory allocation. This dynamic nature makes insertion and deletion operations more efficient, as there is no need to shift elements.

Types of Linked Lists

Linked lists come in three primary variations. Each type differs in how nodes are connected and how the list is traversed or manipulated:

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

You will now understand each of these in detail.

1. Singly Linked List

Each node in a singly linked list contains two parts: the data itself and a pointer that links to the next node. This pointer creates a chain, connecting each node to the next, allowing traversal from the head node to the end, where the last node's pointer is NULL.

Visual Representation:

[Data|Next] -> [Data|Next] -> [Data|Next] -> NULL

Example:

Consider a list of students lined up for registration. Each student knows only who the next student is. You can go through the line only in the forward direction, one student at a time, until you reach the last student.

Pseudocode:

class Node:
    data
    next

class LinkedList:
    head

    method insertAtStart(value):
        newNode = Node(value)
        newNode.next = head
        head = newNode

    method traverse():
        current = head
        while current != NULL:
            print(current.data)
            current = current.next

• insertAtStart adds a new node at the beginning of the list and updates the head.
• traverse prints each node’s data by following the next pointer from head to NULL.
• Singly linked lists are efficient for insertion and deletion at the head, but lack backward traversal.
  

2. Doubly Linked List

Each node contains pointers to both the next and previous nodes. This allows traversal in both directions.

Visual Representation:

NULL <- [Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next] -> NULL

Example:

Think of a web browser's history feature. You can navigate forward and backward through previously visited web pages because each page stores a reference to both the previous and next pages.

Pseudocode:

class Node:
    data
    prev
    next

class DoublyLinkedList:
    head
    tail

    method insertAtEnd(value):
        newNode = Node(value)
        if head == NULL:
            head = newNode
            tail = newNode
        else:
            tail.next = newNode
            newNode.prev = tail
            tail = newNode

    method traverseForward():
        current = head
        while current != NULL:
            print(current.data)
            current = current.next

    method traverseBackward():
        current = tail
        while current != NULL:
            print(current.data)
            current = current.prev

• insertAtEnd appends a node at the tail while maintaining both forward and backward links.
• traverseForward walks from head to tail, while traverseBackward goes in reverse.
• Useful when bidirectional access to elements is needed, like in navigation tools.
  

3. Circular Linked List

In a circular linked list, the last node points back to the first node, forming a loop. This structure is useful when you need to repeatedly loop through the list.

Visual Representation:

[Data|Next] -> [Data|Next] -> [Data|Next]
      ^                                 |
      |---------------------------------|

Example:

Consider a round-robin scheduling system where each process points to the next process. Once the last process finishes, control returns to the first process, creating an endless loop.

Pseudocode:

class Node:
    data
    next

class CircularLinkedList:
    head

    method insert(value):
        newNode = Node(value)
        if head == NULL:
            head = newNode
            newNode.next = head
        else:
            current = head
            while current.next != head:
                current = current.next
            current.next = newNode
            newNode.next = head

    method traverse():
        if head == NULL:
            return
        current = head
        do:
            print(current.data)
            current = current.next
        while current != head

• insert adds a node at the end, linking it back to the head to form a loop.
• traverse prints all nodes by looping through the list until it circles back to the head.
• Ideal for use cases that require circular access patterns, such as media playlists or time-sharing systems.
  

Efficiency Considerations

| Operation | Linked List | Array | |------------------------|----------------------------|--------------------------| | Insertion at Start | O(1) | O(n) (due to shifting) | | Deletion at Start | O(1) | O(n) | | Random Access | O(n) (Sequential Traversal) | O(1) | | Extra Memory | Pointers required | No pointers needed |

Linked lists excel in scenarios where frequent insertion and deletion at the start or middle are required. However, they lack random access, making traversal slower compared to arrays.

Real-World Analogy

Think of a scavenger hunt. Each clue (node) tells you where to find the next clue. You cannot jump to the last clue without following all previous ones, similar to traversing a linked list.

Use Cases:

• Implementing dynamic stacks and queues.
• Playlist applications where the next or previous song may vary.
• Undo/Redo functionality in text editors.
• Memory-efficient storage of variable-length data.

--- You will submit your answers in a text file named task.txt. Your answers should strictly follow the A, B, C, D format to be validated correctly. In this step, you learned about singly, doubly, and circular linked lists, how each type stores pointers and data, their operation efficiency and trade-offs, and their practical applications.

Next, you will explore Tree Structures to understand hierarchical data organization.

In this step, you will learn about Tree Structures, an essential data structure used to represent hierarchical relationships in computing.

What is a Tree?

A Tree is a non-linear hierarchical data structure made up of nodes connected by edges. Each node contains data and may point to multiple child nodes. Trees are widely used because they model hierarchical relationships effectively.

Key Terminology

| Term | Description | |----------|----------------------------------------------------------------| | Root | The topmost node with no parent. | | Leaf | A node with no children. | | Parent/Child | Directly connected nodes, where one node points to others. | | Height | Length of the longest path from the root to a leaf node. | | Depth | Distance from the root to a specific node. |

Types of Trees

Trees come in various types based on their structure and rules. The most commonly used types are:

1. Binary Tree (BT)
2. Binary Search Tree (BST)
3. Balanced Trees (AVL, Red-Black Trees)
4. General Trees

You will now understand these in detail.

1. Binary Tree (BT)

In a binary tree, each node has at most two children referred to as the left child and the right child.

Visual Representation:

        [10]
       /    
    [25]    [15]

Example:

Consider a family tree where each parent can have up to two children. Each family member (node) links to their immediate descendants (children), and the tree continues downward generation by generation.

Pseudocode:

class TreeNode:
    data
    left
    right

class BinaryTree:
    root

    method insertLeft(parent, value):
        parent.left = TreeNode(value)

    method insertRight(parent, value):
        parent.right = TreeNode(value)

    method inOrderTraversal(node):
        if node != NULL:
            inOrderTraversal(node.left)
            print(node.data)
            inOrderTraversal(node.right)

• TreeNode class holds the data and pointers to left and right child nodes.
• insertLeft and insertRight methods add child nodes to a given parent.
• You'll see the details on traversals in the Tree Traversal section below.

2. Binary Search Tree (BST)

A Binary Search Tree is a binary tree with the following rule:

• Left child’s value < Parent’s value
• Right child’s value > Parent’s value

This ordering allows efficient search, insertion, and deletion operations.

Visual Representation:

        [20]
       /    
    [10]    [30]

Example:

Consider a phone directory where entries are arranged alphabetically. Each node represents a name, and left/right child nodes represent names that come before/after alphabetically.

Pseudocode:

class TreeNode:
    data
    left
    right

class BinarySearchTree:
    root

    method insert(node, value):
        if node == NULL:
            return TreeNode(value)
        if value < node.data:
            node.left = insert(node.left, value)
        else:
            node.right = insert(node.right, value)
        return node

    method search(node, value):
        if node == NULL or node.data == value:
            return node
        if value < node.data:
            return search(node.left, value)
        else:
            return search(node.right, value)

• insert method maintains the BST property: left child < parent < right child.
• search method recursively checks if the target value exists in the tree.

--- info> You'll learn more about advanced tree variations in the upcoming steps.

3. Balanced Trees (AVL, Red-Black Trees)

Balanced trees ensure that the height of the tree remains approximately logarithmic to the number of nodes, providing guaranteed O(log n) performance for insertion, deletion, and search operations.

Balanced vs Unbalanced Trees

Understanding whether a tree is balanced or unbalanced is crucial, as it directly impacts the efficiency of tree operations.

Balanced Tree

A tree is balanced when the heights of the left and right subtrees of every node differ by at most a fixed number (commonly one). Balanced trees maintain their height close to O(log n), ensuring optimal search, insertion, and deletion times.

Balanced Tree:

        [15]
       /    
     [10]  [20]
     /  \    /  
   [5] [12][17] [25]

Unbalanced Tree

An unbalanced tree has subtrees whose heights differ significantly, often forming a skewed shape similar to a linked list. This leads to degraded performance (O(n)) for operations.

Visual Representation of an Unbalanced Tree:

     [5]
    /  
  [3] [10]
          
          [15]
             
             [20]
                
                [25]

Balanced trees prevent such degradation by self-adjusting during insertions and deletions.

AVL Tree:

AVL trees maintain strict balance by ensuring the height difference between the left and right subtrees of any node is at most one. Rotations are used to maintain balance after insertions and deletions.

Red-Black Tree:

Red-Black trees are a type of self-balancing binary search tree that enforces balance through node coloring (Red or Black) and specific properties about how nodes can be colored.

4. General Trees

General trees are more flexible and allow any number of children per node, unlike binary trees which limit to two children.

Example:

Consider a file system directory structure where each folder (node) can contain multiple subfolders and files (children).

Pseudocode:

class TreeNode:
    data
    children (list of TreeNode)

class GeneralTree:
    root

    method addChild(parent, value):
        newChild = TreeNode(value)
        parent.children.append(newChild)

    method traverse(node):
        if node != NULL:
            print(node.data)
            for child in node.children:
                traverse(child)

• TreeNode has a list of child nodes allowing multiple children.
• addChild method appends a new child node to the parent's children list.
• traverse method recursively visits all child nodes in the tree.

--- ## Tree Traversals

Once you understand the various types of trees, the next important concept is how to traverse them. Tree traversal refers to the process of visiting each node in the tree in a specific order. Traversals apply to all types of trees, including Binary Trees, Binary Search Trees, Balanced Trees, and General Trees.

The following are the common types of traversals:

1. In-Order Traversal (Left → Root → Right):

   • Visits the left subtree first, then the root, and finally the right subtree.
   • In Binary Search Trees, this traversal retrieves data in sorted order.

2. Pre-Order Traversal (Root → Left → Right):

   • Visits the root first, followed by the left and right subtrees.
   • Useful for creating a copy of the tree or prefix expression evaluations.

3. Post-Order Traversal (Left → Right → Root):

   • Visits the left and right subtrees before visiting the root.
   • Useful for deleting or freeing nodes in the tree.

4. Level-Order Traversal (Breadth-First):

   • Visits nodes level by level, starting from the root.
   • Useful for scenarios like printing the tree level by level or implementing shortest path algorithms in unweighted trees.

Traversal Example

Consider the following Binary Search Tree (BST):

        [8]
       /   
     [3]   [10]
     / \     
   [1] [6]   [14]
       / \    /
     [4] [7] [13]

Traversal Outputs:

1. In-Order Traversal (Left → Root → Right):

1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14

In a BST, in-order traversal returns the node values in ascending sorted order.

2. Pre-Order Traversal (Root → Left → Right):

8 → 3 → 1 → 6 → 4 → 7 → 10 → 14 → 13

3. Post-Order Traversal (Left → Right → Root):

1 → 4 → 7 → 6 → 3 → 13 → 14 → 10 → 8

4. Level-Order Traversal (Breadth-First):

8 → 3 → 10 → 1 → 6 → 14 → 4 → 7 → 13

These traversal techniques are fundamental and universally applicable to all tree structures, but as demonstrated, In-Order traversal is particularly useful in BSTs to retrieve sorted data.

Efficiency Considerations

| Operation | Balanced BST (Average) | Unbalanced BST (Worst Case) | Array/List | |-------------------|-----------------------|-----------------------------|-----------| | Search | O(log n) | O(n) | O(n) | | Insertion | O(log n) | O(n) | O(n) | | Deletion | O(log n) | O(n) | O(n) |

Balanced trees maintain efficient operations, while unbalanced trees degrade to linked list behavior in the worst case.

Real-World Analogy

Think of a company hierarchy chart. The CEO is at the top (root), department heads branch off from the CEO, managers branch off department heads, and so on. This forms a clear hierarchy much like a tree structure.

Use Cases:

• File system directories.
• Database indexing (B-Trees).
• Expression parsing in compilers.
• Organizational charts.

In this step, you learned about binary trees, binary search trees, balanced trees, and general trees, how they organize data hierarchically, their traversal techniques, operational efficiencies, and real-world applications.

Next, you will explore Hash Table to understand how key-value pairs are stored efficiently using hash functions, collision resolution techniques, and real-world applications of hash tables.

In this step, you will learn about Hash Table, a powerful data structure used to store key-value pairs efficiently. You will understand how hash tables use hash functions to quickly locate data, how collisions are resolved, and how resizing ensures optimal performance. ## Key Concepts

Hash Function

A hash function converts the key into an index within the bounds of the table size. A good hash function minimizes the chances of different keys producing the same index.

How a Hash Function Works

A hash function converts a key into a specific index within the bounds of the table size.

Example:

Suppose you have a hash table of size 10 and you want to store a key 25.

Hash Function:

index = key % table_size

Applying:

index = 25 % 10 = 5

The key 25 is stored at index 5 in the hash table.

Collision Handling

Since multiple keys may map to the same index (known as a collision), hash tables implement collision resolution strategies:

1. Separate Chaining:

   • Uses a linked list at each index to store multiple key-value pairs.

2. Open Addressing:

   • Searches for the next available slot in case of collision.
   • Techniques include linear probing, quadratic probing, and double hashing.

Load Factor

The load factor is the ratio of the number of stored elements to the size of the hash table. A high load factor increases the chances of collisions, affecting performance. Typically, a load factor greater than 0.7 prompts resizing of the table.

Resizing and Rehashing

As the number of elements grows, the load factor (entries / table size) increases. A high load factor leads to more collisions and degraded performance.

How Resizing Works:

1. Threshold Breach: When load factor exceeds 0.7, resizing is triggered.
2. Double the Table Size: The hash table’s size is increased (usually doubled).
3. Rehashing: All existing keys are rehashed and inserted into the new table to ensure correct placement.

Visual Representation

Example hash table of size 5:

Index | Data
--------------------
0     | NULL
1     | [Key: A, Value: 10] -> [Key: F, Value: 15] (collision handled)
2     | [Key: B, Value: 20]
3     | NULL
4     | NULL

Pseudocode: Inserting in a Hash Table (Separate Chaining)

class HashTable:
    size
    buckets (list of linked lists)

    method hashFunction(key):
        return key % size

    method insert(key, value):
        index = hashFunction(key)
        if buckets[index] is empty:
            create new linked list
        add (key, value) to linked list at buckets[index]

• hashFunction ensures keys map within table bounds.
• insert checks if the index is empty. If not, it adds to the linked list (Separate Chaining method).
• Ensures efficient handling of collisions.

Efficiency Considerations

| Operation | Average Case | Worst Case | |-------------------|-------------|------------| | Search | O(1) | O(n) | | Insert | O(1) | O(n) | | Delete | O(1) | O(n) |

Average case assumes a good hash function and low load factor. Worst case occurs when collisions result in a linked list or excessive probing.

Real-World Analogy

Think of a library catalog system where books are categorized based on the first letter. If multiple books share the same letter, they are organized in a list (handling collision). The catalog index speeds up the process of locating books based on their titles.

Use Cases:

• Implementing dictionaries/maps.
• Caching frequently accessed data.
• Indexing databases.
• Symbol tables in compilers.

--- In this step, you learned about hash tables, hash functions, collision handling, load factors, and real-world applications. You also explored how efficiency varies based on the quality of the hash function and collision management.

Next, you will learn about Priority Queues and Heaps, focusing on ordered element processing.

In this step, you will learn about Priority Queues and their most common implementation using Heaps. You will understand how elements are processed based on priority and how heaps maintain efficient insertion and removal operations.

What is a Priority Queue?

A priority queue is an abstract data structure where each element has a priority. Elements with higher priority are served before elements with lower priority, regardless of the order they were added.

Priority Queue Implementation

The most efficient implementation of a priority queue is through a Heap, typically a Binary Heap.

Binary Heap Properties:

1. Complete Binary Tree:

   • All levels are completely filled except possibly the last level, which is filled from left to right.

2. Heap Property:

   • Max-Heap: Parent node ≥ child nodes.
   • Min-Heap: Parent node ≤ child nodes.

Visual Representation: Max-Heap Example

        [50]
       /    
    [30]    [40]
   /   \     /
 [20] [10] [35]

--- ## Efficiency Considerations

| Operation | Time Complexity | |---------------------|-----------------| | Insert | O(log n) | | Delete Max/Min | O(log n) | | Peek Max/Min | O(1) |

Real-World Analogy

Think of an airport check-in counter where VIP passengers (higher priority) are served before others, regardless of when they arrived.

Use Cases:

• CPU process scheduling.
• Dijkstra’s algorithm (shortest path).
• Event simulation systems.
• Task scheduling systems.

Pseudocode: Inserting in a Max-Heap

class MaxHeap:
    heap (array)

    method insert(value):
        add value at the end of the heap
        current = index of value
        while current > 0 and heap[parent(current)] < heap[current]:
            swap heap[current] and heap[parent(current)]
            current = parent(current)

    method parent(index):
        return (index - 1) // 2

Explanation:

• insert places the new value at the end of the heap array and ensures the Max-Heap property is maintained by performing a bubble up operation. It compares the inserted value with its parent; if the inserted value is greater, they are swapped. This process repeats until the inserted value is correctly positioned or it becomes the root of the heap.
• parent calculates the parent index in the array-based heap representation.

Working Example:

Consider inserting the following values into an empty Max-Heap:

Sequence: 20, 15, 30, 40

Steps:

1. Insert 20:

[20]

2. Insert 15:

[20]
/
[15]

No need to bubble up; 15 < 20.

3. Insert 30:

[20]
/   
[15] [30]

Since 30 > 20, swap:

[30]
/   
[15] [20]

4. Insert 40:

[30]
/   
[15] [20]
/
[40]

40 > 15 → Swap:

[30]
/   
[40] [20]
/
[15]

40 > 30 → Swap:

[40]
/   
[30] [20]
/
[15]

Final Max-Heap:

        [40]
       /    
    [30]    [20]
    /
  [15]

Pseudocode: Inserting in a Min-Heap

class MinHeap:
    heap (array)

    method insert(value):
        add value at the end of the heap
        current = index of value
        while current > 0 and heap[parent(current)] > heap[current]:
            swap heap[current] and heap[parent(current)]
            current = parent(current)

    method parent(index):
        return (index - 1) // 2

Explanation:

• insert places the new value at the end of the heap array and ensures the Min-Heap property by performing a bubble up operation. It compares the inserted value with its parent; if the inserted value is smaller, they are swapped. This continues until the correct position is found.
• parent calculates the parent index in the array-based heap representation.

Working Example:

Consider inserting the following values into an empty Min-Heap:

Sequence: 40, 50, 30, 20

Steps:

1. Insert 40:

[40]

2. Insert 50:

[40]
/
[50]

No need to bubble up; 50 > 40.

3. Insert 30:

[40]
/   
[50] [30]

Since 30 < 40, swap:

[30]
/   
[50] [40]

4. Insert 20:

[30]
/   
[50] [40]
/
[20]

20 < 50 → Swap:

[30]
/   
[20] [40]
/
[50]

20 < 30 → Swap:

[20]
/   
[30] [40]
/
[50]

Final Min-Heap:

        [20]
       /    
    [30]    [40]
    /
  [50]

In this step, you explored how priority queues are implemented using binary heaps, understood the properties of Max-Heaps and Min-Heaps, analyzed the efficiency of heap operations, and walked through practical insertion examples. You also practiced related tasks to solidify your understanding.

Next, you will explore Advanced Tree Variations to understand specialized trees for specific applications.

In this step, you will learn about specialized tree structures that are optimized for specific performance and storage needs. You will understand how these advanced trees differ from basic binary trees and how they are used in real-world applications.

What are Advanced Trees?

Advanced trees are variations of basic tree structures that are designed to maintain balance, ensure efficient operations, or optimize storage and retrieval in specific contexts.

The most commonly used advanced trees are:

1. AVL Trees
2. Red-Black Trees
3. B-Trees and B+ Trees
4. Trie (Prefix Tree)

You will now explore each of these in detail.

1. AVL Tree

An AVL Tree is a self-balancing binary search tree where the height difference (balance factor) between the left and right subtrees of any node is at most 1. Whenever the tree becomes unbalanced after an insertion or deletion, rotations are performed to restore balance.

Visual Representation:

        [30]
       /    
    [20]    [40]
    /  
  [10] [25]

Key Characteristics:

• Strict height balance.
• Guarantees O(log n) time complexity for search, insert, and delete operations.

2. Red-Black Tree

A Red-Black Tree is a self-balancing binary search tree where each node has an extra bit for color (either Red or Black). The tree maintains balance through specific properties related to the coloring of nodes.

Key Properties:

• Every node is either red or black.
• The root is always black.
• No two red nodes can be adjacent.
• Every path from a node to its descendant NULL nodes contains the same number of black nodes.

Visual Representation:

        [30B]
       /    
    [20R]   [40B]

Red-Black Trees provide O(log n) time complexity for search, insert, and delete but are slightly more relaxed in balancing compared to AVL Trees.

3. B-Tree and B+ Tree

B-Trees are multi-way search trees optimized for systems that read and write large blocks of data, such as databases and file systems.

Key Characteristics:

• Nodes can have multiple children.
• Keeps data sorted and allows searches, insertions, and deletions in logarithmic time.
• Reduces disk I/O by storing multiple keys per node.

B+ Trees extend B-Trees by storing all values at the leaf level and linking leaf nodes for efficient sequential access.

Visual Representation:

      [10 | 20 | 30]
      /    |     
 [1-9] [11-19] [21-29]

4. Trie (Prefix Tree)

A Trie is a tree used for efficient retrieval of strings, commonly used in autocomplete and dictionary applications.

Visual Representation:

Root
 ├── a
 │   └── p
 │       └── p
 │           └── l
 │               └── e
 └── b
     └── a
         └── t

Key Characteristics:

• Each node represents a character.
• Paths from root to leaf represent valid strings.
• Provides fast prefix matching.

Efficiency Considerations

| Tree Type | Search | Insert | Delete | |-------------------|--------|--------|--------| | AVL Tree | O(log n)| O(log n)| O(log n)| | Red-Black Tree | O(log n)| O(log n)| O(log n)| | B-Tree/B+ Tree | O(log n)| O(log n)| O(log n)| | Trie | O(L) | O(L) | O(L) |

L = Length of the string in Trie operations.

Real-World Analogy

Think of a library indexing system:

• AVL/Red-Black Trees keep the index balanced to quickly locate any book.
• B-Trees/B+ Trees optimize for minimal shelf (disk) access by grouping multiple books per index entry.
• Tries are like alphabetically sorted card catalogs where you can jump directly based on prefixes.

Use Cases:

| Tree Type | Use Case | |-------------------|-----------------------------------------------| | AVL Tree | Memory-constrained applications needing strict balance | | Red-Black Tree | Language libraries (e.g., C++ STL maps, Java TreeMap) | | B-Tree/B+ Tree | Database indexing, file systems | | Trie | Autocomplete, spell-checking, dictionary lookups |

--- In this step, you explored advanced tree structures such as AVL Trees, Red-Black Trees, B-Trees, and Tries. You learned how they maintain balance, optimize performance, and are applied in various real-world scenarios.

Conclusion

In this lab, you explored foundational data structures essential to computing. You covered:

• Linked Lists (Singly, Doubly, Circular) and how they manage dynamic sequences.
• Tree Structures, including Binary Trees, Binary Search Trees, Balanced Trees, and General Trees, and learned about tree traversals.
• Hash Tables, focusing on hash functions, collision handling, and efficiency considerations.
• Priority Queues implemented via Binary Heaps, understanding both Max-Heap and Min-Heap variations.
• Advanced Tree Variations such as AVL Trees, Red-Black Trees, B-Trees, and Tries, and their specialized use cases.

You practiced validation tasks to reinforce key concepts, efficiency trade-offs, and real-world applications of each data structure.

Next Steps:

• Implement each data structure (Linked Lists, Trees, Hash Tables, Priority Queues) in your preferred programming language.
• Experiment with inserting, deleting, and searching operations to strengthen your understanding.
• Analyze how different data structures impact the efficiency and scalability of real-world systems.
• Explore the usage of advanced trees (AVL, Red-Black, B-Trees, Tries) in databases, compilers, and search engines.
• Proceed to more complex topics like Graphs, advanced algorithms, and problem-solving techniques to build upon this foundation.

Congratulations on completing the lab! You are now equipped to evaluate, apply, and optimize these core data structures in computational problems.