Linked Lists and Nodes That Point · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Chains made of pointing nodes

Computing · Algorithms & Data Structures · ages 16-18
Name ______________________   Date ____________

  1. What does a null next reference mark?

    • A broken list
    • The fastest node
    • The end of the chain

  2. What does one linked list node hold?

    • Only a value with no links
    • A value plus a next reference to the node after it
    • The whole list copied inside

  3. How do you reach the fifth node of a linked list?

    • Jump straight there by index arithmetic
    • Start at the first and follow next references one by one
    • Ask the last node

  4. How do you delete node 4 from the middle?

    • Point node 3 straight at 5, skipping the removed node
    • Delete every node after 4 as well
    • Null out node 3

  5. Which two pointer changes insert a node between 3 and 4?

    • Node 3 points at 5 and node 5 points back
    • The newcomer points at 4, then node 3 swings onto the newcomer
    • Node 4 points at 3 and the newcomer points at null

  6. Linked list access by position is as fast as array access.

    Circle one:   True   False

  7. A next reference is lost mid-chain before its replacement is set. What happens?

    • Nothing, lists repair themselves
    • Only the first node is lost
    • Every node past the break is stranded and unreachable

  8. Draw four nodes, insert a value after the second node. Which operation is cheap here and which is expensive?

    • Access is cheap and insertion is expensive
    • Insertion is cheap at two pointer changes while access by position is an expensive walk
    • Both are free of cost
LightMySky · lightmysky.comW1-mt_HvY7_-M2Zj-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Chains made of pointing nodes W1-mt_HvY7_-M2Zj-s1

  1. The end of the chain · Null means nothing comes after.
  2. A value plus a next reference to the node after it · Value plus pointer, hooked like paper clips.
  3. Start at the first and follow next references one by one · No index exists, so you walk the chain.
  4. Point node 3 straight at 5, skipping the removed node · One change unhooks the target.
  5. The newcomer points at 4, then node 3 swings onto the newcomer · Link the newcomer forward first, then swing the predecessor across.
  6. False · Lists walk node by node while arrays jump by index.
  7. Every node past the break is stranded and unreachable · With no pointer leading in, the tail cannot be reached.
  8. Insertion is cheap at two pointer changes while access by position is an expensive walk · Pointer surgery beats shifting, but walking beats no index.
Worksheet · LightMySky