Linked Lists and Hash Tables

1 Describe one advantage and one disadvantage of storing a list of items in a linked list rather than in an array. 3

One mark for each of the following, to a maximum of 3.

• Advantage: an item can be inserted or deleted by changing pointers, without shifting other items
• Advantage: the list can grow and shrink one node at a time, so no size has to be fixed
• Disadvantage: items cannot be accessed directly by index, so each one must be reached by following pointers from the head
• Disadvantage: each node needs extra memory for a pointer

Model answer. An advantage is that an item can be inserted or removed by changing a couple of pointers, without shifting all the other items along as an array would need to. A disadvantage is that items cannot be accessed directly by their position, so to reach the fifth item the program must follow the pointers from the head through the four nodes before it.

2 The linked list shown is held in two arrays. The head pointer is 2, the free pointer is 1, and -1 indicates the end of a list. State the items in the list, in order. A new item, 20, is to be stored so that it comes between 17 and 23, using the first free location. State the value that must be stored in each of data[1] and next[1], the change that must be made to next[0], and the new value of the free pointer. 5

One mark for each of the following, to a maximum of 5.

• The items in order are 9, 17, 23
• data[1] is 20
• next[1] is 3, the old pointer of 17
• next[0] is changed to 1
• The free pointer moves on to 4

Model answer. Starting at head 2 gives 9, whose pointer is 0, which gives 17, whose pointer is 3, which gives 23, whose pointer is -1. The items in order are 9, 17, 23. To insert 20, the first free location is index 1, so data[1] is set to 20, and next[1] is set to 3, which is what 17 currently points at. Then next[0] is changed to 1 so that 17 now points at the new item, and the free pointer moves on to 4, the next unused place. If next[0] were changed first, the pointer to 23 would be lost.

3 The hash function for a hash table of size 7 is the key MOD 7, and a collision is resolved by linear probing, moving to the next slot and wrapping from slot 6 to slot 0. The table is empty. Show where the keys 15, 22, 8 and 29 are stored, if they are added in that order. 4

One mark for each of the following, to a maximum of 4.

• 15 is stored in slot 1, because 15 MOD 7 is 1
• 22 hashes to slot 1, which is taken, so it is stored in slot 2
• 8 hashes to slot 1, and slots 1 and 2 are taken, so it is stored in slot 3
• 29 hashes to slot 1, and slots 1, 2 and 3 are taken, so it is stored in slot 4

Model answer. 15 MOD 7 is 1, so 15 goes in slot 1. 22 MOD 7 is also 1, which is occupied, so linear probing moves on and 22 is stored in slot 2. 8 MOD 7 is 1, and slots 1 and 2 are occupied, so 8 goes in slot 3. 29 MOD 7 is 1 as well, and slots 1, 2 and 3 are occupied, so 29 is stored in slot 4.

4 Explain how a hash table stores and retrieves a record, and describe one way of dealing with collisions. 6

One mark for each of the following, to a maximum of 6.

• A hash function is applied to the key of the record
• The result is used as the index of the position in the table where the record is stored
• To retrieve it, the same hash function is applied to the key, so the position is found directly without searching
• A collision occurs when two keys give the same index
• In chaining, each position holds a list of the records that hash to it, and a new record is added to that list
• Alternatively with linear probing the next free slot is used, and a lookup follows the same sequence until it finds the key or an empty slot

Model answer. To store a record, a hash function is applied to its key, and the result is used as the index of the position in the table where the record is kept. To retrieve it, the same hash function is applied to the key again, which gives the position directly, so there is no need to search through the other records. A collision happens when two keys produce the same index. With chaining, each position in the table holds a list of all the records that hash to it, and a new record is added to the end of that list, so a lookup calculates the position and then searches the short list. With linear probing, the record is instead put in the next free slot, and a lookup follows the same sequence of slots until it finds the key or reaches an empty slot.

5 A linked list is made of nodes. Each node has the attributes data and next, and next is None for the last node. Write a Python function called count_nodes that takes the first node, called head, of a linked list and returns the number of nodes in the list. 4

One mark for each of the following, to a maximum of 4.

• Defines a function with the head as a parameter
• A counter that starts at 0
• A loop that moves to the next node until the end, which is None
• Counts each node and returns the result

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

def count_nodes(head):
    count = 0
    current = head
    while current is not None:
        count = count + 1
        current = current.next
    return count

print(count_nodes(Node(4, Node(8, Node(15)))), count_nodes(None))