Problem Solving with Algorithms and Data Structures using Python
Section 3.6 (Big O of list operations): https://runestone.academy/ns/books/published/pythonds/AlgorithmAnalysis/Lists.html
Section 4.19-4.23: https://runestone.academy/ns/books/published/pythonds/BasicDS/toctree.html
class Node:
def __init__(self,initdata):
self.data = initdata
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
We previously looked at the UnorderedList ADT:
List()creates a new list that is empty. It needs no parameters and returns an empty list.add(item)adds a new item to the list. It needs the item and returns nothing. Assume the item is not already in the list.remove(item)removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.search(item)searches for the item in the list. It needs the item and returns a boolean value.isEmpty()tests to see whether the list is empty. It needs no parameters and returns a boolean value.size()returns the number of items in the list. It needs no parameters and returns an integer.append(item)adds a new item to the end of the list making it the last item in the collection. It needs the item and returns nothing. Assume the item is not already in the list.index(item)returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.insert(pos,item)adds a new item to the list at position pos. It needs the item and returns nothing. Assume the item is not already in the list and there are enough existing items to have position pos.pop()removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.pop(pos)removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.
We also talked about how the built-in Python list type is a pretty good match for this.
Now, we will implement the ADT as a linked list - following Section 4.21 in the book
The code we've written so far for the linked-list-based UnorderedList looks like this:
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
#this method is really a prepend - it puts the new node at the beginning
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
#testing it out
my_list = UnorderedList()
print(my_list.isEmpty())
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
print(my_list.isEmpty())
True False
Some of the operations you need to perform with a linked list require you to traverse (i.e., loop over) all/many items in the list.
For example, if I wanted to display each item in a list, I could do it with a loop as in the display() method below:
we're going to add on to the book example
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
#this method is really a prepend - it puts the new node at the beginning
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def display(self):
current = self.head #start with the Node at the head
while current: #this will keep going until current equals None
print(current.getData()) #display the current Node's data
current = current.getNext() #move on to the next Node in the list
my_list = UnorderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)
my_list.display()
54 26 93 17 77 31
__repr__ instead¶class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
#this method is really a prepend - it puts the new node at the beginning
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def __repr__(self):
list_representation = ""
current = self.head #start with the Node at the head
while current: #this will keep going until current equals None
list_representation += str(current.getData())+" -> "
current = current.getNext() #move on to the next Node in the list
list_representation += "None" #the last one in the list points to None
return list_representation
my_list = UnorderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)
print(my_list)
54 -> 26 -> 93 -> 17 -> 77 -> 31 -> None
If you want to get an item by its index, you need to traverse the list and count until you find it.
Note: This is not one of the methods that is listed in the ADT, but I think it is ok to allow it since it's something that you can do with a built-in Python list.
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
#this method is really a prepend - it puts the new node at the beginning
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def __repr__(self):
list_representation = ""
current = self.head #start with the Node at the head
while current: #this will keep going until current equals None
list_representation += str(current.getData())+" -> "
current = current.getNext() #move on to the next Node in the list
list_representation += "None" #the last one in the list points to None
return list_representation
def get(self,index):
if index < 0:
raise Exception("list index "+str(index)+" is out of range")
current = self.head
item_counter = 0
while current and item_counter < index:
current = current.getNext()
item_counter += 1
if current == None:
raise Exception("list index "+str(index)+" is out of range")
return current.getData()
my_list = UnorderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)
print(my_list)
print(my_list.get(3))
print(my_list.get(5))
54 -> 26 -> 93 -> 17 -> 77 -> 31 -> None 17 31
__getitem__ magic method¶And we can instead implement __getitem__ in place of our get method, which will allow us to use [ ] notation instead
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
#this method is really a prepend - it puts the new node at the beginning
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def __repr__(self):
list_representation = ""
current = self.head #start with the Node at the head
while current: #this will keep going until current equals None
list_representation += str(current.getData())+" -> "
current = current.getNext() #move on to the next Node in the list
list_representation += "None" #the last one in the list points to None
return list_representation
def __getitem__(self,index):
if index < 0:
raise Exception("list index "+str(index)+" is out of range")
current = self.head
item_counter = 0
while current and item_counter < index:
current = current.getNext()
item_counter += 1
if current == None:
raise Exception("list index "+str(index)+" is out of range")
return current.getData()
my_list = UnorderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)
print(my_list)
print(my_list[3])
print(my_list[5])
54 -> 26 -> 93 -> 17 -> 77 -> 31 -> None 17 31
Note that the ADT description includes a search operation. Add this to your UnorderedList class.
Hint: You will need to do a traversal like with get, but you're going to be looking for a value in the list that matches your item.
Hint 2: You can find a solution to this exercise in the book: https://runestone.academy/ns/books/published/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html
It should work with code like this:
my_list = UnorderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)
print(my_list)
print( my_list.search(17) ) #should print True
print( my_list.search(34) ) #should print False
Create a method called __contains__ that otherwise is the same as your search method.
This allow you to write code as below. Discuss in your group what the difference is between these two approaches.
my_list = UnorderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)
print(my_list)
print( 17 in my_list ) #should print True
print( 34 in my_list ) #should print False
What is the Big O of get/__getitem__ and search/__contains__?
What things from the ADT do we still have left to implement? Write down a to-do list.
Take a look at the implementation of the size method in the book (https://runestone.academy/ns/books/published/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html ). What is the Big O of that approach?
I claim that it is possible to do size in $O(1)$ time. Discuss ideas for how you might pull that off.
Come up with a strategy for how you would implement append - just describe the approach, you don't actually have to code it up. What would the Big O of that approach be? Can you think of any ways to improve it?
How do the complexities of the methods we've discussed so far compare with the complexities of Python lists (https://runestone.academy/ns/books/published/pythonds/AlgorithmAnalysis/Lists.html )? Which things are the same? Which things are Python lists better at? Which things are linked lists better at?
pop method¶Now we're going to do something that requires us to keep track of a trailing reference in our traversal - it keeps track of the item before the current one.
We'll then be able to use the trailing reference to "jump" over the one we're removing.
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
#this method is really a prepend - it puts the new node at the beginning
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def __repr__(self):
list_representation = ""
current = self.head #start with the Node at the head
while current: #this will keep going until current equals None
list_representation += str(current.getData())+" -> "
current = current.getNext() #move on to the next Node in the list
list_representation += "None" #the last one in the list points to None
return list_representation
def __getitem__(self,index):
if index < 0:
raise Exception("list index "+str(index)+" is out of range")
current = self.head
item_counter = 0
while current and item_counter < index:
current = current.getNext()
item_counter += 1
if current == None:
raise Exception("list index "+str(index)+" is out of range")
return current.getData()
def pop(self,index):
if index < 0:
raise Exception("list index "+str(index)+" out of range")
current = self.head
previous = None
item_counter = 0
while current and item_counter < index:
previous = current
current = current.getNext()
item_counter += 1
if current == None:
raise Exception("list index "+str(index)+" out of range")
#this if-else statement corrects an error in the video
#I didn't originally check for the edge case of popping
#the first item
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
return current.getData()
my_list = UnorderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)
print(my_list)
print(my_list.pop(3))
print(my_list)
#let's test emptying out the list
while not my_list.isEmpty():
print(my_list.pop(0))
print(my_list)
54 -> 26 -> 93 -> 17 -> 77 -> 31 -> None 17 54 -> 26 -> 93 -> 77 -> 31 -> None 54 26 -> 93 -> 77 -> 31 -> None 26 93 -> 77 -> 31 -> None 93 77 -> 31 -> None 77 31 -> None 31 None
Implement a remove method for UnorderedList which allows you to remove items by their value (rather than their index, which is what pop() does.
Hint: You will need a trailing reference, just like with pop, but instead of counting to find the Node to remove, you will look at the data.
Hint 2: You can find a solution to this exercise in the book: https://runestone.academy/ns/books/published/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html
It should work with code like this:
my_list = UnorderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)
print(my_list)
my_list.remove(17)
print(my_list)