having problem in displaying doubly circular linked list in python

Question

I am currently learning data structures in python and I am having problem in display() method in CircularDoublyLinkedList class

The while loop run infinitely by repeating the elements of the CircularDoublyLinkedList class

#my code:
class Node:
    def __init__(self,value):
        self.value=value
        self.next=None
        self.prev=None

class CircularDoublyLinkedList:
    def __init__(self):
        self.head=None
        self.tail=None

    def display(self):
        if self.head is None:
            return 'Circular doubly Linked list doesn\'t exists'
        else:
            node=self.head
            elements=[]
            while node:
                if node==self.tail:
                    break
                elements.append(node.value)
                print(node.value)
                node=node.next
        return elements

    def insertnode(self,value,position):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.tail=node
            self.prev=node
            self.next=node
        else:
            if position==0:
                node.prev=self.tail
                node.next=self.head
                self.head=node
                self.head.prev=node
                self.tail.next=node
            elif position==-1:
                node.next=self.head
                node.prev=self.tail
                self.tail=node
                self.tail.next=node
                self.head.prev=node
            else:
                index=0
                tempnode=self.head
                while index


I tried changing the if condition inside display() method from node==self.tail to node==self.tail.next but nothing changed
So how to resolve this error in display() method of class CircularDoublyLinkedList?
any help will be appreciated...thanks

trincot · Accepted Answer

There are several issues:

In display, the break should come after you have printed the tail value. So that loop should look like this:

while node:
    elements.append(node.value)
    print(node.value)
    if node==self.tail:
        break
    node=node.next

In insertnode, for the first case, you are assigning to self.prev and self.next, but those are not attributes that belong to self (which is a linked list instance, not a node instance). Instead you want:
```
node.prev=node
node.next=node
```
In insertnode, for the second case, you should not change self.head before assigning to self.head.prev. So swap these statements so you get this order:
```
self.head.prev=node
self.head=node
```
In insertnode, for the remaining case, you have a similar issue as in the previous point: first assign to self.tail.next and only then move the self.tail reference, so you get this order of execution:
```
self.tail.next=node
self.tail=node
```

With those fixes your code will work as expected.

Other remarks and alternative

In a circular doubly linked list you don't need a tail reference, because in a non-empty list that self.tail is always going to be equal to self.head.prev. So there is really no good reason to maintain it in a separate attribute. Leaving it out makes the code shorter without losing on efficiency.

As no node in a circular doubly linked list has a None value for either prev or next, it is more natural to initialise these attributes with a self-reference in the Node constructor.

Printing inside a method is not really nice: it mixes the linked-list logic with I/O concerns. Instead, make the linked list iterable by implementing the __iter__ method, and keep the printing in the main program code.

The code for insertnode can be reduced, by only determining what node.next must be, and then all the rest of the "wiring" can be common to all cases. The only exception is when a node is added to an empty list.

Applying those points we get this:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = self.prev = self  # No None in a doubly linked list

class CircularDoublyLinkedList:
    def __init__(self):
        self.head = None  # No tail needed

    def __iter__(self):  # iterator is useful for many scenarios
        node = self.head
        if node:
            yield node.value
            while node.next != self.head:
                node = node.next
                yield node.value

    def insertnode(self, value, position):
        node = Node(value)
        if not self.head:
            self.head = node  # node is already correctly wired
            return
        node.next = self.head
        if position == 0:
            self.head = node
        while position > 0:  # No need for an index variable
            node.next = node.next.next
            position -= 1
        # Common code:
        node.prev = node.next.prev
        node.prev.next = node.next.prev = node

cdll = CircularDoublyLinkedList()
cdll.insertnode(5, 0)
cdll.insertnode(0, 0)
cdll.insertnode(1, -1)
cdll.insertnode(2, 2)

print(*cdll)  # Use iterator for displaying

having problem in displaying doubly circular linked list in python

Answers (2)

Other remarks and alternative

Related Questions