Chains made of pointing nodes

Computing · Algorithms & Data Structures · ages 16-18

Name ______________________ Date ____________

In a correctly formed singly linked list, what does a node's null next reference mark?
- It marks an unused node with no stored value.
- It marks the first node visited during each traversal.
- It marks the last node visited during this traversal.
In the singly linked list taught here, what does each node hold?
- A value and copies of every later node's data
- A value and a reference to the next node
- A value and its array index, without any links
A singly linked list has at least five nodes. Using only head and next references, how do you reach its fifth node?
- Start at head and follow four next references
- Start at head and follow five next references
- Use the position to calculate its array address
Start with 3 -> 4 -> 5. You already hold a reference to node 3. Which update removes node 4 from this chain?
- Set 3.next to the node holding 5.
- Set 3.next to null and leave 4.next unchanged.
- Set 5.next to the node holding 3 instead.
Start with 3 -> 4 -> 5 and a new node X. Which ordered updates insert X after 3 while preserving the route to 4?
- Set 3.next to X, then set X.next to 3.next.
- Set X.next to 4, then set 3.next to X.
- Set X.next to 3, then set 4.next to X.
Starting with only head, linked-list access takes fixed work as the requested position grows, just like array access by index.
Circle one: True False
A middle node's next is set to null. Head is the only saved entry reference, and no separate reference into the detached tail remains. What follows?
- Traversal from head automatically restores the reference into the detached tail.
- Traversal from head loses access to every node before the break.
- Traversal from head cannot reach nodes in the detached tail.
An array and a singly linked list each store 6, 12, 18, 24. Insert 15 between 12 and 18, keeping order. The array has room at its end; you already hold list node 12. Which comparison is correct?
- Both structures shift 18 and 24 to later storage positions before inserting 15.
- The array changes two next references; the list shifts 18 and 24 to later positions.
- The array shifts 18 and 24; the list changes two next references.

Answer key

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

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

It marks the last node visited during this traversal. · There is no following node. Traversal stops after visiting this node.
A value and a reference to the next node · The value is the node's own data. Its next reference leads to another node, or is null at the end.
Start at head and follow four next references · Head identifies the first node before any next step. Four steps reach the fifth node.
Set 3.next to the node holding 5. · Make the predecessor refer to the target's successor. Traversal then goes from 3 directly to 5.
Set X.next to 4, then set 3.next to X. · Link X to the old successor before linking 3 to X. The result is 3 -> X -> 4 -> 5.
False · Farther positions require more next-reference steps. Array index access does not walk through earlier elements.
Traversal from head cannot reach nodes in the detached tail. · The walk stops at the new null. Without another entry reference, the program has no route into the detached tail.
The array shifts 18 and 24; the list changes two next references. · The array moves 18 and 24 one position right to make room. The list keeps its existing nodes in place and inserts 15 with two next assignments.