在链表中插入Python

Question

null

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

因为每个节点都包含对下一个节点的引用，所以称之为NodePointer。这对这里有帮助（我认为）：

    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样式的链表。