CS21: Lab 11

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.

Add methods to the LinkedList class

For this lab, run update21 to get a clean copy of the code we wrote in class for the Node and LinkedList classes. In your cs21/labs/11 directory should be the node.py and linkedlist.py files. Read through them and make sure you understand how they work. You can also start with your own files from class, if you want.

So far we have written the following methods:

__init__()
__str__()
__len__()
append(item)

Add these two methods to the LinkedList class:

prepend(item) -- add new node with item in it to head of the list
count(item) -- count and return number of nodes with item stored in node

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

Draw the Linked-Lists

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...

CS21 Lab 11: LinkedList practice