This lab is completely optional. You will not receive a grade on this assignment. However, you may want to do this as practice for the final exam.

For this lab, run update21 to get a clean copy of the Node and LinkedList classes. In your cs21/labs/11 directory should be the linkedlist.py file. This file will look a little bit different from the one we developed in our class. If you'd rather use your own version go ahead.

So far we have written the following methods:

• __init__()
• __str__()
• append(item) [We called this insertAtTail in class.]

Add these two methods to the LinkedList class:

1. prepend(item) -- add new node with item in it to head of the list
2. count(item) -- count and return number of nodes in the list that contain the given item

Here is some test code. Make sure you test your methods!

LL = LinkedList()
print len(LL), LL
for ch in "ABCD":
    LL.append(ch)
print len(LL), LL

LL.prepend(1)
LL.prepend(2)
LL.prepend(3)
LL.append(3)
print len(LL), LL

print "num of X in list: ", LL.count("X")
print "num of 3 in list: ", LL.count(3)

And here is the test code output:

0 HEAD--><--TAIL
4 HEAD-->(A)(B)(C)(D)<--TAIL
8 HEAD-->(3)(2)(1)(A)(B)(C)(D)(3)<--TAIL
num of X in list:  0
num of 3 in list:  2

Suppose the following 3 methods were added to the LinkedList class:

    def mystery1(self, item, n):
      if n == 0:
        self.prepend(item)
      elif n >= self.size:
        self.append(item)
      else:
        prev = self.head
        for i in range(n-1):
          prev = prev.getNext()
        newnode = Node(item)
        newnode.setNext(prev.getNext())
        prev.setNext(newnode)
        self.size += 1

    def mystery2(self):
        if self.size == 0:
            return None
        elif self.size == 1:
            data = self.head.getItem()
            self.head = None
            self.tail = None
            self.size = 0
            return data
        else:
            current = self.head
            for i in range(self.size - 2):
                current = current.getNext()
            current.setNext(None)
            data = self.tail.getItem()
            self.tail = current
            self.size -= 1
            return data

    def mystery3(self):
        if self.size == 0:
            return None
        elif self.size == 1:
            data = self.head.getItem()
            self.head = None
            self.tail = None
            self.size = 0
            return data
        else:
            data = self.head.getItem()
            current = self.head.getNext()
            self.head.setNext(None)
            self.head = current
            self.size -= 1
            return data

Draw what the linked list would look like (draw each node in the linked list, including it's data item and what the node is connected to) after each of the following:

LL = LinkedList()
for ch in "ABCD":
    LL.append(ch)

# draw what linked list looks like at this point

LL.mystery1("XX", 2)

# now here, after mystery1 is called

LL.mystery2()

# and here, after mystery2 is called

LL.mystery3()

# and finally, here...