Week 13, Wednesday: Linked Lists

Quiz 6 on Friday
Lab 10 due this Saturday

the `LinkedList` class

Last time we wrote a Node class to be used to create our linked lists. A Node is just a "container" to hold two things: the item or data we want stored in the list, plus a next "pointer" to point to the next node in the list. Here is an example of how we could manually create nodes and link them together:

>>> from node import *
>>> n1 = Node("jeff")
>>> n2 = Node("zach")
>>> n3 = Node("lauri")
>>> 
>>> print(n1)
(jeff)--|
>>> 
>>> n1.setNext(n2)
>>> n2.setNext(n3)
>>> 
>>> print(n1)
(jeff)-->
>>> print(n2)
(zach)-->
>>> print(n3)
(lauri)--|

Instead of doing this manually, we could create a LinkedList class to allow us to create linked lists just like python lists. Here is what I would like to be able to do:

>>> from linkedlist import *
>>> LL = LinkedList()
>>> LL.append("jeff")
>>> LL.append("zach")
>>> LL.append("lauri")
>>> print(LL)
head-->(jeff)(zach)(lauri)<--tail

Each linked list should have three instance variables: self.head, self.tail, and self.size. All methods we write should make sure all three are updated accordingly. For example, when appending to the list, the self.tail pointer should be adjusted, as well as the size of the list. And if it is the first node being added/appended to the list, then the self.head pointer will also need to be set (i.e., if there is just one node in the list, both the head and the tail should point to that one node).

the constructor

For the constructor, we want to build an empty linked list object, so self.head and self.tail don't point to anything, and the size is zero. We use python's None type when things don't point to anything:

def __init__(self):
  """construct an empty linked list"""

  self.head = None
  self.tail = None
  self.size = 0

the `append` method

To append a new node, we need to create the node with the given item stored in the node, and then add it to the end of the list. That means connecting the current tail of the list to the newly-created node, then resetting the tail to be the newly-created node. Something like this:

n = Node(item)
self.tail.setNext(n)    # connect to end
self.tail = n           # reset tail pointer
self.size += 1

However, this only works if there are already nodes in the list. If this is the first node in the list, we have to account for that (set the head to point to this node, and don't connect the current tail). Here is the final version of our append() method:

def append(self, item):
  """add new node, containing item, to end of the list"""

  n = Node(item)
  if self.size == 0:
    self.head = n
  else:
    self.tail.setNext(n)
  self.tail = n
  self.size += 1

the `prepend` method

Can you create a similar method called prepend, to add nodes to the beginning of the list?

the `str` method

It would be nice to be able to print the list, to make sure it is set up correctly. Something like the above example would be useful:

head-->(jeff)(zach)(lauri)<--tail

However, to get each item stored in the list, we need to access each node in the list. This is typically done with a loop to visit each node in the list (i.e., list traversal). Here is how you could manually set a pointer to the first node in the list, get the item stored there, and then move the pointer over to the next node in the list:

s = "head-->"
curr = self.head
s += "(%s)" % str(curr.getItem())
curr = curr.getNext()

Note the curr = curr.getNext()...this moves the pointer from one node to the next. Putting this in a loop, we can visit each node in the list and create/accumulate a string-representation of the list:

def __str__(self):
  """return string representation of linked list"""
  s = "head-->"
  curr = self.head
  for i in range(self.size):
    s += "(%s)" % str(curr.getItem())
    curr = curr.getNext()
  s+="<--tail"
  return s

Note: if the list is empty, the for loop never executes, so all we get is "head--><--tail", which shows an empty list.

If you want you can change the str method to use square brackets and commas between items, so the linked list prints exactly like the python list.

the `len()` method

Adding a getter for self.size could be useful. Calling it __len__() allows you to use len(LL), just like we've done with python lists.

testing

Once you have the above methods written, add some test code to make sure everything works. Try to test all possible cases. Thoroughly testing now will help eliminate bugs that can cause lots of headaches later!!

Use the assert statement to add as many tests as you can think of.

# test init,str,append,len
LL = LinkedList()
assert len(LL) == 0
assert str(LL) == "head--><--tail"
LL.append("A")
LL.append("B")
LL.append("C")
assert len(LL) == 3
assert str(LL) == "head-->(A)(B)(C)<--tail"

Week 13, Wednesday: Linked Lists

the LinkedList class

the constructor

the append method

the prepend method