CODEWITHSUNDEEP
python-3.xoopinfinite-loopsingly-linked-list
Gober
Gober

Reputation: 167

Singly linked list infinite loop when sharing elements between lists in Python

I implemented a linked list using Python 3.6, the linked list itself works well, but the problem is when I try to create the following example: 

3 -> 1 -> 5 -> 9 ->
                   7 -> 2
          4 -> 6 ->

It means I have 2 linked lists and in a certain point they share the same elements (7,2), the code of my linked list is the following:

class Element:    
    def __init__(self,value):
        self.next = None 
        self.value = value

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

    def append(self,new_element):
        current = self.head
        if current:
            while current.next:
                current = current.next
            current.next = new_element
        else:   
            self.head = new_element

    def print_linked(self):
        current = self.head
        while current:
            print(current.value, end=" ")
            current = current.next

e1 = Element(3)
e2 = Element(1)
e3 = Element(5)
e4 = Element(9)

e1p = Element(4)
e2p = Element(6)

e1s = Element(7)
e2s = Element(2)

# Start setting up a LinkedList
ll = LinkedList(e1)
ll.append(e2)
ll.append(e3)
ll.append(e4)
ll.append(e1s)
ll.append(e2s)

l2 = LinkedList(e1p)
l2.append(e2p)
l2.append(e1s)
l2.append(e2s)

When I try to print any of the linked list, the program always enters in an infinite loop at the last element and only happens when I try to share the same element. 

3 1 5 9 7 2 2 2 2 2 2 2 [...]

Am I missing something?. Help is appreciated. Thanks

Upvotes: 0

Views: 116

Answers (1)

Reut Sharabani
Reut Sharabani

Reputation: 31339

Lets go over this:

ll.append(e2)
ll.append(e3)
ll.append(e4)
ll.append(e1s)
ll.append(e2s)

After this code run the internal state for the last item (e2s) is it points to nowhere.

But then:

l2.append(e2p)
l2.append(e1s)
l2.append(e2s)

This makes the last item point to itself (l2.append(e2s) appends without regard to cycles). You iterate the entire list and append the item even if it is already there.

Because the state is internal to the nodes (Element) you probably have two options:

  1. Don't share state (make a copy)
  2. Check for exitence of node and do not allow it to repeat in a list

You can raise an error in case of duplicate items:

def append(self,new_element):
    current = self.head
    if current is new_element:
        raise ValueError('can not duplicate node %s on list' % new_element)
    if current:
        while current.next:
            current = current.next
        current.next = new_element
    else:   
        self.head = new_element

Upvotes: 1

Related Questions