Implement the dictionary operations INSERT, DELETE, and SEARCH using singly linked, circular lists. What are the running times of your procedures?
Unfortunately, this exercise does not specify that the singly linked, circular lists use a sentinel which complicates matters a bit.
SINGLY-LINKED-CIRCULAR-LIST-INSERT(L, x)
1 x.next = L.head
2 L.head = x
Because our list is singly linked, we don’t need to worry about previous values at all. Furthermore, because our list is circular we don’t even need to care about whether L.head is \(NIL\) or not resulting in this very simple operation that runs at constant time.
SINGLY-LINKED-CIRCULAR-LIST-DELETE(L, x)
In the event that the list head is the value we’re looking for we bypass the while loop completely and simply change the next value on the head so it points to where the deleted node used to point to. In all other cases, we proceed through the list until we find the node which points to our desired node and perform that same next-swap operation, erroring if instead we see that the next node is the head node in which case we’ve reached the end of the list and ought to throw an error indicating the desired node cannot be found. This operation will run at linear time.
1 prev = L.head
2 while prev.next != x:
3 if prev.next == L.head:
4 error "element does not exist"
5 prev = prev.next
6 prev.next = x.next
SINGLY-LINKED-CIRCULAR-LIST-SEARCH(L, k)
Without a sentinel object this search becomes a bit more complex. We first control for an empty list with lines 1 and 2. Then in the main loop we look for an object with a value that matches \(k\) until we reach the head node again at which point we have traversed the entire list and return \(NIL\) since no object holds the sought-after value \(k\). This operation runs at linear time because we may need to check every node in the list.
1 if L.head == NIL:
2 return NIL
3 x = L.head
4 while True:
5 if x.key == k:
6 return x
7 x = x.next
8 if x == L.head:
9 return NIL