Вставка в связанный список Python

Question

Я создал довольно стандартный связанный список в python с классом Node и классом LinkedList. Я также добавил методы LinkedList следующим образом:

1. add (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()

Понедельник-> Среда

Answer 1

Это исправление, которое меняет внешний вид следующего узла для вставки ранее и обрабатывает любую вставку головки отдельно. Я также изменил имена переменных и атрибутов класса, чтобы сделать вещи немного понятнее:

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

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

Поскольку каждый узел содержит ссылку на следующий узел, называемый его указателем узла. Это помогает здесь (я думаю):

    def addBefore(self, valueToFind, newNode):

        currentNode = self.headnode

        if currentNode.dataval == valueToFind:    #treat the front-end insertion as a 
            newNode.nodepointer = self.headnode   #special case outside the while loop
            self.headnode = newNode
            return -1

        while currentNode.nodepointer:            #notice lose all the 'is None' syntax
            # We found the element we will insert before *by looking ahead*
            if currentNode.nodepointer.dataval == valueToFind:
                # Set our new node's next *reference* to the current element's *next ref*
                newNode.nodepointer = currentNode.nodepointer
                currentNode.nodepointer = newNode  #now link 'previous' to new Node
                return -1                
            # Update loop variables
            currentNode = currentNode.nodepointer  #if this is None, while loop ends
        return 0

Это больше похоже на традиционный список C в стиле, я думаю.

Answer 2

У вас есть опечатка, смотрите ниже #TODO в методе addBefore:

    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

Answer 3

Чтобы уточнить комментарий Сатвира Киры, используйте этот тестовый жгут

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 на вторник. Подождите, понедельник также имеет 'nexval' для вторника и 'nextval' для среды ... TYPO !!! nexval и nextval совершенно разные!

О, да, мои отпечатки имеют такой вывод, потому что я добавил это в узел класса:

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

Answer 4

Надеюсь, это поможет

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