How to Insert a New Node at the beginning of a Linked List in Python

By
Editorial Team
-
0
176

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.

Leave a Reply