Study Notes

# Study Notes: [Subject / Topic]

**Course:** [Course Name]
**Date:** January 15, 2024
**Lecture:** Week 3 — Data Structures
**Textbook:** Chapter 5, pages 120–145

---

## Key Concepts

| Concept | Definition |
|---------|-----------|
| Array | Fixed-size, contiguous memory block |
| Linked List | Nodes connected by pointers |
| Stack | LIFO (Last In, First Out) |
| Queue | FIFO (First In, First Out) |
| Hash Table | Key-value store with O(1) average lookup |

## Detailed Notes

### Arrays

- Stored in contiguous memory locations
- Access by index: O(1)
- Insertion/deletion: O(n) — requires shifting elements
- Best for: random access, known size

### Linked Lists

- Each node stores data + pointer to next node
- Types: singly linked, doubly linked, circular
- Insertion/deletion at head: O(1)
- Search: O(n) — must traverse from head
- Best for: frequent insertions/deletions, unknown size

### Hash Tables

- Maps keys to indices using a hash function
- Handles collisions via chaining or open addressing
- Average case: O(1) for insert, delete, lookup
- Worst case: O(n) when all keys collide

## Examples

### Implementing a Stack

```python
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        return self.items[-1] if self.items else None

    def is_empty(self):
        return len(self.items) == 0
```

## Comparison Table

| Operation | Array | Linked List | Hash Table |
|-----------|-------|-------------|------------|
| Access | O(1) | O(n) | O(1) avg |
| Search | O(n) | O(n) | O(1) avg |
| Insert | O(n) | O(1)* | O(1) avg |
| Delete | O(n) | O(1)* | O(1) avg |

*At known position

## Practice Questions

1. When would you choose a linked list over an array?
2. What happens when a hash table's load factor exceeds 0.75?
3. Implement a queue using two stacks.
4. What is the time complexity of searching in a balanced BST?

## Summary

- Arrays are best for indexed access; linked lists for dynamic size.
- Hash tables provide fast lookups but use more memory.
- Choose data structures based on the most frequent operation.

---

**Next lecture:** Trees and Graphs (Week 4)
**Assignment due:** Problem Set 3 — January 22