Day 15: Linked List | HackerRank | Python
Tags: python, codenewbie, beginners, hackerrank
Published: 2023-05-13 06:05:00

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

![example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a84tclkzbnru6ryp30fj.png)

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

```python
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.

```python
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:

```python
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](https://www.hackerrank.com/challenges/30-linked-list/problem?isFullScreen=true)

For more insightful solutions and tech-related content, feel free to connect with me on my [Beacons page](https://beacons.ai/ranggakd).

{% embed https://beacons.ai/ranggakd %}