CODEWITHSUNDEEP
pythonsingly-linked-list
papa_pig
papa_pig

Reputation: 9

Python - LinkedList confusion

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None    

    def insert_at_end(self,data):   >>> this function is working
        print('self.head: ', self.head)
        if self.head is None:
            self.head = Node(data, None)
            return
        
        itr = self.head

        while itr.next != None:
            itr = itr.next

        itr.next = Node(data, None)

def insert_at_end(self,data):   >>> this function is NOT working
    n = self.head
    node = Node(data, None)
    if n is None:
        n = node
        return
    
    while n.next != None:
        n = n.next
    n.next = node

When I add a node at end, the function which is not working gives me an empty list but the function which is working gives me a list. I think I am missing a basic point but unable to understand. I am new to Python and learning DSA.

if __name__ == '__main__':
    ll = LinkedList()
    ll.insert_at_end(100)
    ll.insert_at_end(101)
    ll.print_ll()

The working function gave me 100-->101--> The non working function gave me empty linked list.

Below is the print function which I used in both cases.

    def print_ll(self):
        if self.head == None:
            print("Empty Linked List")
            return

        n = self.head
        strll = ''
        
        while n != None:
            strll += str(n.data) + '-->'
            print("linkedlist: ", strll)

            n = n.next

Upvotes: -1

Views: 92

Answers (3)

KUDRAT ARORA
KUDRAT ARORA

Reputation: 1

The issue with the non-working function lies in how the new node is assigned to the linked list.

WORKING FUNCTION:

def insert_at_end(self, data):
print('self.head: ', self.head)
if self.head is None:
    self.head = Node(data, None)
    return

itr = self.head
while itr.next != None:
    itr = itr.next

itr.next = Node(data, None)

In this version, self.head is correctly updated when the list is empty, and new nodes are added to the end by traversing the list using the itr pointer.

NON-WORKING FUNCTION

def insert_at_end(self, data):
n = self.head
node = Node(data, None)
if n is None:
    n = node
    return

while n.next != None:
    n = n.next
n.next = node

Corrected Non-Working Function:

def insert_at_end(self, data):
node = Node(data, None)
if self.head is None:
    self.head = node  # Update self.head
    return

n = self.head
while n.next != None:
    n = n.next
n.next = node

Now, self.head is updated correctly when the list is empty, ensuring that the new node is properly linked as the first node in the list.

Working Function: Properly updates self.head and uses a pointer to traverse and append nodes.

Non-Working Function: Fails to update self.head when the list is empty.

Solution: Ensure self.head is updated in the initial check for an empty list.

In the fixed function, the behavior should now match the working function, and the linked list will correctly append nodes at the end.

Upvotes: 0

Chris
Chris

Reputation: 36611

Blckknght has nicely identified the problem with your code, but you can also make things easier on yourself (and improve performance) by storing the last element in your list along with the head.

You'll probably also find it useful to implement __iter__ for your linked list.

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None    
        self.last = None

    def insert_at_end(self, data):   
        if self.head is None:
            self.head = Node(data)
            self.last = self.head
            return
        
        n = Node(data)
        self.last.next = n
        self.last = n

    def __iter__(self):
        itr = self.head
        while itr != None:
            yield itr.data
            itr = itr.next

With __iter__ then you can implement __str__ with something like:

    def __str__(self):
        return ' --> '.join(str(x) for x in self)

Upvotes: 0

Blckknght
Blckknght

Reputation: 104762

The issue you have is that:

n = self.head
n = node

Isn't the same thing as:

self.head = node

The first version just assigns two different values to the same local variable n, while the second modifies the head attribute of self in a way that will persist outside of the function.

Upvotes: 3

Related Questions