Lists, Data Structures
The key decision for this challenge is how to store the data. Conceptually, it makes sense to think of the array as linked list nodes, where the last node points to the first node and we have a pointer to head. However, this does not optimize the runtime for getting data by index.
Instead, we store the data in a Python list, and we also store which index represents the current “head” for the circular array. As the array rotates, the head index changes, but the list remains the same.
For example, when a list is created:
0 harry
1 hermione
2 ginny
3 ron
Here, self.head is 0. But when the array is rotated, the indexes for the circular array shift. So if we rotate the array by one, the effective indexes for the circular array are:
3 harry
0 hermione
1 ginny
2 ron
But the way this is stored is that self.head has changed to 1. Note that nothing actually changes in self.array. We are just keeping track that the current head of our circuar array is being stored at index 1 of the Python list in self.array.
Another challenge: where to insert new items after the array has rotated. Since the description specifies that new items are to have a position at the end of the current list rotation, the easiest thing to do is to put it at the current head’s position, and then bump the head index up by one.
class CircularArray(object):
"""An array that may be rotated, and items retrieved by index"""
def __init__(self):
"""Instantiate CircularArray."""
# START SOLUTION
# using a list to store the array instead of linked-list
# style nodes in order to optimize runtime for indexes
self.array = []
# track the current item at index 0 for the circular array
# by storing that item's actual index in self.array.
# Store None for an empty array.
self.head = None
# END SOLUTION
def add_item(self, item):
"""Add item to array, at the end of the current rotation."""
# START SOLUTION
if self.head is None:
# if there are currently no items in the array, set
# `self.array` to contain our new item, and set the head
# to point to that item (at index 0 in self.array).
self.head = 0
self.array = [item]
else:
# insert item. If we insert it at the self.head position,
# it will get inserted just before the head, which puts
# it at the end of the current rotation
self.array.insert(self.head, item)
# reassign head --- it has shifted ahead by one thanks
# to the insert for the new item.
self.head += 1
# END SOLUTION
def get_by_index(self, index):
"""Return the data at a particular index."""
# START SOLUTION
# index doesn't exist the list, return None
if index >= len(self.array):
return None
# this is the easy case -- the index doesn't go off the
# end of self.array when you start from head
if index + self.head < len(self.array):
return self.array[index + self.head]
# the fun case: we have to go round the twist (beyond end of
# self.array).
# In this case, add index to self.head and then shift left by
# the length of array to get back into self.array index space
adjusted_index = index + self.head - len(self.array)
return self.array[adjusted_index]
# END SOLUTION
def rotate(self, increment):
"""Rotate array, positive for right, negative for left.
If increment is greater than list length, keep going around.
"""
# START SOLUTION
# if the array doesn't have any elements, don't do anything
if not self.head:
return
# mod take care of cases where we've gone all the way around
adjusted_index = (increment + self.head) % len(self.array)
self.head = adjusted_index
# END SOLUTION
def print_array(self):
"""Print the circular array items in order, one per line"""
# START SOLUTION
for i in range(len(self.array)):
print(self.get_by_index(i))