WEEK13: linked lists --------------------------------------------------------------- M: 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 - linked lists typically have a head node and sometimes a tail node: ----- ----- ----- ------ ------ head --> | 3 |--> | 5 |--> | 0 |--> | 91 |--> | 12 | <--tail ----- ----- ----- ------ ------ 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(20,None) print "n1: ", n1 n2 = Node(721,None) n2.setNext(n1) print "n2: ", n2, n2.getNext() 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 head of the list. here's one possible algorithm: create a new node with the given data set the new node's next field to point to the current head set the head of the linked list to point to the new node if this is the only node in the list, set the tail to point to it, too add one to the size of the linked list YOUR TURN: - write a LinkedList class that works with the following test code: if __name__ == "__main__": LL = LinkedList() for i in [4,10,"cat",905, 3.14159]: LL.insertAtHead(i) print LL - if you have time, see if you can write insertAtTail