Linked List Queue

To use our Linked List as a fast queue (O(1) pushes and pops) we need our add_to_tail function to be O(1). Currently, it iterates over the entire list before appending an item. We can fix this by keeping track of the last item with a new data member: tail.

Note: It's common in algorithms to make this kind of trade-off. By using a little extra memory (keeping track of tail), we can make our operations faster. Sometimes you might need to go the other way, and use more computation time to save memory.

Assignment

LockedIn's queue was working just fine on small datasets, but appending items once the list has 100,000+ items has started to take a toll on our servers. Implement these changes to speed up our Linked List's inserts to O(1):

add_to_head should set the tail reference to the given node if the list is empty.
add_to_tail should:
1. Set the head and tail to the given node if the list is empty
2. Instead of iterating to find the last node, use the tail reference to append the new node
3. Update the tail reference to new node
The constructor should set self.tail to None.

from node import Node

class LinkedList:

def add_to_head(self, node):

node.set_next(self.head)

self.head = node

def add_to_tail(self, node):

if self.head is None:

self.head = node

return

last_node = None

for current_node in self:

last_node = current_node

last_node.set_next(node)

def __init__(self):

self.head = None

# don't touch below this line

def __iter__(self):

node = self.head

while node is not None:

yield node

node = node.next

def __repr__(self):

nodes = []

for node in self:

nodes.append(node.val)

return " -> ".join(nodes)

import random

import time

from main import *

run_cases = [

(10, "Patrick Bateman", "Paul Allen"),

(100, "Paul Allen", "Paul Allen"),

(1000, "Paul Allen", "Paul Allen"),

(10000, "Patrick Bateman", "Paul Allen"),

]

submit_cases = run_cases + [

(12000, "Paul Allen", "Paul Allen"),

]

def test(num_items, first_item, last_item):

print("---------------------------------")

print(f"Adding {num_items} job candidates to a linked list's head")

linked_list = LinkedList()

timeout = 1.5

start = time.time()

for item in get_items(num_items):

linked_list.add_to_head(Node(item))

print(f"Adding {num_items} job candidates to a linked list's tail")

linked_list2 = LinkedList()

for item in get_items(num_items):

linked_list2.add_to_tail(Node(item))

end = time.time()

print(f"Expecting to complete in less than {timeout * 1000} milliseconds")

if (end - start) < timeout:

print(f"Test completed in less than {timeout * 1000} milliseconds!")

else:

print("Fail")

class Node:

def __init__(self, val):

self.val = val

self.next = None

def set_next(self, node):

self.next = node

def __repr__(self):

return self.val