Computer Science 9618/41 — May/June 2021

Background Concept

To output the contents of a linked list, you do not loop through the array from index 0 to the end. Instead, you start at the first used node and repeatedly follow each node's pointer to the next one.

In an array-based linked list:

• startPointer gives the index of the first node
• each node's nextNode gives the index of the next node
• -1 means the end of the list

This is called traversal.

Understanding the Question

The procedure outputNodes() is given two parameters:

• the array linkedList
• the startPointer

It must output the data values that are actually in the linked list. That means it must follow the chain of nextNode values, not just print every element in the array.

Approach

Use a variable such as currentPointer.

1. set it to startPointer
2. while it is not -1
3. output the node's data
4. move to the next node using nextNode

This is the standard traversal pattern for a linked list.

Step-by-Step Reasoning

def outputNodes(linkedList, startPointer): defines a procedure that receives the array and the first node position.

currentPointer = startPointer means traversal begins at the first used node.

while currentPointer != -1: keeps processing nodes until the end of the list is reached.

Inside the loop:

• print(linkedList[currentPointer].data) outputs the data in the current node
• currentPointer = linkedList[currentPointer].nextNode moves to the next node in the chain

For the given data, the movement would be:

• start at index 0, output 1
• move to 1, output 5
• move to 4, output 2
• move to 2, output 6
• move to 7, output 56
• move to 3, output 7
• move to -1, stop

That shows why the values come out in linked-list order rather than numerical index order.

Key Takeaways

• Linked lists are processed by following pointers.
• The array index order is not necessarily the logical order of the list.
• The termination condition is the null marker, here -1.

Common Mistakes

• Using a for loop through all array positions; that would print unused nodes too.
• Starting at index 0 by assumption instead of using startPointer.
• Forgetting to update currentPointer, causing an infinite loop.
• Stopping at the wrong condition, such as when data == 0 instead of when nextNode reaches -1.

Things to Be Careful About

• Use linkedList[currentPointer].nextNode to move along the list.
• Use -1 as the end marker because that is what the structure uses.
• Output data, not nextNode.
• This procedure should work for any valid startPointer, not just the specific example shown.

Background Concept

When a traversal procedure is called on a linked list, the output sequence depends on the links between nodes, not on the physical array positions. The startPointer tells you where to begin, and each nextNode tells you where to go next.

Understanding the Question

This part asks you to edit the main program so that outputNodes() is called, then show what appears on the screen. There is no new algorithm here; the main task is to use the procedure from part (c)(i) and determine the correct output.

Approach

Call:

outputNodes(linkedList, startPointer)

Then follow the linked-list chain from the given structure to work out what the procedure prints.

Step-by-Step Reasoning

The start of the list is index 0 because startPointer = 0.

Now follow the links:

• index 0 has data 1, next 1
• index 1 has data 5, next 4
• index 4 has data 2, next 2
• index 2 has data 6, next 7
• index 7 has data 56, next 3
• index 3 has data 7, next -1

So the output order is:

1, 5, 2, 6, 56, 7

With the procedure as written, each value is printed on its own line.

Key Takeaways

• The visible order of output comes from pointer links.
• Always trace from startPointer to -1.
• Screenshot-style questions still depend on correct algorithm tracing.

Common Mistakes

• Printing in array index order: 1, 5, 6, 7, 2, ... which is wrong.
• Including free-list nodes such as indices 5, 6, 8 and 9.
• Forgetting that index 4 comes before index 2 in the linked structure.

Things to Be Careful About

• The screenshot should show only the active linked-list data.
• If your own program prints labels or extra text, your screenshot may differ in formatting, but the data sequence must still be correct.
• The actual values must be 1 5 2 6 56 7 in that order.

Background Concept

In an array-based linked list, unused nodes are often stored as a second linked list called the free-list. The pointer emptyList points to the first available empty node. When a new node is needed, the program removes the first node from the free-list and uses it.

To add a node at the end of the used linked list, the program must:

• check whether a free node exists
• take one node from the free-list
• place the new data into that node
• mark its nextNode as -1 because it will become the new last node
• find the current last node in the used list
• change that last node's nextNode to point to the new node

Understanding the Question

The function addNode() must:

• take the array and pointers as parameters
• input the data value to be added
• add a new node at the end of the linked list
• update the pointers correctly
• return a success result if it worked, otherwise return failure if no empty node is available

So this is not just a normal append to a Python list. It must preserve the linked-list structure shown in the array representation.

Approach

Use the free-list first.

1. If emptyList == -1, there is no spare node, so the function fails.
2. Otherwise, use the node at emptyList as the new node.
3. Advance emptyList to the next free position.
4. Store the input data in the chosen node and set its nextNode to -1.
5. Find the current last used node.
6. Point that last node to the new node.
7. Return success.

In Python, integers such as startPointer and emptyList are not passed by reference in the same way as some other languages, so returning the updated pointers alongside the Boolean result is a practical way to keep the caller updated.

Step-by-Step Reasoning

newData = int(input()) reads the value that will be added.

if emptyList == -1: checks whether there are any free nodes. If not, the function cannot insert anything, so it returns failure immediately.

newPointer = emptyList remembers the index of the free node we are about to use.

emptyList = linkedList[emptyList].nextNode moves the free-list pointer on to the next free node. This removes newPointer from the free-list.

Now the selected free node becomes a real used node:

