I'm revisiting a question I posted some time ago posted here: LinkedList - Insert Between Nodes not Inserting
I'm having a hard time figuring out how to insert a node in between other nodes in a singly linked list. In the solution above I wrote an additional getNodes method that turns data into a node and pushes it in between the nodes but it greatly increases the time complexity. There has to be a way to insert in between nodes without using this custom method, but I just cannot figure out how.
Here is my new code:
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()
Right now it prints: 10, 20, 30, 40, 50 but it's supposed to print: 10, 20, 25, 30, 40, 50.
I think the problem is in this line in the insert_in_between2 method:
new_node.nextNode = prev_data2.nextNode
...because both of these are printing out None. Any help in the right direction would be great.
LinkedList
but anyway: Ininsert_in_between2
you create for the previous data a new nodeprev_data2
and use itsnextNode
which of course isNone
for a fresh node. Instead find the already linked node havingprev_data
and use that. – Michael Butscher Dec 25 '18 at 2:47