WEEK13: linked lists --------------------------------------------------------------- W: LinkedList class LINKED LISTS: - 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, next): """ Create an new linked list node """ self.data = data self.next = next 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",None) # store a string in each node n2 = Node("frances",None) n1.setNext(n2) print "n1: ", n1 print "n2: ", n2 LINKED LIST CLASS: - 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 -- " curr = self.head while curr != None: s = s + str(curr.getData()) + " -- " curr = curr.getNext() s = s + "tail" YOUR TURN: - write a LinkedList class that works with the following test code: LL = LinkedList() for i in ["jeff", "frances", "molly", "justin"]: LL.append(i) print LL