| title |
Data Structures Overview |
| created |
2025-05-18 09:15:00 UTC |
| modified |
2025-05-20 14:30:00 UTC |
| tags |
coursework |
computer science |
algorithms |
|
| author |
Student001 |
| status |
complete |
| priority |
2 |
- Contiguous memory allocation
- O(1) access time
- Fixed size in many languages
- Dynamic arrays (e.g., ArrayList in Java, List in C#) can resize automatically
- Non-contiguous memory allocation
- O(n) access time
- O(1) insertion/deletion at known positions
- Types: Singly linked, Doubly linked, Circular
- LIFO (Last In, First Out) principle
- Operations: push, pop, peek
- Applications: Function calls, Undo mechanisms, Expression evaluation
- FIFO (First In, First Out) principle
- Operations: enqueue, dequeue, peek
- Applications: Job scheduling, Print spooling, Message queues
- Key-value pairs
- O(1) average case for insertion, deletion, lookup
- Collision resolution: Chaining, Open addressing
- Load factor affects performance
- Hierarchical structure
- Binary trees, AVL trees, Red-Black trees, B-trees
- Tree traversals: Inorder, Preorder, Postorder, Level order
- Compare and contrast arrays vs. linked lists
- When would you choose a hash table over a binary search tree?
- Implement a stack using arrays and linked lists
Note to self: Prepare implementation examples for midterm project