Lectures 9, 10 and 11
Data structures
in motion
Change a collection. Follow a link. Choose a path through a tree. Make a prediction before each step.
Optional practice. Exams are based on lecture notes.
These diagrams explain the operations. They do not trace every line of the lecture code.
Lecture 9
Same items, different removal
Add a value to both collections. Then compare which value each collection removes.
Stack
Last in, first out
Bottom → Top
No value removed yet.
Queue
First in, first out
Front → Rear
No value removed yet.
A, B and C were added in that order. The next removed values will differ.
Read the procedure
Stack
- Add a new item at the top.
- Remove the item at the top.
- Check for an empty stack before removing.
Queue
- Add a new item at the rear.
- Remove the item at the front.
- Check for an empty queue before removing.
Based on the longer Lecture 9, slides 25 through 32 and 49 through 56.
Lecture 10
Change the links, not the values
Each node has a value and a link to the next node. The node ID identifies the node even when values repeat.
Positions start at 0. Position 0 is the head. Inserting at the list length adds a node at the end. The value field is used only when inserting.
Read the procedure
- To insert at the head, make the new node point to the old head. Then make head point to the new node.
- To insert later, find the previous node. Make the new node point to its successor. Then make the previous node point to the new node.
- To delete the head, move head to the next node.
- To delete later, make the previous node point to the removed node’s successor.
The drawing places nodes next to each other for readability. The links, not their physical positions, define the list.
Based on the longer Lecture 10, slides 13 through 23. Node IDs are labels added for this visual explanation.
Lecture 11
One tree, four visit orders
This is an ordinary binary tree. Left and right describe child positions. There is no value ordering rule.
The lecture uses preorder for DFS and a queue for BFS. Inorder and postorder are optional comparisons.
The number below a visited node shows its visit position. The outlined node is the most recent visit.
Output so far
Waiting queue
Front is on the left
Read the procedure
This demo advances between visits. It does not show every function call or every internal operation. Explore the call stack for recursive execution.
Based on Lecture 11, slides 14 through 19. The example is an ordinary binary tree, not a binary search tree.