• linkedList[newPointer].data = newData
• linkedList[newPointer].nextNode = -1

Setting nextNode to -1 is important because the new node is being added at the end.

If the used list were empty, startPointer would need to become newPointer. That is why the code checks if startPointer == -1:.

Otherwise, the list already has nodes, so the code traverses from the start until it finds the current last node, meaning the node whose nextNode is -1.

linkedList[currentPointer].nextNode = newPointer then connects the old last node to the new one.

Finally, the function returns success together with the updated pointers.

Key Takeaways

• Adding to an array-based linked list uses both the used list and the free-list.
• emptyList must be updated when a free node is taken.
• Appending requires changing the previous last node's pointer.
• A success/failure return value is useful when insertion may be impossible.

Common Mistakes

• Forgetting to move emptyList on to the next free node.
• Forgetting to set the new node's nextNode to -1.
• Overwriting the new node before saving its index.
• Traversing until currentPointer == -1 instead of stopping at the last valid node.
• Returning success without actually linking the node into the list.

Things to Be Careful About

• The free-list null marker is -1, not 0.
• The node taken from the free-list must be removed from the free-list before being reused.
• If you are writing Python, make sure the caller receives updated pointer values after the function call.
• Appending to the end means changing the old tail node's nextNode, not changing startPointer unless the list was empty.

Background Concept

A main program often coordinates smaller procedures and functions. A procedure such as outputNodes() performs an action, while a function such as addNode() performs an action and also returns a result. Here the returned result is used to decide which message to display.

Understanding the Question

You must edit the main program so that it:

• outputs the current linked list
• calls addNode()
• prints a suitable message depending on whether the addition succeeded
• outputs the linked list again afterwards

So the important skill here is sequencing the calls in the correct order.

Approach

The required order is exactly:

1. call outputNodes() before insertion
2. call addNode()
3. use if to display the success or failure message
4. call outputNodes() again after insertion

This makes the effect of the insertion visible.

Step-by-Step Reasoning

print("Before:") is a helpful label so the first traversal output is clearly identified.

outputNodes(linkedList, startPointer) shows the current list before any change is made.

result, startPointer, emptyList = addNode(...) calls the insertion function and stores the returned values. The Boolean result goes into result, while the pointers are updated for later use.

The if result: statement checks whether the insertion worked:

• if True, output Node added
• otherwise, output No empty node available

print("After:") labels the second list display.

outputNodes(linkedList, startPointer) is then called again so the user can see the list after the attempted insertion.

This exactly matches the wording of the question because the list is shown once before and once after the call to addNode().

Key Takeaways

• Procedures and functions are often combined in a main control sequence.
• A returned Boolean is commonly used with an if statement to choose output.
• Showing data before and after an update is a useful testing technique.

Common Mistakes

• Calling outputNodes() only once.
• Printing the message before calling addNode().
• Forgetting to store the returned updated pointers.
• Using the wrong condition for the success message.

Things to Be Careful About

• Keep the calls in the order the question specifies.
• Make sure the second outputNodes() call uses the updated linked list state.
• If your function returns updated pointers in Python, the assignment when calling it must match that return structure exactly.

Background Concept

Testing a linked-list operation means tracing both the pointer updates and the visible output. When a node is appended, the logical order of the list changes even though most of the array stays the same.

The free-list is especially important here because the new node must come from the first available empty position.

Understanding the Question

You must run the finished program with input value 5 and show the output. To work that out, you need to know both:

• what the list looks like before insertion
• what changes after addNode() uses the next free node

Approach

Trace the insertion step by step.

1. output the original list
2. add value 5 using the first free node
3. update the free-list and the last used node's pointer
4. output the list again

That gives the exact sequence that should appear in the screenshot.

Step-by-Step Reasoning

Before insertion, the linked list is:

0 -> 1 -> 4 -> 2 -> 7 -> 3 -> -1

So the data output before the call is:

• 1
• 5
• 2
• 6
• 56
• 7

Now trace addNode() with input 5.

The first free node is at index 5 because emptyList = 5.

So the new node will use index 5.

Then emptyList is updated to the next free node, which is index 6, because index 5 originally had nextNode = 6.

The new node at index 5 is changed to:

• data = 5
• nextNode = -1

Now the current last used node must be found. Before insertion, the tail is index 3 because it has nextNode = -1.

So index 3 is updated so that nextNode = 5.

The used list is now:

0 -> 1 -> 4 -> 2 -> 7 -> 3 -> 5 -> -1

Therefore the second traversal outputs:

• 1
• 5
• 2
• 6
• 56
• 7
• 5

Since a free node was available, the message shown is Node added.

Key Takeaways

• Testing linked-list code often means tracing pointer changes manually.
• Appending adds the new value at the end of the logical list, not at the next numerical index in display order.
• The free-list head moves on after a node is allocated.

Common Mistakes

• Assuming the new value replaces an existing 5 rather than being appended as a new node.
• Forgetting that the original list is displayed before the insertion happens.
• Updating the free-list incorrectly and choosing the wrong index for the new node.
• Missing the final 5 at the end of the second output.

Things to Be Careful About

• The value entered is 5, but there is already a 5 in the list; duplicates are allowed because the list is unordered.
• The first output is unchanged from the original list.
• The new node uses index 5 only because that is where emptyList points initially.
• If your own program includes an input prompt, the exact screenshot formatting may vary, but the list content and success message must still be correct.