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)

Where to start?

This video helped me a lot!

What is known?

• class Node
  – Two attributes (data, next)
• class Solution
  – Two functions (display, insert)

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.