Insert Node at beginning of Linked List

Problem Statement: For a given Singly LinkedList, insert a node at the beginning of the linked list.

Examples:

Example 1:

Input: List = 10->20->30->40->null, Node = 0
Output: 0->10->20->30->40->null
Explanation: Inserted the given node at the beginning of the linked list.

Example 2:
Input: List = 100->200->300->null, Node =700
Output: 700->100->200->300->null
Explanation: Inserted the given node at the beginning of the linked list.


Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

Inserting a Node at the beginning of LinkedList is 3 step Process

Step 1: First create a node with a value that is to be inserted at the beginning of LinkedList.

Step 2: Point the next of the newly created Node to the head of the LinkedList.

Step 3: As the node is inserted at the beginning of LinkedList, this is the first Node in LinkedList. So point the head of the LinkedList to the newly created Node.

Visual Representation of the 3 Steps involved in inserting a Node at beginning of LinkedList

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

class ListNode {
  public:
    int val;
  ListNode * next;
  ListNode(int x) {
    val = x;
    next = NULL;
  }
};

void PrintList(ListNode * head) // Function to print the LinkedList
{
  ListNode * curr = head;
  for (; curr != NULL; curr = curr -> next)
    cout << curr -> val << "-->";
  cout << "null" << endl;
}

ListNode * InsertatFirst(int value, ListNode * head) {

  // Step1 : creating a new Node with the given val
  ListNode * newnode = new ListNode(value);

  // Step2 : Making next of newly created Node to point the head of LinkedList
  newnode -> next = head;

  // Making the newly created Node as head
  head = newnode;
  return head;
}

int main() {
  ListNode * head = NULL; // head of the LinkedList
  head = InsertatFirst(40, head);
  head = InsertatFirst(30, head);
  head = InsertatFirst(20, head);
  head = InsertatFirst(10, head);
  cout << "LinkedList before inserting 0 at beginning : " << endl;
  PrintList(head);
  head = InsertatFirst(0, head);
  cout << "LinkedList after inserting 0 at beginning : " << endl;
  PrintList(head);
  return 0;
}

Output:

LinkedList before inserting 0 at beginning :
10–>20–>30–>40–>null
LinkedList after inserting 0 at beginning :
0–>10–>20–>30–>40–>null

Time Complexity:  O(1) Because we are just Manipulating the links, which is a constant operation.

Space Complexity: O(1) We are not using any extra space.

Java Code

import java.util.*;

class ListNode {

  int val;
  ListNode next;
  ListNode(int x) {
    val = x;
    next = null;
  }
}

class TUF {
  static void PrintList(ListNode head) // Function to print the LinkedList
  {
    ListNode curr = head;
    for (; curr != null; curr = curr.next)
      System.out.print(curr.val + "-->");
    System.out.println("null");
  }

  static ListNode InsertatFirst(int value, ListNode head) {

    // Step1 : creating a new Node with the given val
    ListNode newnode = new ListNode(value);

    // Step2 : Making next of newly created Node to point the head of LinkedList
    newnode.next = head;

    // Making the newly created Node as head
    head = newnode;
    return head;
  }

  public static void main(String args[]) {
    ListNode head = null; // head of the LinkedList
    head = InsertatFirst(40, head);
    head = InsertatFirst(30, head);
    head = InsertatFirst(20, head);
    head = InsertatFirst(10, head);
    System.out.println("LinkedList before inserting 0 at beginning : ");
    PrintList(head);
    head = InsertatFirst(0, head);
    System.out.println("LinkedList after inserting 0 at beginning : ");
    PrintList(head);
  }
}

Output:

LinkedList before inserting 0 at beginning :
10–>20–>30–>40–>null
LinkedList after inserting 0 at beginning :
0–>10–>20–>30–>40–>null

Time Complexity:  O(1) Because we are just Manipulating the links, which is a constant operation.

Space Complexity: O(1) We are not using any extra space.

Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article