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

#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()

Answer 2

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