• 1: Compare every element in the list with every other element in the list using nested loops. Sort the list using bubble sort, then determine if there are duplicates by comparing each item with the item that follows it in the list (if there are duplicates in the original list, they must be neighbors in the sorted list).

• Solution 2 Sort the list using merge sort (recursive), then determine if there are duplicates by comparing each item with the item that follows it in the list.

• Solution 3 Take advantage of the fact that the range of the integers in the list is fixed (0 to m, where m is the largest ID you can find in the linked list). Use a boolean array seen of length m+1 to indicate if elements in the array have been seen before. Then determine if there are duplicates by performing a single pass through the unsorted list. Hint: while traversing the list, seen[item] = True if integer item has been seen before in the search.

• Solution 4: Test code goes here - Use this code cell to call the methods you wrote in. The previous code cells. You can think of this code cell as your *main* cell

Determine the big-O running time of each of the previous solutions (1 to 4). Illustrate your results by means of plots and/or tables. Create your own activision.txt and vivendi.txt files to perform this analysis.

class LinkedListNode:

def __init__(self, item, next=None):

self.item = item

self.next = next

class LinkedList:

def __init__(self):

self.clear()

def clear(self):

self.head = None

self.tail = None

self.size = 0

def is_empty(self):

return self.size == 0

def append(self, item):

new_node = LinkedListNode(item=item)

if self.is_empty():

self.head = new_node

self.tail = new_node

else:

self.tail.next = new_node

self.tail = new_node

self.size += 1

def prepend(self, item):

self.head = LinkedListNode(item=item, next=self.head)

if self.is_empty():

self.tail = self.head

self.size += 1

def insert(self, idx, item):

if idx < 0 or idx > self.size:

raise Exception("Cannot insert -Index out of bounds")

elif idx == 0:

self.prepend(item=item)

elif idx == self.size:

self.append(item=item)

else:

new_node = LinkedListNode(item=item)

temp = self.head

for _ in range(idx - 1):

temp = temp.next

new_node.next = temp.next

temp.next = new_node

self.size += 1

def remove_first(self):

if self.is_empty():

raise Exception("Cannot remove - list is empty")

elif self.size == 1:

self.clear()

else:

self.head = self.head.next

self.size -= 1

def remove_last(self):

if self.is_empty():

raise Exception("Cannot remove - list is empty")

elif self.size == 1:

self.clear()

else:

temp = self.head

while temp.next.next:

temp = temp.next

temp.next = None

self.tail = temp

self.size -= 1

def remove(self, idx):

if self.is_empty():

raise Exception("Cannot remove - list is empty")

elif idx < 0 or idx >= self.size:

raise Exception("Cannot remove - Index out of bounds")

elif idx == 0:

self.remove_first()

elif idx == self.size - 1:

self.remove_last()

else:

temp = self.head

for _ in range(idx - 1):

temp = temp.next

temp.next = temp.next.next

self.size -= 1

def get(self, idx):

if idx < 0 or idx >= self.size:

raise Exception("Cannot retrieve - Index out of bounds")

elif idx == 0:

return self.head.item

elif idx == self.size - 1:

return self.tail.item

else:

temp = self.head

for _ in range(idx):

temp = temp.next

return temp.item

def __str__(self):

out_lst = []

temp = self.head

while temp:

out_lst.append(str(temp.item))

out_lst.append(' ')

temp = temp.next

return ''.join(out_lst)