Retiago Drago

Posted on

# 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.

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:
while current:
print(current.data,end=' ')
current = current.next

node = Node(data)
while tail.next:
tail = tail.next
tail.next = node
return node

mylist= Solution()
T=int(input())
for i in range(T):
data=int(input())
``````

### 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:
while current:
print(current.data, end=' ')
current = current.next

node = Node(data)
return node

while tail.next:
tail = tail.next

tail.next = node

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

for _ in range(T):
data = int(input())

``````

### 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:
while current:
print(current.data,end=' ')
current = current.next

node = Node(data)
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

mylist = Solution()
T = int(input())
for i in range(T):
data = int(input())
``````

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