我已经用Node类和LinkedList类在python中创建了一个非常标准的链表。我还为LinkedList添加了如下方法：
- add(newNode(：将元素添加到链表中
- addBefore(valueToFind，newNode(：在具有指定值的元素之前添加新节点
- 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()
周一->周三
如果您有拼写错误，请参阅下面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
希望这能帮助
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
要详细说明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}
星期一仍然指向星期三，尽管我们肯定会把下一个定在星期二。等等，星期一还有"nextval"到星期二，还有"nextval'到星期三。。。打字错误！！！nextval和nextval完全不同！
哦，是的，我的打印有那个输出，因为我把它添加到类节点：
def __repr__(self):
if self.nextval:
return self.dataval + '->' + self.nextval.dataval
return self.dataval
这里有一个修复程序，它改变了您之前查找下一个要插入的节点的方式，并单独处理任何头插入。我还更改了变量和类属性的名称，使其更加清晰：
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风格的链表。