Week 14, Monday: Linked Lists

• review Quiz 6
• Lab 12 is optional

Linked Lists vs Python lists

How do python lists work? We have used them a lot this semester. Is there another way to implement lists? And if so, what are the pros and cons of each way?

What things do we normally do with python lists?

  L = []                 # construct
  L.append("cat")        # add to
  print L, len(L), L[1]  # print, length, indexing
  L.pop(0)               # remove from

Can we write/create lists from scratch (without using python lists)?

Computer Memory

There are two main options for representing lists internally:

1. Store the list items in consecutive locations in memory (python list)
2. Store "nodes" anywhere in memory. A Node consists of the list item, plus the address (or something like the address) of where the next node can be found. This is known as a linked list

Here is a klunky/simplified picture of how each option might look:

For the python list, because everything is at known, easy-to-calculate memory addresses, that makes indexing fast and efficient:

L[0] is at 2000
L[1] is at 2000 + 1
L[2] is at 2000 + 2
... 
L[i] is at 2000 + i

So, to get any value from the list, all we have to do is one quick calculation (base memory address + i). This is a constant time operation (i.e., it doesn't depend on the size of the list).

It is also easy to append to the python list, by using the length of the list to locate the next location to store a new item.

Some disadvantages of using consecutive memory:

• what happens when you want to insert a new item in the middle of a list, or at the beginning of the list? all following items need to be shifted down one spot
• what happens when the computer runs out of large chunks of consecutive memory? think of a crowded movie theater, and how you can't always sit with all of your friends

Linked Lists:

A linked list is a collection of objects/nodes, where each node contains both the item stored in the list, as well as a "pointer" to the next node in the list.

Linked lists typically have three instance variables: a head pointer (self.head), a tail pointer (self.tail), and the number of nodes in the list (self.size)

In the above picture, the linked list has 5 nodes, and each node stores a simple string, as well as a pointer to the next node in the list. In class I often draw linked lists and nodes as follows:

              ------    ------   ------   ------   ------
self.head --> |rich|    |lisa|   |andy|   |zach|   |tia |<--self.tail
              ------    ------   ------   ------   ------
              |    |--> |    |-->|    |-->|    |-->|    |-->None
              ------    ------   ------   ------   ------

                             self.size = 5

Linked lists are often used to create other useful data structures, such as stacks and queues. They are also a good introduction to more advanced data structures, such as binary trees.

One big advantage of the linked list is not needing large chunks of consecutive memory. Each node in the list is just put in memory wherever there is space, and all nodes are "linked" together into one "list".

Also, adding an item into the middle of the list does not require shifting all other elements down one slot. Simply reset the next "pointers" to include the new node.

Implementing A Linked List

We will implement a linked list using two classes:

1. Node, which will store a data value (the list item) and a "pointer" to the next node in the list
2. LinkedLlist, which will store pointers to the head Node and the tail Node, as well as the current size of the list.

the Node class:

Let's write a Node class, where each node has two instance variables: one to hold the node data (call it "data"), and one to hold a pointer to another node (call it "next"). Later we will use these node objects to build a linked-list!

Add two mutators and two accessors for the data and next variables, then test it out.

class Node(object):

  def __init__(self, item):
    """
    construct new node, with given item.
    next initially set to None.
    """
    self.item = item
    self.next = None

  def __str__(self):
    """return a string representation of the node"""
    s = "("+str(self.item)+")"
    if self.next == None:
      s += "--|"
    else:
      s += "-->"
    return s

  def getItem(self): return self.item
  def getNext(self): return self.next

  def setItem(self, i):
    """set node item to i"""
    self.item = i

  def setNext(self, n):
    """set node next to n"""
    self.next = n


if __name__ == "__main__":

  n1 = Node("jeff")
  n2 = Node("zach")
  n3 = Node("lauri")
  n4 = Node("rich")

  n1.setNext(n2)
  print(n1)
  n2.setNext(n3)
  print(n2)
  n3.setNext(n4)