I am implementing a linked list from scratch on Python. I have already implemented. In particular, I am interested in the different implementations of the append method. Following the instructions on the book that I am using, after implementing append
as a linear time function, I am now trying to implement it in constant time.
I first I create a Node
class that will help create my linked list:
class Node:
"""
A node class that is used to implement a linked list object.
The node contains a data field, aka the item in the node and a
reference to the next node.
"""
def __init__(self, init_data):
self.data = init_data
self.next = None
def get_data(self):
return self.data
def get_next(self):
return self.next
def set_data(self, new_data):
self.data = new_data
def set_next(self, new_next):
self.next= new_next
Here is my implementation of the linked list with its different methods:
from node_class import Node
class UnorderedList:
"""
An unordered list class built from a collection of nodes.
"""
def __init__(self):
self.head = None
def is_empty(self):
return self.head == None
def add(self, item):
temp = Node(item)
temp.set_next(self.head)
self.head = temp
def size(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.get_next()
return count
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.get_data() == item:
found = True
else:
current = current.get_next()
return found
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.get_data() == item:
found = True
else:
previous = current
current = current.get_next()
if previous == None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())
def print_list(self):
current = self.head
while current != None:
print(current.data)
current = current.get_next()
def append(self, item):
new_node = Node(item)
## Append Linear Time O(n)
if self.head == None:
self.head = new_node
return
current = self.head
found_last = False
while not found_last:
if current.get_next() == None:
found_last = True
current.set_next(new_node)
else:
current = current.get_next()
I know my implementation of append is linear time as it has to traverse the length of the list to find the last Node so it can append my new node to it.
The logic I am following to implement my constant time solution is first adding an instane variable named tail so I can point it to the last node (thus bypassing the need to traverse the whole list to find the last node). I am considering the special case where my list might be only 1 item long.
Intuitively, this should work, as like I mentioned I won't need to traverse the whole list to find the last item, I can simply set my tail's next node to the new node that I want to append. My question is, whether there are any instances where this won't work?
I added a modified version of my add method as it is another way of adding nodes and I will need to keep track of the last node too if I want to keep my append method constant time.
class UnorderedList:
"""
An unordered list class built from a collection of nodes.
"""
def __init__(self):
self.head = None
self.tail = None
def add(self, item):
temp = Node(item)
temp.set_next(self.head)
if self.head == None:
self.tail = temp
self.head = temp
def append(self, item):
new_node = Node(item)
## Append Constant Time O(1)
if self.head == None:
self.tail = new_node
self.head = new_node
return
else:
self.tail.set_next(new_node)
return