Day 15: Linked List | HackerRank | Python

The Problem

We are provided with a Node class in the editor. Each Node object has an integer data field, data, and a Node instance pointer, next, which points to the next node in a linked list. A function insert is also declared, which takes two parameters: a pointer, head, pointing to the first node of a linked list, and an integer, data, that must be added to the end of the list as a new Node object.

Task

The task is to complete the insert function so that it creates a new Node (passing data as the Node constructor argument) and inserts it at the tail of the linked list referenced by the head parameter. After the new node is added, the function should return the reference to the head node.

Note: The head argument is null for an empty list.

The Input

The first line contains T, the number of elements to insert. Each of the next T lines contains an integer to insert at the end of the list.

Sample Input:

4
2
3
4
1

The Output

The function should return a reference to the head node of the linked list.

Sample Output:

2 3 4 1

Explanation

T=4, so your function will insert 4 nodes into an initially empty list. It will first return a new node that contains the data value 2 as the head of the list. Then it will create and insert nodes 3, 4, and 1 at the tail of the list.

The Solution

Here are three Python solutions, each with its own strengths and weaknesses:

Source Code 1

This solution creates a new node and then traverses the linked list to find the tail node, upon which it appends the new node. This solution is straightforward and intuitive but may be a bit slow for very large lists because it traverses the entire list to find the tail node.

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): 
        node = Node(data)
        if head:
            tail = head
            while tail.next:
                tail = tail.next
            tail.next = node
            return head
        return node

mylist= Solution()
T=int(input())
head=None
for i in range(T):
    data=int(input())
    head=mylist.insert(head,data)    
mylist.display(head);

Source Code 2

This refactored solution does the same thing but has a slight improvement in readability. The logic of checking for an empty list is moved to the top of the insert function, making it immediately clear what happens in that case. This doesn't change the performance but enhances the readability and maintainability of the code.

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):
        node = Node(data)
        if not head:
            return node

        tail = head
        while tail.next:
            tail = tail.next

        tail.next = node
        return head

mylist = Solution()
T = int(input())
head = None

for _ in range(T):
    data = int(input())
    head = mylist.insert(head, data)

mylist.display(head)

Source Code 3

If we want to optimize the insert function, we could maintain a reference to the tail of the list. However, since the scope of the optimization is limited to the insert function, we cannot store the tail as an attribute of the Solution class.

Here is an optimized version of the insert function that uses a local static variable to keep track of the tail of the list. A local static variable is a variable that retains its value between the function calls.

Please note that this concept is not directly available in Python. However, we can achieve similar functionality using mutable objects like a list or a dictionary. In the following example, we use a list to simulate a static variable:

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): 
        node = Node(data)
        if not head:
            self.tail = [node]  # initialize the static variable
            return node
        else:
            self.tail[0].next = node  # update the next attribute of the tail node
            self.tail[0] = node  # update the tail node
            return head

mylist = Solution()
T = int(input())
head = None
for i in range(T):
    data = int(input())
    head = mylist.insert(head, data)    
mylist.display(head)

The advantage of this method is that we don't need to traverse the list each time we want to add a new node. The time complexity of the insert function becomes O(1), which means that the function will have the same performance regardless of the size of the list.

Using the service like ChatGPT can help you tidy and clean up your code, making it easier to read and maintain. It can also help you spot logical errors or suggest improvements in your code structure. In fact source code 2 and 3 were generated by ChatGPT GPT4!

Original Source

For more insightful solutions and tech-related content, feel free to connect with me on my Beacons page.

ranggakd - Link in Bio & Creator Tools | Beacons

@ranggakd | center details summary summary Oh hello there I m a an Programmer AI Tech Writer Data Practitioner Statistics Math Addict Open Source Contributor Quantum Computing Enthusiast details center.

beacons.ai