插入到链表Python中

Question

我用python创建了一个非常标准的链表，其中包含一个节点类和LinkedList类。我还为LinkedList添加了如下方法：

1. 添加（newNode）：将元素添加到链接列表中
2. addBefore（valueToFind，newNode）：在具有指定值的元素之前添加新节点
3. printClean：打印链接列表

我试图使用addBefore方法来执行插入，但是如果插入不在头部，它将不起作用。我不知道为什么

class Node:
    def __init__(self, dataval =None):
        self.dataval = dataval
        self.nextval = None

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

    def add(self, newNode):
        # The linked list is empty
        if(self.headval is None):
            self.headval = newNode
        else:
            # Add to the end of the linked list
            currentNode = self.headval
            while currentNode is not None:
                # Found the last element
                if(currentNode.nextval is None):
                    currentNode.nextval = newNode
                    break
                else:
                    currentNode = currentNode.nextval


    def addBefore(self, valueToFind, newNode):
        currentNode = self.headval
        previousNode = None
        while currentNode is not None:
            # We found the element we will insert before
            if (currentNode.dataval == valueToFind):
                # Set our new node's next value to the current element
                newNode.nextval = currentNode

                # If we are inserting at the head position
                if (previousNode is None):
                    self.headval = newNode
                else:
                    # Change previous node's next to our new node
                    previousNode.nexval = newNode
                    return 0

            # Update loop variables
            previousNode = currentNode
            currentNode = currentNode.nextval
        return -1

    def printClean(self):
        currentNode = self.headval
        while currentNode is not None:
            print(currentNode.dataval, end='')
            if(currentNode.nextval != None):
                print("->", end='')
                currentNode = currentNode.nextval
            else:
                return

testLinkedList = LinkedList()
testLinkedList.add(Node("Monday"))
testLinkedList.add(Node("Wednesday"))
testLinkedList.addBefore("Wednesday", Node("Tuesday"))
testLinkedList.printClean()

Monday->Wednesday

Answer 1

要详细说明Satvir Kira的评论，请使用此测试工具

monday = Node("Monday")
tuesday = Node("Tuesday")
wednesday = Node("Wednesday")

testLinkedList = LinkedList()
testLinkedList.add(monday)
testLinkedList.add(wednesday)
testLinkedList.addBefore(wednesday.dataval, tuesday)

print (monday.__dict__)
print (tuesday.__dict__)
print (wednesday.__dict__)

输出：

{'dataval': 'Monday', 'nextval': Wednesday, 'nexval': Tuesday->Wednesday}
{'dataval': 'Tuesday', 'nextval': Wednesday}
{'dataval': 'Wednesday', 'nextval': None}

星期一仍然指向星期三，尽管我们确定下一个星期二是星期二。等等，星期一也有下星期二和下星期三。。。打字错误nexval和nextval完全不同

哦，是的，我的指纹有那个输出，因为我把它添加到类节点：

def __repr__(self):
    if self.nextval:
        return self.dataval + '->' + self.nextval.dataval
    return self.dataval

Answer 2

希望这有帮助

def addBefore(self, valueToFind, newNode):
        currentNode = self.headval # point to headval
        previousNode = None 
        while currentNode.data != valueToFind: # while currentNode.data is not equal to valueToFind, move currentNode to next node and keep track of previous node i.e. previousNode
            previousNode = currentNode # keep tack of previous node
            currentNode = currentNode.nextval # move to next node

        previousNode.nextval = newNode # previous node will point to new node
        previousNode = previousNode.nextval # move previous node to newly inserted node
        previousNode.nextval = currentNode # previous node ka next will to currentNode

Answer 3

如果您有输入错误，请参阅addBefore方法中的#TODO：

    def addBefore(self, valueToFind, newNode):
    currentNode = self.headval
    previousNode = None
    while currentNode is not None:
        # We found the element we will insert before
        if (currentNode.dataval == valueToFind):
            # Set our new node's next value to the current element
            newNode.nextval = currentNode

            # If we are inserting at the head position
            if (previousNode is None):
                self.headval = newNode
            else:
                # Change previous node's next to our new node
                previousNode.nexval = newNode #TODO: Fix Typo: nexval
                return 0

        # Update loop variables
        previousNode = currentNode
        currentNode = currentNode.nextval
    return -1