📖 Chapter 2: Abstract Data Types (ADTs)

What this chapter covers: This chapter introduces fundamental Abstract Data Types (ADTs) such as Stacks and Queues. It explains their principles, main methods, and implementation costs using both array-based and linked list-based approaches. Understanding ADTs is essential for designing efficient algorithms.

🔑 Essential Concepts & Formulas

🛠️ Problem Types

Type A: Implementing a Stack with a Linked List

Setup: "When you need to implement a stack using a linked list data structure."

Method: "Use the head of the linked list as the top of the stack. The push operation adds a new node at the head, and the pop operation removes the node from the head. Both operations should take O(1) time."

Example: "Implement a stack with push(1), push(2), pop(), push(3), pop(). The stack should output 2, 3."

Type B: Implementing a Queue with a Circular Array

Setup: "When you need to implement a queue using a circular array to avoid shifting elements."

Method: "Use two pointers, front and rear, to track the front and rear of the queue. When enqueuing, add the element at rear and increment rear modulo the array size. When dequeuing, remove the element at front and increment front modulo the array size."

Example: "Implement a queue with enqueue(1), enqueue(2), dequeue(), enqueue(3), dequeue(). The queue should output 1, 2."

🧮 Solved Example

Problem: Implement a stack using an array.

Given: An array stack and a top index.

Steps:

1. Initialize top to -1.
2. push(x): Increment top and set stack[top] = x.
3. pop(): Return stack[top] and decrement top.

"

✅

Answer: ```python class ArrayStack: def init(self, capacity): self.stack = [None] * capacity self.top = -1 self.capacity = capacity

code
Copy
def push(self, x):
    if self.top == self.capacity - 1:
        raise Exception("Stack Overflow")
    self.top += 1
    self.stack[self.top] = x

def pop(self):
    if self.top == -1:
        raise Exception("Stack Underflow")
    item = self.stack[self.top]
    self.top -= 1
    return item

code
Copy

### ⚠️ **Common Mistakes**

**❌ Mistake 1:** Stack overflow when pushing onto a full array-based stack.

**✅ How to avoid:** Check if the stack is full before pushing.

**❌ Mistake 2:** Queue underflow when dequeuing from an empty queue.

**✅ How to avoid:** Check if the queue is empty before dequeuing.

### 💡 **Study Tip**
Visualize the behavior of stacks and queues with diagrams. Practice implementing these ADTs using both arrays and linked lists to understand their trade-offs.

---

## 📖 Chapter 3: Lists and Trees
**What this chapter covers:** This chapter covers Index Lists, Positional Lists, and Trees. It explains how elements are accessed and manipulated in these structures. Understanding these concepts is crucial for building more complex data structures and algorithms.

### 🔑 Essential Concepts & Formulas
| **Concept/Formula** | **Definition/Equation** | **When to Use** | **Quick Check** |
|---------------------|-------------------------|-----------------|-----------------|
| **Index List** | Access by index. | When element order matters and index-based access is needed. | Verify index boundaries. |
| **Positional List** | Access by position. | When relative element order matters and position-based access is needed. | Check `before()` and `after()` methods. |
| **Tree** | Hierarchical data structure. | Representing hierarchical relationships. | Verify parent-child relationships. |
| **ArrayList Add(i, e)** | Insert element at index i, O(n) | Inserting into an index list. | Confirm correct element shifting. |
| **Doubly Linked List AddBefore(p, e)** | Insert element before position p, O(1) | Inserting into a positional list. | Check pointer updates. |

### 🛠️ Problem Types

**Type A: Implementing an Index List with an Array**

*Setup:* "When you need to implement an index list using an array and analyze the time complexity of its operations."

*Method:* "Use an array to store the elements. The `get(i)` operation takes O(1) time. The `add(i, e)` and `remove(i)` operations take O(n) time because elements need to be shifted."

*Example:* "Implement an index list with `add(0, 1)`, `add(1, 2)`, `get(0)`, `remove(0)`. The list should output 1, and the remaining element should be 2."

**Type B: Implementing a Positional List with a Doubly Linked List**

*Setup:* "When you need to implement a positional list using a doubly linked list and analyze the time complexity of its operations."

*Method:* "Use a doubly linked list to store the elements. The `before(p)`, `after(p)`, `addBefore(p, e)`, `addAfter(p, e)`, and `remove(p)` operations all take O(1) time because nodes can be inserted and removed by updating pointers."

*Example:* "Implement a positional list and perform operations to add and remove elements at specific positions."

### 🧮 Solved Example
**Problem:** Implement a function to find the height of a binary tree.

**Given:**
The root node of a binary tree.

**Steps:**
1. If the root is None, return 0.
2. Recursively calculate the height of the left subtree.
3. Recursively calculate the height of the right subtree.
4. Return the maximum of the left and right subtree heights, plus 1.



> [!success] **Answer:** ```python
def height(root):
  if root is None:
    return 0
  left_height = height(root.left)
  right_height = height(root.right)
  return max(left_height, right_height) + 1

⚠️ Common Mistakes

❌ Mistake 1: Forgetting to handle the case where the root is None when calculating the height of a tree.

✅ How to avoid: Always check for the base case (empty tree) in recursive functions.

❌ Mistake 2: Incorrectly updating pointers when inserting or removing elements in a positional list.

✅ How to avoid: Carefully manage the pointer updates to maintain the integrity of the list.

💡 Study Tip

Draw diagrams of trees and lists to visualize their structure and operations. Practice implementing these data structures to reinforce your understanding.