I’ve been doing the 30 Days of Code challenge at HackerRank. My python skills are being tested and it’s helping use the language to the fullest. On this day, I’ve come across linked lists. This is in data structure/algorithm territory and that means it’s scary. I wont be scared though.
Task
Complete the insert function in your editor so that it creates a new Node (pass data as the Node constructor argument) and inserts it at the tail of the linked list referenced by the head parameter. Once the new node is added, return the reference to the head node.
And this is the code given to me:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Solution:
def display(self, head):
current = head
while current:
print(current.data, end=' ')
current = current.next
def insert(self, head, data):
#Complete this method
mylist= Solution()
T = int(input())
head = None
for i in range(T):
data = int(input())
head = mylist.insert(head,data)
mylist.display(head)
What is known?
How to insert a new node into a linked list?
I started by looking if there was a preexisting head. If not, it becomes the head.
def insert(self, head, data):
# if the head doesn't exist
if (head == None):
# the head becomes a new object (the first!)
head = Node(data)
Now there is a head. What happens next?
Well now I can use the nifty instance variable ‘next’ to see if it’s vacant. If so, this code will make the next node in the list
def insert(self, head, data):
if (head == None):
head = Node(data)
# if the next head doesn't exist
elif (head.next == None):
# make this new input a new Node object
head.next = Node(data)
I just need to add a nice recursive else clause as a catch-all and a return to tidy it all up.
def insert(self, head, data):
if (head == None):
head = Node(data)
elif (head.next == None):
head.next = Node(data)
else:
# if there are already multiple nodes
# shift the head to the next head and restart
# until one of the if statements apply
self.insert(head.next, data)
# when there is no more input data
return head
Linked lists are pretty much the beginning of data structures for me. They seem to be extremely important in the field I’m studying for: computer science. So I want to be prepared for future interviews. I’ve heard they ask many questions involving that data structures/algorithms.