Introduction
In this article, we will discuss how to insert a new node at the beginning of a linked list. We will provide a step-by-step guide and examples to help you understand the process. Additionally, we will include a code snippet in Python to demonstrate the implementation.
Problem Statement
Given a linked list and an integer value val, the task is to insert a new node with the value val at the beginning (before the head) of the list. The function should return the updated linked list.
Example 1:
Input Format: 0->1->2, val = 5
Result: 5->0->1->2
Explanation: We need to insert the value 5 before the head of the given linked list.
Example 2:
Input Format: 12->5->8->7, val = 100
Result: 100->12->5->8->7
Explanation: We need to insert the value 100 before the head of the linked list.
Approach
To insert a new node with a value before the head of the list, follow these steps:
1. Create a new node with the given value val and point it to the current head of the linked list.
2. Update the head of the linked list to the newly created node.
Code Implementation
Here is the code snippet in Python to insert a new node at the beginning of a linked list:
class Node:
def __init__(self, value):
self.value = value
self.next = None
def insertAtBeginning(head, val):
new_node = Node(val)
new_node.next = head
head = new_node
return head
# Driver code
def printList(head):
curr = head
while curr:
print(curr.value, end=" ")
curr = curr.next
# Example 1
head = Node(0)
head.next = Node(1)
head.next.next = Node(2)
val = 5
print("Original Linked List:")
printList(head)
head = insertAtBeginning(head, val)
print("\nUpdated Linked List after inserting", val, "at the beginning:")
printList(head)
# Example 2
head = Node(12)
head.next = Node(5)
head.next.next = Node(8)
head.next.next.next = Node(7)
val = 100
print("\nOriginal Linked List:")
printList(head)
head = insertAtBeginning(head, val)
print("\nUpdated Linked List after inserting", val, "at the beginning:")
printList(head)
Output
The output for both examples will be:
Original Linked List:
0 1 2
Updated Linked List after inserting 5 at the beginning:
5 0 1 2
Original Linked List:
12 5 8 7
Updated Linked List after inserting 100 at the beginning:
100 12 5 8 7
Time and Space Complexity Analysis
The time complexity for inserting the new head of the linked list is O(1), as it involves only a few operations. The time complexity for printing the linked list is O(N), where N is the number of elements in the list, as we need to traverse the entire list. The space complexity is O(1) because we have not used any extra space.
Conclusion
In this article, we discussed how to insert a new node at the beginning of a linked list. We provided a step-by-step approach, along with examples and a Python code implementation. By following these guidelines, you should now be able to insert a new node at the beginning of a linked list efficiently.
