- Due before 23:59 Wednesday, September 21
- Submit using the submit program
301 lab 04.
"Traversal" refers to visiting every piece of data in a data structure. Here's linked list traversal with iteration:
1 2 3 4 5
def traverse(self): curnode = self.head while curnode is not None: # DO SOMETHING HERE curnode = curnode.nextNode
and here it is with recursion:
1 2 3 4 5 6 7 8 9 10 11
def traverse(self) : self._traverse(self.head) # Helper method so no user has to know or care about nodes. def _traverse(self, curnode): if curnode is None: # base case: nothing left to do return else: # DO SOMETHING HERE self._traverse(curnode.nextNode)
Make sure you understand how this works. Soon, there will be data structures where the iterative version is pages long, and the recursive version is five lines. You want to know and understand how this works.
In class, we wrote two other methods, one of which counted the number of 5's in a linked list:
1 2 3 4 5 6 7 8 9 10 11 12 13
def count_fives(self): return self._count_fives(self.head) def _count_fives(self, curnode): if curnode is None: # base case, no more fives left return 0 elif curnode.data == 5: # found a 5 return 1 + self._count_fives(curnode.nextNode) else: # no 5 here, but we still count the rest return self._count_fives(curnode.nextNode)
The other method we wrote adds a 4 before the first 5 it comes to.
For example, if we have a linked list holding the integers 1,3,5, then after
add_before_five(4), we would have a linked list with
the integers 1,3,4,5.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
def add_before_five(self, item): self.head = self._add_before_five(item, self.head) def _add_before_five(self, item, curnode): if curnode is None: # guess there was no five to add before raise RuntimeError("No five to add before") elif curnode.data == 5: # insert a new node with this item, before curnode newnode = Node(item) newnode.nextNode = curnode return newnode else: # keep on looking for a five curnode.nextNode = self._add_before_five(item, curnode.nextNode) return curnode
Make some examples to try the above on, and understand why it works!
The work for lab is going to be very similar to Lab 2,
except that you cannot use any loops to implement these methods.
Pretty much all of your methods should be recursive except for the simple \(O(1)\)
methods such as
Start with this starter code
(download and save as
and fill in all of the methods. Specifically, you need to write the following
methods without using any loops:
__init__: No different from Lab 2.
add_front(item): No different from Lab 2.
print_forward(): Print the list elements in order, one per line
print_reverse(): Do the same, but the elements should print in reverse order.
contains(needle): Search for the needle within the list.
get(index): Return the list item at the given index.
insert(index, item): Insert the item at the given index, without removing anything.
add_ordered(item): Same as Lab 2, except now you have to get to use recursion.
remove(index): Remove the item at the given index from the list
size(): No explanation necessary I hope!
Test as you go.