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

Question

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

Reut Sharabani · Accepted Answer · 2018-05-12 17:20:22Z

1

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:

Don't share state (make a copy)
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

edited May 12, 2018 at 17:20

answered May 12, 2018 at 17:13

Reut Sharabani

31.5k7 gold badges76 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Gober Over a year ago

I tried to make a deep copy of the object, but I would like to compare if two objects are the same using "is", the point of that it's check if two lists share she same element (object not by value). Is it possible to do that?

Reut Sharabani Over a year ago

If you make a copy than is (identity) is not going to be True.

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related