Show understanding that a stack, queue and linked list are examples of ADTs
10.4 Introduction to Abstract Data Types (ADT)
An Abstract Data Type (ADT) is a mathematical model for data that defines the operations that can be performed on it, without specifying how these operations are implemented. Think of it as a contract: what can be done with the data, not how it is done.
Stack – The Stack of Plates 🍽️
A stack is a collection that follows the Last In, First Out (LIFO) rule. Imagine a stack of plates: you add (push) a plate on top, and you remove (pop) the top plate first.
| Operation | Description | Time Complexity |
|---|---|---|
| push(x) | Add element x to the top. | $O(1)$ |
| pop() | Remove and return the top element. | $O(1)$ |
| peek() | Return the top element without removing it. | $O(1)$ |
Exam Tip: When asked to implement a stack, remember that push and pop should be constant time. Use an array or linked list with a pointer to the top.
Queue – The Ticket Line 🎟️
A queue follows the First In, First Out (FIFO) rule. Picture a line at a ticket counter: the first person in line is the first to be served.
| Operation | Description | Time Complexity |
|---|---|---|
| enqueue(x) | Add element x to the rear. | $O(1)$ |
| dequeue() | Remove and return the front element. | $O(1)$ |
| front() | Return the front element without removing it. | $O(1)$ |
Exam Tip: For a queue, use a circular array or a linked list with head and tail pointers to achieve $O(1)$ enqueue and dequeue.
Linked List – The Chain of Beads 🔗
A linked list is a sequence of nodes where each node points to the next one. Think of a chain of beads: each bead knows where the next bead is.
| Operation | Description | Time Complexity |
|---|---|---|
| insert(pos, x) | Insert element x at position pos. | $O(n)$ (need to traverse to pos) |
| delete(pos) | Delete element at position pos. | $O(n)$ |
| search(x) | Find element x. | $O(n)$ |
Exam Tip: When implementing a linked list, remember that insertion or deletion at the head is $O(1)$, but at an arbitrary position requires traversal ($O(n)$).
Key Takeaways
- ADTs define operations and their time complexities, not implementation details.
- Stack: LIFO, push/pop/peek – $O(1)$.
- Queue: FIFO, enqueue/dequeue/front – $O(1)$.
- Linked List: dynamic size, insert/delete/search – $O(n)$ (except at head).
- Use appropriate data structures to meet performance requirements in exams.
Revision
Log in to practice.
2 views
0 suggestions