如何在链表中的另一个节点之间插入一个节点？
How to Insert a Node between another node in a Linked List?
我正在重温我之前发布的一个问题：
我很难搞清楚如何在单向链表的其他节点之间插入一个节点。在上面的解决方案中，我编写了一个额外的 getNodes 方法，将数据转换为节点并将其推送到节点之间，但它大大增加了时间复杂度。必须有一种方法可以在不使用这种自定义方法的情况下在节点之间插入，但我就是不知道怎么做。
这是我的新代码：
class Node(object):
def __init__(self, data):
self.data = data
self.nextNode = None
def __str__(self):
return str(self.data)
class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
def insert_in_between2(self, data, prev_data):
# instantiate the new node
new_node = Node(data)
# assign to head
thisval = self.head
# check each value in linked list against prev_data as long as value is not empty
prev_data2 = Node(prev_data)
while thisval is not None:
# if value is equal to prev_data
if thisval.data == prev_data2.data:
print("thisval.data == prev_data.data")
# make the new node's next point to the previous node's next
new_node.nextNode = prev_data2.nextNode
# make the previous node point to new node
prev_data2.nextNode = new_node
break
# if value is not eqaul to prev_data then assign variable to next Node
else:
thisval = thisval.nextNode
def push_from_head(self, NewVal):
new_node = Node(NewVal)
print("This is new_node: ", new_node.data)
last = self.head
print("This is last/HEAD: ", last)
if last is None:
print("Head is NONE")
self.head = new_node
print("This is self.head: ", self.head)
return
print("last.nextNode: ", last.nextNode)
while last.nextNode is not None:
print("this is last inside while loop: ", last.data)
print("last.nextNode is not NONE")
last = last.nextNode
print("This is the last last: ", last.data)
last.nextNode = new_node
print("This is last.nextNode: ", last.nextNode)
def print_nodes(self):
if self.head:
thisval = self.head
while thisval:
print("This is node: ", thisval.data)
thisval = thisval.nextNode
e1 = LinkedList()
e1.push_from_head(10)
e1.push_from_head(20)
e1.push_from_head(30)
e1.push_from_head(40)
e1.push_from_head(50)
e1.insert_in_between2(25, 20)
# print("This is the index: ", e1.getNode(1))
e1.print_nodes()
现在它打印：10、20、30、40、50 但它应该打印：10、20、25、30、40、50。
我认为问题出在 insert_in_between2 方法的这一行：
new_node.nextNode = prev_data2.nextNode
...因为这两个都打印出来 None。任何正确方向的帮助都会很棒。
您正在创建一个不属于列表的新节点：
prev_data2 = Node(prev_data)
prev_data 似乎是您正在搜索的要插入的值。
然后将新节点连接到该节点，但由于它不在列表中，因此有点孤立。你不需要那个节点。只需将您的新节点连接到您刚刚找到的节点即可：
while thisval is not None:
if thisval.data == prev_data: # you found the node before the insert
new_node.nextNode = thisval.nextNode # new node's next gos to found node's next
thisval.nextNode = new_node # found node's next goes to new node
#Linked List Program to Add and Delete Node Form Head, Tail, in Between Nodes.
class Node:
""" Node Class having the data and pointer to the next Node"""
def __init__(self,value):
self.value=value
self.nextnode=None
class LinkedList(object):
""" Linked List Class to point the value and the next nond"""
def __init__(self):
self.head=None
#Adding Node to the head of linked List
def head_node(self,value):
node=Node(value)
if self.head is None:
self.head=node
return
crnt_node=node
crnt_node.nextnode=self.head
self.head=crnt_node
# Adding New Node in between Node After the Previous Node
def in_bw_node(self,prev_data,value):
if prev_data is None:
print('Can not add nodes in between of empty LinkedList')
return
n=self.head
while n is not None:
if n.value==prev_data:
break
n=n.nextnode
new_node=Node(value)
new_node.nextnode=n.nextnode
n.nextnode=new_node
# Adding New Node in between Node before the Previous Node
def insert_before_node(self,prev_data,value):
if prev_data is None:
print('Can not add nodes in between of empty LinkedList')
return
p=self.head
new_node=Node(value)
while p is not None:
if p.nextnode.value==prev_data:
break
p=p.nextnode
new_node.nextnode=p.nextnode
p.nextnode=new_node
# Adding New Node in the last and last node is pointting to None
def tail_node(self,value):
node=Node(value)
if self.head is None:
self.head=node
return
crnt_node=self.head
while True:
if crnt_node.nextnode is None:
crnt_node.nextnode=node
break
crnt_node=crnt_node.nextnode
# Deleting head node(1'st Node ) of the Linked List
def del_head_node(self):
if self.head is None:
print('Can not delete Nodes from Empty Linked List')
return
crnt_node=self.head
while self.head is not None:
self.head=crnt_node.nextnode
break
crnt_node.nextnode=self.head.nextnode
# Deleting the last Node of the linked List
def del_tail_node(self):
if self.head is None:
print('Can not delete Nodes from Empty Linked List')
return
crnt_node=self.head
while True:
if crnt_node.nextnode.nextnode is None:
crnt_node.nextnode=None
break
crnt_node=crnt_node.nextnode
# Deleting the Node after given Node
def del_in_bw_node(self,value):
del_node=Node(value)
if self.head is None:
print('Can not delete Nodes from Empty Linked List')
return
crnt_node=self.head
while True:
if crnt_node.value==del_node.value:
break
prev=crnt_node
crnt_node=prev.nextnode
prev.nextnode=crnt_node.nextnode
# Method to print the Data
def print_list(self):
crnt_node=self.head
while crnt_node is not None:
print(crnt_node.value,end='->')
crnt_node=crnt_node.nextnode
print('None')
llist=LinkedList()
llist.print_list()
llist.head_node(1)
llist.print_list()
llist.tail_node(2)
llist.print_list()
llist.tail_node(5)
llist.print_list()
llist.tail_node(10)
llist.print_list()
llist.head_node(25)
llist.print_list()
llist.in_bw_node(5,7)
llist.print_list()
llist.insert_before_node(5,3)
llist.print_list()
llist.del_head_node()
llist.print_list()
llist.del_tail_node()
llist.print_list()
llist.del_in_bw_node(5)
llist.print_list()
我正在重温我之前发布的一个问题：
我很难搞清楚如何在单向链表的其他节点之间插入一个节点。在上面的解决方案中，我编写了一个额外的 getNodes 方法，将数据转换为节点并将其推送到节点之间，但它大大增加了时间复杂度。必须有一种方法可以在不使用这种自定义方法的情况下在节点之间插入，但我就是不知道怎么做。
这是我的新代码：
class Node(object):
def __init__(self, data):
self.data = data
self.nextNode = None
def __str__(self):
return str(self.data)
class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
def insert_in_between2(self, data, prev_data):
# instantiate the new node
new_node = Node(data)
# assign to head
thisval = self.head
# check each value in linked list against prev_data as long as value is not empty
prev_data2 = Node(prev_data)
while thisval is not None:
# if value is equal to prev_data
if thisval.data == prev_data2.data:
print("thisval.data == prev_data.data")
# make the new node's next point to the previous node's next
new_node.nextNode = prev_data2.nextNode
# make the previous node point to new node
prev_data2.nextNode = new_node
break
# if value is not eqaul to prev_data then assign variable to next Node
else:
thisval = thisval.nextNode
def push_from_head(self, NewVal):
new_node = Node(NewVal)
print("This is new_node: ", new_node.data)
last = self.head
print("This is last/HEAD: ", last)
if last is None:
print("Head is NONE")
self.head = new_node
print("This is self.head: ", self.head)
return
print("last.nextNode: ", last.nextNode)
while last.nextNode is not None:
print("this is last inside while loop: ", last.data)
print("last.nextNode is not NONE")
last = last.nextNode
print("This is the last last: ", last.data)
last.nextNode = new_node
print("This is last.nextNode: ", last.nextNode)
def print_nodes(self):
if self.head:
thisval = self.head
while thisval:
print("This is node: ", thisval.data)
thisval = thisval.nextNode
e1 = LinkedList()
e1.push_from_head(10)
e1.push_from_head(20)
e1.push_from_head(30)
e1.push_from_head(40)
e1.push_from_head(50)
e1.insert_in_between2(25, 20)
# print("This is the index: ", e1.getNode(1))
e1.print_nodes()
现在它打印：10、20、30、40、50 但它应该打印：10、20、25、30、40、50。
我认为问题出在 insert_in_between2 方法的这一行：
new_node.nextNode = prev_data2.nextNode
...因为这两个都打印出来 None。任何正确方向的帮助都会很棒。
您正在创建一个不属于列表的新节点：
prev_data2 = Node(prev_data)
prev_data 似乎是您正在搜索的要插入的值。
然后将新节点连接到该节点，但由于它不在列表中，因此有点孤立。你不需要那个节点。只需将您的新节点连接到您刚刚找到的节点即可：
while thisval is not None:
if thisval.data == prev_data: # you found the node before the insert
new_node.nextNode = thisval.nextNode # new node's next gos to found node's next
thisval.nextNode = new_node # found node's next goes to new node
#Linked List Program to Add and Delete Node Form Head, Tail, in Between Nodes.
class Node:
""" Node Class having the data and pointer to the next Node"""
def __init__(self,value):
self.value=value
self.nextnode=None
class LinkedList(object):
""" Linked List Class to point the value and the next nond"""
def __init__(self):
self.head=None
#Adding Node to the head of linked List
def head_node(self,value):
node=Node(value)
if self.head is None:
self.head=node
return
crnt_node=node
crnt_node.nextnode=self.head
self.head=crnt_node
# Adding New Node in between Node After the Previous Node
def in_bw_node(self,prev_data,value):
if prev_data is None:
print('Can not add nodes in between of empty LinkedList')
return
n=self.head
while n is not None:
if n.value==prev_data:
break
n=n.nextnode
new_node=Node(value)
new_node.nextnode=n.nextnode
n.nextnode=new_node
# Adding New Node in between Node before the Previous Node
def insert_before_node(self,prev_data,value):
if prev_data is None:
print('Can not add nodes in between of empty LinkedList')
return
p=self.head
new_node=Node(value)
while p is not None:
if p.nextnode.value==prev_data:
break
p=p.nextnode
new_node.nextnode=p.nextnode
p.nextnode=new_node
# Adding New Node in the last and last node is pointting to None
def tail_node(self,value):
node=Node(value)
if self.head is None:
self.head=node
return
crnt_node=self.head
while True:
if crnt_node.nextnode is None:
crnt_node.nextnode=node
break
crnt_node=crnt_node.nextnode
# Deleting head node(1'st Node ) of the Linked List
def del_head_node(self):
if self.head is None:
print('Can not delete Nodes from Empty Linked List')
return
crnt_node=self.head
while self.head is not None:
self.head=crnt_node.nextnode
break
crnt_node.nextnode=self.head.nextnode
# Deleting the last Node of the linked List
def del_tail_node(self):
if self.head is None:
print('Can not delete Nodes from Empty Linked List')
return
crnt_node=self.head
while True:
if crnt_node.nextnode.nextnode is None:
crnt_node.nextnode=None
break
crnt_node=crnt_node.nextnode
# Deleting the Node after given Node
def del_in_bw_node(self,value):
del_node=Node(value)
if self.head is None:
print('Can not delete Nodes from Empty Linked List')
return
crnt_node=self.head
while True:
if crnt_node.value==del_node.value:
break
prev=crnt_node
crnt_node=prev.nextnode
prev.nextnode=crnt_node.nextnode
# Method to print the Data
def print_list(self):
crnt_node=self.head
while crnt_node is not None:
print(crnt_node.value,end='->')
crnt_node=crnt_node.nextnode
print('None')
llist=LinkedList()
llist.print_list()
llist.head_node(1)
llist.print_list()
llist.tail_node(2)
llist.print_list()
llist.tail_node(5)
llist.print_list()
llist.tail_node(10)
llist.print_list()
llist.head_node(25)
llist.print_list()
llist.in_bw_node(5,7)
llist.print_list()
llist.insert_before_node(5,3)
llist.print_list()
llist.del_head_node()
llist.print_list()
llist.del_tail_node()
llist.print_list()
llist.del_in_bw_node(5)
llist.print_list()