WEEK13: linked lists
---------------------------------------------------------------
 M: nodes in linked list and Node class

LISTS...

 - how does python's list work? how is it implemented?

 - what things do we normally do with python lists?

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

 - can we write/create lists from scratch?
 - can we examine python lists vs our own version of a list to
   see which is better/more efficient?


COMPUTER MEMORY:

There are two main options for representing lists internally:
1. Store the list in consecutive locations in memory
2. Store each item of the list along with the address of where the
   next item can be found (known as a linked list)

Here's an example of consecutive memory locations:

>>> L = ["happy", "pretty", "pony"]
>>> print id(L)
139752655559280
>>> print id(L[0])
139752655654608
>>> print id(L[1])
139752655654656
>>> print id(L[2])
139752655654704
>>> help(id)
id(...)
    id(object) -> integer
    
    Return the identity of an object.  This is guaranteed to be unique among
    simultaneously existing objects.  (Hint: it's the object's memory address.)

 See how L[0], L[1], and L[2] are all 48 apart (608+48=656, 656+48=704)?

 Because everything is at known, easy-to-calculate memory addresses,
 that makes indexing fast and efficient:

   L[0] is at 608
   L[1] is at 608 + 1*48
   L[2] is at 608 + 2*48

   L[i] is at 608 + i*48

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

 It is also easy to add/append to the 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? 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
     (thanks, Jon!)

LINKED LISTS:

 - a linked list is a collection of objects/nodes, where each
   node "points" to the next one 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)

              -----    -----    -----    ------    ------
 head node--> | 3 |    | 5 |    | 0 |    | 91 |    | 12 | <--tail node
              -----    -----    -----    ------    ------
              |   |--> |   |--> |   |--> |    |--> |    | 
              -----    -----    -----    ------    ------

   the above linked list has 5 nodes, and each node stores
   one piece of data (a simple integer)

 - linked lists are often used to create other useful data structures,
   such as stacks and queues

 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 value and the address of the next value;

2) LinkedLlist, which will store the addresses of the head Node and
the tail Node, as well as the current size of the list.


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 on 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:
    """
    A class to represent one node in a singly-linked list.
    A node has two fields: data and next. Data stores the data
    value and next refers to the next node in the linked list.
    """

    def __init__(self, data):
        """ Create an new linked list node """
        self.data = data
        self.next = None

    def __str__(self):
        """return string representation of node"""
        return "(%s)" % (str(self.data))

    def setData(self, data):
        self.data = data
    def setNext(self, next):
       self.next = next

    def getData(self):
        return self.data
    def getNext(self):
        return self.next

#########################################################

if __name__ == "__main__":

  n1 = Node("jeff")
  n2 = Node("frances")
  n1.setNext(n2)
  print "n1: ", n1
  print "n2: ", n2