Python Homework Three | Python Fiddle

# HW3.py
# Homework 3
#  
# UT EID: kl23883, UTCS username: kevinlin 
# CS313e, Fall 2013, Dr. P. Cannata 
# Department of Computer Science, The University of Texas at Austin

# -*- coding: utf-8 -*-
class LinkedList():
    def __init__(self):
        self.__head = None
        self.__tail = None
        self.__size = 0
        
    # Return the head element in the list
    def getFirst(self):
        if self.__size == 0:
            return None
        else:
            return self.__head.element

# Return the last element in the list
    def getLast(self):
        if self.__size == 0:
            return None
        else:
            return self.__tail.element

# Add an element to the beginning of the list
    def addFirst(self, e):
       # link the new node with the head"
       newNode = Node(e)	
       newNode.next = self.__head
       self.__head = newNode
       self.__size += 1	
       if self.__tail == None: # the new node is the only node in list
          self.__tail = self.__head
          
    # Add an element to the end of the list
    def addLast(self, e):
       newNode = Node(e) # Create a new node for e
       if self.__tail == None:
          self.__head = self.__tail = newNode # The only node in list
       else:
          self.__tail.next = newNode # Link the new with the last node
          self.__tail = self.__tail.next # tail now points to the last node
       self.__size += 1 # Increase size

# Same as addLast
    def add(self, e):
        self.addLast(e)

# Insert a new element at the specified index in this list
    # The index of the head element is 0
    def insert(self, index, e):
       if index == 0:
          self.addFirst(e) # Insert first
       elif index >= self.__size:
          self.addLast(e) # Insert last
       else: # Insert in the middle
          current = self.__head
          for i in range(1, index):
             current = current.next
             temp = current.next
             current.next = Node(e)
             (current.next).next = temp
             self.__size += 1
        
    #  return the object that is contained in the removed node.
    def removeFirst(self):
       if self.__size == 0:
          return None # Nothing to delete
       else:
          temp = self.__head # Keep the first node temporarily
          self.__head = self.__head.next # Move head to point the next
          self.__size -= 1 # Reduce size by 1
          if self.__head == None:
             self.__tail = None # List becomes empty
          return temp.element # Return the deleted element

# Remove the last node and
    # return the object that is contained in the removed node
    def removeLast(self):
       if self.__size == 0:
          return None # Nothing to remove
       elif self.__size == 1: # Only one element in the list
          temp = self.__head
          self.__head = self.__tail = None # list becomes empty
          self.__size = 0
          return temp.element
       else:
          current = self.__head
          for i in range(self.__size - 2):
             current = current.next
          temp = self.__tail
          self.__tail = current
          self.__tail.next = None
          self.__size -= 1
          return temp.element

# Remove the element at the specified position in this list.
    #  Return the element that was removed from the list.
    def removeAt(self, index):
       if index < 0 or index >= self.__size:
          return None # Out of range
       elif index == 0:
          return self.removeFirst() # Remove first
       elif index == self.__size - 1:
          return self.removeLast() # Remove last
       else:
          previous = self.__head
          for i in range(1, index):
             previous = previous.next
          current = previous.next
          previous.next = current.next
          self.__size -= 1
          return current.element

# Return true if the list is empty
    def isEmpty(self):
        return self.  size == 0

# Return the size of the list
    def getSize(self):
        return self.  size

def __str__(self):
        result = "["
        current = self.__head
        for i in range(self.__size):
            result += str(current.element)
            current = current.next
            if current != None:
                result += ", " # Separate two elements with a comma
            else:
                result += "]" # Insert the closing ] in the string

return result

# Clear the list */
    def clear(self):
        self.__head = self.__tail = None

# Return true if this list contains the element o
    def contains(self, e):
        place = self.__head
        for i in range(self.__size):
            if place.element == e:
                return True
            elif place.next == None:
                return False
            else:
                place = place.next

# Remove the element and return true if the element is in the list
    def remove(self, e):
        print("Implementation left as an exercise")
        return True

# Return the element from this list at the specified index
    def get(self, index):
        if index < 0 or index >= self.__size:
        	return None
        else:
            place = self.__head
            for i in range(index):
                place = place.next
            return place.element
        
    # Return -1 if no match.
    def indexOf(self, e):
        print("Implementation left as an exercise")
        return 0

# Return the index of the last matching element in this list
    #  Return -1 if no match.
    def lastIndexOf(self, e):
        print("Implementation left as an exercise")
        return 0

# Replace the element at the specified position in this list
    #  with the specified element. */
    def set(self, index, e):
        print("Implementation left as an exercise")
        return None

# Return an iterator for a linked list
    def __iter__(self): # To be discussed in Section 18.3
        return LinkedListIterator(self.__head)
    
    def car(self):
        return self.getFirst()
    
    def cdr(self):
        l = self
        l.removeFirst()
        return l
    
    def cons(self):
        pass

# The Node class
class Node:
    def __init__(self, element):
        self.element = element
        self.next = None

class LinkedListIterator: # To be discussed in Section 18.3
    def __init__(self, head):
        self.current = head

def next(self):
        if self.current == None:
            raise StopIteration
        else:
            element = self.current.element
            self.current = self.current.next
            return element
            
ll1 = LinkedList()
ll1.addFirst("A")
print ll1, ll1.getFirst(), ll1.getLast()
ll1.addFirst("B")
print ll1, ll1.getFirst(), ll1.getLast()
ll1.addLast("D")
print ll1, ll1.getFirst(), ll1.getLast()
227
ll1.insert(2, "E")
228
print ll1, ll1.getFirst(), ll1.getLast()
229
 
230
print ll1.contains("AB")
231
 
232
for i in ll1:
233
   print i,
234
 
235
list1 = LinkedList()
236
for i in {"Tom", "George", "Peter", "Jean", "Jane"} :
237
   list1.addFirst(i)
238
print
239
print list1
 
Run
  
Reset
  
Share
  
Import
  
Dashboard
[A] A A
[B, A] B A
[B, A, D] B D
[B, A, E, D] B D
False
B A E D
[Tom, George, Peter, Jean, Jane]
Examples
Chaining comparison operators
Decorators
Creating generators objects
Enumerate
Function closure
Lex tokenizer
Step argument in slice operators
For Else
Verbose regular expressions
In-place value swapping
Function argument unpacking
Packages
Hotkeys
Featured
Pages

ll1.insert(2, "E")
print ll1, ll1.getFirst(), ll1.getLast()

print ll1.contains("AB")

for i in ll1:
   print i,

list1 = LinkedList()
for i in {"Tom", "George", "Peter", "Jean", "Jane"} :
   list1.addFirst(i)
print
print list1

Python Fiddle

Python Cloud IDE