As stated in class, I'm linking a recorded lecture from a 
previous offering of CS 9. Please watch the before our next 
lecture on Tuesday 8/29.

You can ignore any announcements / reminders in the video. 
Reminders relevant for this course are:
* h04 due Tuesday 8/29 by 9:30AM
* lab04 due Tuesday 8/29 by 11:59PM

# LinkedList.py
class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

	def getData(self):
		return self.data

	def getNext(self):
		return self.next

	def setData(self, newData):
		self.data = newData

	def setNext(self, newNext):
		self.next = newNext

class LinkedList:
	def __init__(self):
		self.head = None

	def isEmpty(self):
		return self.head == None

	def addToFront(self, item):
		temp = Node(item)
		temp.setNext(self.head)
		self.head = temp

	def length(self):
		temp = self.head
		count = 0
		while temp != None:
			count = count + 1
			temp = temp.getNext()
		return count

	def search(self, item):
		temp = self.head
		found = False
		while temp != None and not found:
			if temp.getData() == item:
				found = True
			else:
				temp = temp.getNext()
		return found

	def remove(self, item):
		current = self.head
		
		if current == None: # empty list, nothing to do
			return

		previous = None
		found = False
		while not found: #Find the element
			if current == None:
				return
			if current.getData() == item:
				found = True
			else:
				previous = current
				current = current.getNext()

		# Case 1: remove 1st element
		if found == True and previous == None:
			self.head = current.getNext()
		
		# Case 2: remove not 1st element
		if found == True and previous != None:
			previous.setNext(current.getNext())

#LinkedListTest.py
from LinkedList import LinkedList, Node

def test_NodeCreation():
	n = Node(20)
	assert n.getData() == 20
	assert n.getNext() == None

def test_NodeSetData():
	n = Node(20)
	n.setData(200)
	assert n.getData() == 200

def test_NodeSetNext():
	n = Node(20)
	n2 = Node(10)
	n.setNext(n2)
	assert n.getNext() == n2

def test_createList():
	ll = LinkedList()
	assert ll.isEmpty() == True

def test_addingNodesToList():
	ll = LinkedList()
	assert ll.isEmpty() == True
	ll.addToFront(10)
	ll.addToFront("Gaucho")
	ll.addToFront(False)
	assert ll.isEmpty() == False
	assert ll.length() == 3
	assert ll.search(10) == True
	assert ll.search("Gaucho") == True
	assert ll.search(False) == True
	assert ll.search("CS9") == False

def test_removeNodesFromList():
	ll = LinkedList()
	ll.addToFront(10)
	ll.addToFront("Gaucho")
	ll.addToFront(False)
	ll.addToFront("CS9")
	assert ll.length() == 4
	assert ll.search(10) == True
	ll.remove(10)
	assert ll.search(10) == False
	assert ll.search("Gaucho") == True
	assert ll.search(False) == True
	assert ll.search("CS9") == True
	assert ll.length() == 3
	ll.remove(False)
	assert ll.search(False) == False
	assert ll.search("Gaucho") == True
	assert ll.search("CS9") == True
	assert ll.length() == 2
	assert ll.isEmpty() == False
	ll.remove("Gaucho")
	ll.remove("CS9")
	ll.isEmpty() == True
	ll.length() == 0