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.10-4.23: https://runestone.academy/ns/books/published/pythonds/BasicDS/toctree.html
pop method in our Linked List¶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()
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)
Download UnorderedListLinkedList.py and UnorderedListArray.py
Both have many of the methods that are part of the UnorderedList ADT, but one uses a linked list, and the other uses an array (i.e., a Python list).
In order to compare these approaches, we will need to understand the computational complexity of each of their methods. Fill out the table below (copy and paste it into a text file or spreadsheet). This will be a good thing to have handy in the future!
Recall that the complexity of all of the list operations are given here: https://runestone.academy/ns/books/published/pythonds/AlgorithmAnalysis/Lists.html
| Method | Linked List | Array |
|---|---|---|
get/__getitem__ |
||
add |
||
search/__contains__ |
$O(n)$ | $O(n)$ |
pop(n) |
||
pop first item |
||
pop last item |
||
remove |
||
size |
||
isEmpty |
The UnorderedList ADT is also supposed to have an append method (see https://runestone.academy/ns/books/published/pythonds/BasicDS/TheUnorderedListAbstractDataType.html )
We could make one easily in the array version by using the Python list's append method. What would the complexity of this be?
It is possible to do this in the linked list by traversing the list all the way to the end of the list and then putting the new item there - this would take $O(n)$.
It might be possible to do it in $O(1)$ time by adding a self.tail attribute that keeps track of the last item. Can you think of any problems that would arise from a strategy like this?
class UnorderedList:
def __init__(self):
self.head = None
self.tail = None
def append(self,item):
if self.isEmpty():
temp = Node(item)
temp.setNext(self.head)
self.head = temp
self.tail = temp
else:
temp = Node(item)
self.tail.setNext(temp)
self.tail = temp
Which other methods would need to change to make sure that self.tail always continues referring to the last item in the list?
Using self.tail, can we now implement a version of pop that would be able to remove the last item in $O(1)$ time? If yes, write down some pseudocode of how that would work. If no, why not - what else would we need?
A doubly linked list is like a linked list, except each node keeps track of the item both before and after it in the list.
We can also keep track of the tail - the end of the list.
This gives us O(1) access to both ends of the list - for adding or removing items from the ends!
We could use this to implement a queue in which both enqueue and dequeue are O(1). Hooray!
The code for a doubly linked list is similar to a linked list, except
prev and next references for each node any time you add or remove an itemThis can be a headache to implement - so I'm not going to make you add code to this. But, here's what the code looks like. Caveat: I wrote this from scratch, and I hope I caught all the bugs...
class DoubleNode:
def __init__(self,initdata):
self.__data = initdata
self.__next = None
self.__prev = None
def get_data(self):
return self.__data
def get_next(self):
return self.__next
def get_prev(self):
return self.__prev
def set_data(self,newdata):
self.__data = newdata
def set_next(self,newnext):
self.__next = newnext
def set_prev(self,newprev):
self.__prev = newprev
class DoublyLinkedList:
def __init__(self):
"""a DoublyLinkedList is initially empty"""
self.__head = None
self.__tail = None
self.__length = 0
def is_empty(self):
return self.__head == None
def size(self):
return self.__length
def append(self,item):
#create the new node
temp = DoubleNode(item)
#case 1: the list is empty
if self.is_empty():
self.__head = temp
self.__tail = temp
#case 2: the list has 1 item
elif self.__length == 1:
self.__tail = temp
self.__tail.set_prev(self.__head)
self.__head.set_next(self.__tail)
#case 3: the list has 2 or more items
else:
self.__tail.set_next(temp)
temp.set_prev(self.__tail)
self.__tail = temp
#update the length counter because we added an item
self.__length += 1
def prepend(self,item):
#create the new node
temp = DoubleNode(item)
#case 1: the list is empty
if self.is_empty():
self.__head = temp
self.__tail = temp
#case 2: the list has 1 item
elif self.__length == 1:
self.__head = temp
self.__head.set_next(self.__tail)
self.__tail.set_prev(self.__head)
#case 3: the list has 2 or more items
else:
self.__head.set_prev(temp)
temp.set_next(self.__head)
self.__head = temp
#update the length counter because we added an item
self.__length += 1
def __repr__(self):
list_representation = "None <-> "
current = self.__head #start with the Node at the head
while current: #this will keep going until current equals None
list_representation += str(current.get_data())+" <-> "
current = current.get_next() #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):
#case 1: the index is out of range - error
if index >= self.__length or index < (-1)*self.__length:
raise Exception("list index "+str(index)+" out of range")
#case 2: positive index - count starting at the head
elif index >= 0:
current = self.__head
item_counter = 0
while current and item_counter < index:
current = current.get_next()
item_counter += 1
#case 3: negative index - count starting at the tail
else:
current = self.__tail
item_counter = -1
while current and item_counter > index:
current = current.get_prev()
item_counter -= 1
return current.get_data()
def pop(self,index):
#case 1: the index is out of range - error
if index >= self.__length or index < (-1)*self.__length:
raise Exception("list index "+str(index)+" out of range")
#case 2: the list is empty - error
elif self.__head == None:
raise Exception("You cannot pop from an empty list")
#case 3: there is only one item
elif self.__head == self.__tail and (index == 0 or index == -1):
self.__length -= 1
temp = self.__head
self.__head = None
self.__tail = None
return temp.get_data()
#case 4: 2 or more items, popping the first item
elif index == 0 or index == self.__length*(-1):
self.__length -= 1
temp = self.__head
self.__head.get_next().set_prev(None)
self.__head = self.__head.get_next()
return temp.get_data()
#case 5: 2 or more items, popping the last item
elif index == -1 or index == self.__length-1:
self.__length -= 1
temp = self.__tail
self.__tail.get_prev().set_next(None)
self.__tail = self.__tail.get_prev()
return temp.get_data()
#case 6: 2 or more items, popping a non-end, counting from left
elif index > 0:
self.__length -= 1
current = self.__head
trailing = None
item_counter = 0
while current and item_counter < index:
trailing = current
current = current.get_next()
item_counter += 1
trailing.set_next(current.get_next())
current.get_next().set_prev(trailing)
return current.get_data()
#case 7: 2 or more items, popping a non-end, counting from right
elif index < 0:
self.__length -= 1
current = self.__tail
trailing = None
item_counter = -1
while current and item_counter > index:
trailing = current
current = current.get_prev()
item_counter -= 1
trailing.set_prev(current.get_prev())
current.get_prev().set_next(trailing)
return current.get_data()
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.prepend(4)
dll.prepend(5)
print("Here's the list:",dll)
print("Item at index 3:",dll[3])
print("Item at index -1:",dll[-1])
print("Popping index 3:",dll.pop(3))
print("Popping index -1:",dll.pop(-1))
print("Here's the resulting list:",dll)
print("Its size is",dll.size())
Here's the list: None <-> 5 <-> 4 <-> 1 <-> 2 <-> 3 <-> None Item at index 3: 2 Item at index -1: 3 Popping index 3: 2 Popping index -1: 3 Here's the resulting list: None <-> 5 <-> 4 <-> 1 <-> None Its size is 3
Recall: when we made our Queue ADT using a Python list as the underlying data structure, one of enqueue and dequeue had to be $O(n)$.
We can now use a doubly linked list instead, and all the operations will be $O(1)$.
class Queue:
def __init__(self):
self.__dll = DoublyLinkedList()
def is_empty(self):
return self.__dll.is_empty()
def enqueue(self,item):
self.__dll.append(item)
def dequeue(self):
return self.__dll.pop(0)
def size(self):
return self.__dll.size()
def __repr__(self):
rval = "Front|"
for i in range(self.size()):
rval += str(self.__dll[i])+","
rval = rval.strip(",")
rval += "|Back"
return rval
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)
print("Starting queue:",q)
print( q.dequeue() )
print( q.dequeue() )
print( q.dequeue() )
print("Ending queue:",q)
print("Size:",q.size() )
Starting queue: Front|1,2,3,4,5|Back 1 2 3 Ending queue: Front|4,5|Back Size: 2
Chapter 4 of the book has implementations for two more Abstract Data Types that we haven't looked at yet:
The book uses an array (i.e., a Python list) to implement the Deque and a linked list to implement the OrderedList. However, like their implementation of the Queue, these may not necessarily be the best choices.
For each one, discuss, which would be the better choice to implement that ADT: array, linked list, or doubly-linked list. Give reasons to back up your choice. Time complexity of the different methods should be the main consideration, so start there, but you may be able to come up with some other reasons as well.