CODEWITHSUNDEEP
pythonlinked-listsingly-linked-list
huzzzus
huzzzus

Reputation: 300

Inserting same node twice in LinkedList triggers infinite loop

I am trying to understand why does inserting the same node twice in a singly linked list causes an infinite loop.

I tried to insert the last node as the new head node. But when I run the code, it's starting an infinite loop I can see since I am calling a method to print nodes at the end. Here's my code.

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


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

    def insertLast(self, newNode):
        if self.head is None:
            self.head = newNode
        else:
            lastNode = self.head
            while True:
                if lastNode.next is None:
                    break
                lastNode = lastNode.next
            lastNode.next = newNode

    def insertHead(self, newNode):
        # x, y ,z. => new head, x,y,z
        if self.head is None:
            print("List is empy please call inserlast()")
        else:

            currentHead = self.head
            self.head = newNode
            self.head.next = currentHead

    def printList(self):
        if self.head is None:
            print("EMPTY List. No Data found!")
            return
        else:
            currentNode = self.head
            while True:
                print(currentNode.data)
                currentNode = currentNode.next
                if currentNode is None:
                    break


node1 = Node("Head")
node2 = Node("Some Data")
node3 = Node("Some More Data")

# I am adding this node at the end of the list
newnode1 = Node("New Head")

linkedList = LinkedList()

# create a new linked list by inserting at end
linkedList.insertLast(node1)
linkedList.insertLast(node2)
linkedList.insertLast(newnode1)

# using a node i have already added in the list as New head of the list
linkedList.insertHead(newnode1)
linkedList.printList()

Upvotes: 0

Views: 447

Answers (2)

Nour-Allah Hussein
Nour-Allah Hussein

Reputation: 1459

Briefly, according to your code, the infinite loop you face results from the fact that    The linked list does not arrange the nodes physically, it just tells each node which node is next.

Let us explain it in details:

As shown, each node has a next attribute which is set by LinkedList to the next one.

after initiating the Nodes

node1.next mentions to None
node2.next mentions to None
newnode1.next mentions to None

after creating the linked list

node1.next mention to Node2
node2.next mention to Newnode1
newnode1.next mention to None

after inserting Newnode1 again as a head, the linked list set Nownode1.next to mention to Node1, and the hole figure becomes:

node1.next mention to Node2
node2.next mention to Newnode1
newnode1.next mention to Node1

Therefor, it becomes a closed loop

The linked list does not arrange the nodes physically, it just tells each node which node is next.

That is the explanation of the infinite loop you face.

Good Luck

Upvotes: 1

Samwise
Samwise

Reputation: 71464

When you re-add an existing node to the list, you don't do anything about existing nodes that already referenced the re-added node. In your case, you now have a node at the end of the list whose next points back to the node which has just become the head, and so now your list is circular, which is going to cause any function which tries to traverse the list to infaloop.

There are three ways I can think of to solve this, and I'll save the best for last:

  1. Add cycle detection logic to protect you from infalooping when your list becomes circular (i.e. break the cycles or just stop traversing once you get back to someplace you've already been). This is nontrivial and IMO not a great solution; better to keep the list from getting broken in the first place than have to constantly check to see if it needs fixing.

  2. Add a removeNode function to ensure that a given node has been fully removed from the list (i.e. by scanning through the whole list to see what other nodes, if any, reference the given node, and adjusting pointers to skip over it). Then you can safely re-insert a node by first removing it. Note: if the caller passes you a Node that belongs to a DIFFERENT list, you can still end up in trouble, because you'll have no way of finding that other list! Circular structures will still be possible by building lists and then inserting the nodes of each into the other.

  3. Don't allow callers of your list class to access the actual nodes at all; have them insert values (rather than nodes) so that you can ensure that they're never giving you a node with weird pointer values (a node that belongs to another list, a node that points to itself, etc). The pointers should be completely internal to your linked list class rather than something that the caller can mess up.

Upvotes: 2

Related Questions