I’m new to linked lists, so this question drove me up the wall! The question (in question) is from an A Level computer science past paper (from summer 2021 variant 42).

The main demands of this question aren’t anything too complicated. They were:

1. create a node class
2. write a procedure to output the nodes in the linked list
3. write a function that adds a node to the linked list

Foreword

This exam wanted you to implement the linked list as an array of node objects, with your null pointers represented as a -1.

1. Create a node class

I chose the long route to do this, where a node’s pointer defaults to -1. My class definition looked as such:

1class Node:
2  def __init__(self, data):
3    self.data = data
4    self.next_node = -1

Then I created a list of nodes. The values and the pointers were given in the exam.

 1linked_list = [
 2    Node(1),
 3    Node(5),
 4    Node(6),
 5    Node(7),
 6    Node(2),
 7    Node(0),
 8    Node(0),
 9    Node(56),
10    Node(0),
11    Node(0),
12]
13
14# linking the list
15linked_list[0].next_node = 1
16linked_list[1].next_node = 4
17linked_list[2].next_node = 7
18linked_list[3].next_node = -1
19linked_list[4].next_node = 2
20linked_list[5].next_node = 6
21linked_list[6].next_node = 8
22linked_list[7].next_node = 3
23linked_list[8].next_node = 9
24linked_list[9].next_node = -1

The exam tells you to declare a variable that points to the next free space in the list and another that points to its start (“start_pointer”) with the values 5 and 0 respectively.

What I found rather upsetting about this question is that it doesn’t tell you that a free space in this list is denoted by a 0! It also tells you to delcare a variable called “empty_list” but doesn’t tell you what that is for! I figured both of these things out only by looking at the mark scheme! “empty_list” is supposed to denote the index of the next free space in the list. They could have at least given that variable a decent name, like “next_free_space”! Preposterous!

1empty_list = 5
2start_pointer = 0

2. Write a procedure to output the nodes in the linked list

Fairly simple logic here: we want to print the data in all nodes until the node points to a -1. Or, print the data in nodes while the node’s pointer is not -1.

For clarity and testing purposes, I also printed the node’s pointer along with its data.

1def output_nodes(ll, current_pointer):
2    while current_pointer != -1:
3        print(ll[current_pointer].data, " points to index", ll[current_pointer].next_node)
4        current_pointer = ll[current_pointer].next_node

3. Write a function that adds a node to the linked list

Here’s the logic:

1. check if there is a free space available
2. find the “last” node (a.k.a. the linked node that points to a -1)
3. make this “last” node point to the free space
4. insert value at the free space
5. update the “empty_list” pointer to point to the next available free space

The question also wants us to return True if there is a free space and False if there isn’t.

Being new to linked lists, I found this rather tricky! But here’s the solution I found:

 1def add_node(ll, current_pointer, input_data):
 2  # ll is short for linked list
 3  global empty_list
 4
 5  # check if there is a free space available
 6  if ll[empty_list].data == 0:
 7    for node in ll:
 8      # make the "last" node point to the empty space if it points to -1 
 9      if node.next_node == -1:
10        node.next_node = empty_list
11        break
12        
13    # add data to the free space and make it point to -1
14    ll[empty_list].data = input_data
15    ll[empty_list].next_node = -1
16
17    # determine the next free space
18    for i in range(len(ll)):
19      if ll[i].data == 0:
20        empty_list = i
21        break
22
23    return True
24  else:
25    return False

Testing

We’ll add 5 items to the linked list (even though there are only 4 free spaces) and then run output_nodes().

1print(add_node(linked_list, start_pointer, 5))
2print(add_node(linked_list, start_pointer, 6))
3print(add_node(linked_list, start_pointer, 7))
4print(add_node(linked_list, start_pointer, 8))
5print(add_node(linked_list, start_pointer, 9))
6output_nodes(linked_list, start_pointer)

Here’s the output I got:

 1True
 2True
 3True
 4True
 5False
 61 points to index 1
 75 points to index 4
 82 points to index 2
 96 points to index 7
1056 points to index 3
117 points to index 5
125 points to index 6
136 points to index 8
147 points to index 9
158 points to index -1

We can see that 9 wasn’t added to the list!

Conclusion

I did NOT like this question for the reasons I stated in the first section, but being new to linked lists and after having bashed my head against the wall for a while, I’m happy I was able to do this!