```
---------------------------------------------------------------

- used as building blocks for many advanced data structures (like
queues, stacks, and skip lists)

- can be used like Python lists -- many languages (like C) don't
have a data structure like a Python list

- we'll use linked lists as another example of a class, and write
our own

REVIEW of LINKED LISTS:

- a linked list is a collection of "nodes", where each
node "points" to the next one in the list

- each node stores two things: data and where (if anywhere) the next node is
(see Node __init__ method below)

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

NODE Class from last time:

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):
"""show if next is None or points to something"""
me =  "(%s)" % (self.data)
if (self.next != None):
me += "-->"
else :
me += "--|"
return me

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")      # store a string in each node
n2 = Node("frances")
n1.setNext(n2)
print "n1: ", n1
print "n2: ", n2

- each linked list should have what kind of data and methods???

data: head, tail, size??
methods: __init__, __str__, add (at head? at tail? in sorted order?),
remove (at head? tail?), findNode, len?

- for the constructor, let's make the list empty, with both
the head and the tail set to None (and a size of zero)

- let's start with adding a new node at the tail of the list
(like the python list append method). here's one possible algorithm:

create a new node with the given data
set the new node's next field to point to None
set the current tail node's next to point to the new node
set the tail of the linked list to point to the new node
if this is the only node in the list, set the head to point to it, too
add one to the size of the linked list

APPEND method:

def append(self, data):
"""append new node to linked list"""

newnode = Node(data)

if self.size == 0:
self.head = newnode  # list is empty case
self.tail = newnode
else:
self.tail.setNext(newnode)
self.tail = newnode

self.size += 1

__str__ method:

- need to traverse the list, visiting every node, adding each
node's data item to the string we will return

s = "head -- "
while curr != None:
s = s + str(curr.getData()) + " -- "
curr = curr.getNext()
s = s + "tail"