MA214 Algorithms and Data Structures
2023/24
Exercises 6
(linked lists, stacks, queues, hashing)
Exercise 6.1. Linked lists 4 pts
Consider the implementation of a singly linked list LinkedList.py, discussed in the lec-ture and available from Moodle. This implementation just has a head pointer. It also comes with just two methods: isEmpty(self) and add(self,item). The first one checks whether the linked list is empty; the latter one adds an item at the front of the linked list.
1 class Node :
2 def __init__ ( self , item , next ) :
3 self . item = item
4 self . next = next
5
6 class LinkedList :
7 def __init__ ( self ) :
8 self . head = None
9
10 def isEmpty ( self ) :
11 return self . head == None
12
13 def add ( self , item ) :
14 temp = Node ( item , self . head )
15 self . head = temp
(a) Explain in words which changes would be required to have a head and a tail pointer. Implement these changes in Python.
(b) Explain in words how to remove an element from the front of a singly linked list. Implement this method in Python. What is the time complexity of this method? Justify your answer.
(c) Explain how to remove the element at the end of the singly linked list. Implement this method in Python. What is the time complexity of this method? Justify your answer.
Exercise 6.2. Stacks and queues 3 pts
(a) Explain how to implement a queue using two stacks. Analyse the running time of the queue operations enqueue and dequeue.
(b) Explain how to implement a stack using two queues. Analyse the running time of the stack operations pop and push.
Exercise 6.3. Hashing 3 pts
Suppose you need to insert unique 3-character IDs into a hash table, where each ID is made up of some combination of two of the capital letters A-D, followed by one of the lower case letters x-z, such as: ABx, DCy, BBz, etc. Repeat letters are allowed in an ID.
(a) How many unique 3-character IDs are there?
(b) What is the smallest length of the keys list for which we can guarantee that no LinkedList in keys has length more than 2?
(c) Describe a hash function for this setting that guarantees that no key collides with more than one other key.