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.

Display limit of 8 items per collection

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

      1. Add a new item at the top.
      2. Remove the item at the top.
      3. Check for an empty stack before removing.

      Queue

      1. Add a new item at the rear.
      2. Remove the item at the front.
      3. Check for an empty queue before removing.

      Predict before trying

      Start with empty collections. Add X, then Y, then X. Which value is removed first from the stack and from the queue?

      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.

      Display limit of 6 nodes

        Choose an operation to see which links change.
        Read the procedure
        1. To insert at the head, make the new node point to the old head. Then make head point to the new node.
        2. 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.
        3. To delete the head, move head to the next node.
        4. 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.

        Which link changes?

        For head → N1 → N2 → N3 → None, delete N2. Where must N1 point next?

        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.

        A binary tree with six nodesA has left child B and right child C. B has left child D and right child E. C has only a right child F. D, E and F are leaves. A B C D E F

        The number below a visited node shows its visit position. The outlined node is the most recent visit.

        Output so far

        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.

        Think about the root

        Using this tree, which node is visited last in postorder?

        Based on Lecture 11, slides 14 through 19. The example is an ordinary binary tree, not a binary search tree.