时间戳

首页 > 解决方案 > 插入链表 Python

python - 插入链表 Python

问题描述

我在 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()

星期一->星期三

标签： pythondata-structureslinked-list

解决方案

希望这可以帮助

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

推荐阅读