How to Insert a Node at a Specific Position in a Linked List
Understand the Problem
We are given a function called insertNodeAtPosition, which has three parameters, head, data, and position.
Our head is a SinglyLinkedListNode [class] pointer to the head of the list, our data is an integer value to insert as data in a new node which we will create, and the position is a zero based index position to where we should insert our new node.
head: pointer to the head of the listdata: integer value of our new node [1]
position: a zero based index position [2]
In order to insert a Node at a specific position in the singly linked list, we must create a new node with our data parameter, insert it at the position we were given, and return the head node.
We must return a reference to the head node of our finished list.
Plan
We know that our first step will have to be to create a new node in order to have one to insert. Taking a look at our SinglyLinkedListNode class, we can see that it is expecting data to be passed in.
class SinglyLinkedListNode:def __init__[self, node_data]:
self.data = node_data
self.next = None
We can create a new node in our insertNodeAtPosition function definition by setting new to SinglyLinkedListNode[data].
We know that our position is index value 2, so well need to set a pointer to the head in order to traverse through the list from the very beginning, and also set a counter in order to move our pointer through the list node by node, until we reach our given position.
pointer = headcounter = 1
We will need to traverse through the list in order reach our position, starting with the head. Since our pointer is already set to the head, we can use a while loop that will traverse through the list until pointer.next is at our given position. We do this while pointer.next is not None.
while pointer.next is not None:We will traverse through the list position by position, with our pointer, until we are at our given position, setting counter to counter + 1.
pointer = pointer.next
If pointer.next is finally at our given position, where our counter would be equal to our position of 2, we would set new.next to point to pointer.next.
Then we would set our pointer.next to our new node, and break.
# new.next will point to pointer.next
new.next = pointer.next
# and our pointer.next will be equal to our new node
pointer.next = new
break
Execute
# For our reference:# SinglyLinkedListNode:# int data
# SinglyLinkedListNode next
#
#def insertNodeAtPosition[head, data, position]: # create a new node
new = SinglyLinkedListNode[data]
# set a pointer to head in case our initial position is not 0
pointer = head
# set our counter so we can traverse through SLL
counter = 1
while pointer.next is not None:
# and if our counter is equal to the position given
if counter == position:
# our new node will point to pointer.next
new.next = pointer.next
# and our pointer.next will be equal to our new node
pointer.next = new
break
# we traverse the list one position at a time until
# counter == position
counter += 1
pointer = pointer.next
# we return the head as requested
return head
Bonus
In the case where our given position is zero, or if we were asked to insert a new node at the beginning of the list, we would set our new node pointer to the head node.
Then we need to set the head to our new node, and return it.
# our new node will point to the head
new.next = head
# now head will point to the new node
head = new
# we then return head as requested
return head
The execution code with both test cases would be:
# For our reference:# SinglyLinkedListNode:# int data
# SinglyLinkedListNode next
#
#def insertNodeAtPosition[head, data, position]:
# create a new node
new = SinglyLinkedListNode[data]
# set a pointer to head in case our initial position is not 0
pointer = head
# set our counter so we can traverse through SLL
counter = 1
# if our given position is 0
if position == 0:
# our new node will point to the head
new.next = head
# now head will point to the new node
head = new
# we then return head as requested
return head
# while the next node away from the head node is not None
while pointer.next is not None:
# and if our counter is equal to the position given
if counter == position:
# our new node will point to pointer.next
new.next = pointer.next
# and our pointer.next will be equal to our new node
pointer.next = new
break
# we traverse the list one position at a time until counter
# == position
counter += 1
pointer = pointer.next
# we return the head as requested
return head