1 # ListModule.py  2 # Classes List and Node definitions.  3   4 class Node:  5    """Single node in a data structure"""  6   7    def __init__( self, data ):  8       """Node constructor"""  9        10       self._data =http://www.mamicode.com/ data 11       self._nextNode = None 12      13    def __str__( self ): 14       """Node data representation""" 15  16       return str( self._data )       17  18 class List: 19    """Linked list""" 20  21    def __init__( self ): 22       """List constructor""" 23  24       self._firstNode = None 25       self._lastNode = None 26  27    def __str__( self ): 28       """List string representation""" 29  30       if self.isEmpty(): 31          return "empty" 32  33       currentNode = self._firstNode 34       output = [] 35  36       while currentNode is not None: 37          output.append( str( currentNode._data ) ) 38          currentNode = currentNode._nextNode 39  40       return " ".join( output )       41  42    def insertAtFront( self, value ): 43       """Insert node at front of list""" 44  45       newNode = Node( value ) 46  47       if self.isEmpty():  # List is empty 48          self._firstNode = self._lastNode = newNode 49       else:   # List is not empty 50          newNode._nextNode = self._firstNode 51          self._firstNode = newNode 52          53    def insertAtBack( self, value ): 54       """Insert node at back of list""" 55  56       newNode = Node( value ) 57  58       if self.isEmpty():  # List is empty 59          self._firstNode = self._lastNode = newNode 60       else:  # List is not empty 61          self._lastNode._nextNode =  newNode 62          self._lastNode = newNode 63  64    def removeFromFront( self ): 65       """Delete node from front of list""" 66  67       if self.isEmpty():  # raise exception on empty list 68          raise IndexError, "remove from empty list" 69  70       tempNode = self._firstNode 71  72       if self._firstNode is self._lastNode:  # one node in list 73          self._firstNode = self._lastNode = None 74       else: 75          self._firstNode = self._firstNode._nextNode 76  77       return tempNode 78  79    def removeFromBack( self ): 80       """Delete node from back of list""" 81  82       if self.isEmpty():  # raise exception on empty list 83          raise IndexError, "remove from empty list" 84       85       tempNode = self._lastNode 86  87       if self._firstNode is self._lastNode:  # one node in list 88          self._firstNode = self._lastNode = None 89       else: 90          currentNode = self._firstNode 91  92          # locate second-to-last node 93          while currentNode._nextNode is not self._lastNode: 94                currentNode = currentNode._nextNode 95                 96          currentNode._nextNode = None 97          self._lastNode = currentNode 98  99       return tempNode100     101    def isEmpty( self ):102       """Returns true if List is empty"""103 104       return self._firstNode is None

 1 # -*- coding: utf-8 -*- 2 """ 3 Created on Thu Aug 07 23:20:31 2014 4  5 @author: Administrator 6 """ 7  8 # Driver to test class List 9 10 from ListModule import List11 12 # instructions for user13 instructions = """Enter one of the following:14     1 to insert at beginning of list15     2 to insert at end of list16     3 to delete from beginning of list17     4 to delete from end of list18     5 to end list processing\n"""19 20 # 创建空的List对象    21 listObj = List()22 23 print instructions24 25 # obtain user choice until user chooses to quit ( choice 5 )26 while 1:27     choice = raw_input("Enter value:")28     29     # insert at front30     if choice == "1":31         listObj.insertAtFront(raw_input("Enter value:"))32         print "The list is:",listObj33     # insert at end34     elif choice == "2":35         listObj.insertAtBack(raw_input("Enter value:"))36         print "The list is:", listObj37     # delete from front38     elif choice == "3":39         try:40             value =http://www.mamicode.com/ listObj.removeFromFront()41         except IndexError, message:42             print "Fail to remove: ",message43         else:44             print value, "removed from list"45             print "The list is:",listObj46     # delete from end47     elif choice == "4":48         try:49             value =http://www.mamicode.com/ listObj.removeFromBack()50         except IndexError, message:51             print "Fail to remove:",message52         else:53             print value,"removed from list"54             print "The list is:",listObj55     # exit56     elif choice == "5":57         break   # terminate while loop58     59     # invalid choice60     else:61         print "Invalid choice:", choice62         print instructions63         64 print "End list test\n"