How to Insert a Node between another node in a Linked List?

Question

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.

Answer 1

You are creating a new node that isn't part of the list with the line:

prev_data2 = Node(prev_data)

prev_data seems to be the value you're searching for that you want to insert in from of.

Then you connect your new node to that, but since it's not part of the list, it's kind of orphaned. You don't need that node. Just connect your new node to the one you just found:

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