无法在循环单链表中插入节点

Question

我无法在给定的代码中获得所需的输出。代码是在循环单链表中插入节点。请根据所述问题更正此代码。

class Node:
    def __init__(self,value):
        self.value = value
        self.next = None
 
class CircularSLL:
    
    def __init__(self):
        self.head = None
        self.tail = None
        
    def __iter__(self):
        node = self.head
        while node:
            yield node
            if node.next == self.head:
                print('break')
                break
            node = node.next
            
    def insertnode(self, value, location):
        new_node = Node(value)
        
        # check if head is None or not
        
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            new_node.next = self.head
            
        else:
            
            
            
            # At the start
            if location == 0:
                new_node.next = self.head
                self.head = new_node
                self.tail.next = self.head
            
            # At the end
            elif location == -1:
                new_node.next = self.tail.next
                self.tail.next = new_node
                self.tail = new_node
                
            else:
                
                # At specific location
                temp_node = self.head
                index = 0
                
                while index < location - 1:
                    
                    # node is the last element
                    if temp_node.next == self.head:
                        break
                    temp_node = temp_node.next
                    index += 1
                
                next_node = temp_node.next
                temp_node.next = new_node
                new_node.next = next_node
                
                if temp_node.next == self.head:
                    self.tail == temp_node
                    self.tail.next = self.head
                
            return 'The node has been successfully inserted'
 
cll = CircularSLL()
 
cll.insertnode(1,0)
 
cll.insertnode(3, 1)
 
cll.insertnode(4, 2)
 
cll.insertnode(5, 3)
 
cll.insertnode(6, 4)
 
print([node.value for node in call])

输出=[1,3,4,5,6]

第一个问题 - 在索引 = '0' 处插入时。

cll.insertnode(10,0)

输出=[10,1]

预计

输出=[10,1,3,4,5,6]

第二个问题-放置location = '-1'时

cll.insertnode(30, -1)

输出 = [1, 30]

预计

输出=[10,1,3,4,5,6,30]

Answer 1

使用您的测试设置，tail 在插入第一个节点后永远不会设置。

(Pdb) [c.value for c in cll]
[1, 3, 4, 5, 6]
(Pdb) cll.head.value
1
(Pdb) cll.tail.value
1
(Pdb) cll.head is cll.tail
True

你的第一个问题是你有 self.tail == temp_node 而不是 self.tail = temp_node，所以让我们解决这个问题。仍然，我们没有得到预期的输出：

[1, 3, 4, 5, 6]

下一个问题是，当您检查 if temp_node.next is self.head: 时，您已经将 temp_node.next 设置为 new_node。它永远不会是 self.head。我相信您此时打算检查 new_node.next，因为它现在是最后一个元素。

简单替换

                if temp_node.next == self.head:
                    self.tail == temp_node
                    self.tail.next = self.head

和

                if new_node.next is self.head:
                    self.tail = new_node

获得

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

class CircularSLL:

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

    def __iter__(self):
        node = self.head
        while node:
            yield node
            if node.next is self.head:
                break
            node = node.next

    def insertnode(self, value, location):
        new_node = Node(value)

        # check if head is None or not

        if self.head is None:
            self.head = new_node
            self.tail = new_node
            new_node.next = self.head

        else:
            # At the start
            if location == 0:
                new_node.next = self.head
                self.head = new_node
                self.tail.next = self.head

            # At the end
            elif location == -1:
                new_node.next = self.tail.next
                self.tail.next = new_node
                self.tail = new_node

            else:
                # At specific location
                temp_node = self.head
                index = 0

                while index < location - 1:
                    # node is the last element
                    if temp_node.next is self.head:
                        break
                    temp_node = temp_node.next
                    index += 1

                next_node = temp_node.next
                new_node.next = next_node
                temp_node.next = new_node

                if new_node.next is self.head:
                    self.tail = new_node


            return 'The node has been successfully inserted'

cll = CircularSLL()

cll.insertnode(1,0)

cll.insertnode(3, 1)

cll.insertnode(4, 2)

cll.insertnode(5, 3)

cll.insertnode(6, 4)

cll.insertnode(10,0)

cll.insertnode(30, -1)

print([node.value for node in cll])

输出： [10, 1, 3, 4, 5, 6, 30]

我还在几个地方用 is 替换了 == 以更清楚地测试同一性而不是等效值。

无法在循环单链表中插入节点

Unable to Insert node in Circular Singly linked list

python

oop

algorithm

linked-list

data-structures