What is the time complexity of adding an element of beginning of singly linked list of size n?

Introduction to Singly Linked List

Singly Linked List is a variant of Linked List which allows only forward traversal of linked lists. This is a simple form, yet it is effective for several problems such as Big Integer calculations.

Table of Contents Show

Introduction to Singly Linked List
Insert N elements in a Linked List one after other at middle position
Linked List | Set 2 (Inserting a node)

A singly linked list is made up of nodes where each node has two parts:

The first part contains the actual data of the node
The second part contains a link that points to the next node of the list that is the address of the next node.

The beginning of the node marked by a special pointer named START. The pointer points to the fist node of the list but the link part of the last node has no next node to point to.

The main difference from an array is:

Elements are not stored in contiguous memory locations.
Size of Linked List need not be known in advance. It can increase at runtime depending on number of elements dynamically without any overhead.

In Singly Linked List, only the pointer to the first node is stored. The other nodes are accessed one by one.

To get the address of ith node, we need to traverse all nodes before it because the address of ith node is stored with i-1th node and so on.

Insert N elements in a Linked List one after other at middle position

Given an array of N elements. The task is to insert the given elements at the middle position in the linked list one after another. Each insert operation should take O(1) time complexity.
Examples:

Input: arr[] = {1, 2, 3, 4, 5}
Output: 1 -> 3 -> 5 -> 4 -> 2 -> NULL
1 -> NULL
1 -> 2 -> NULL
1 -> 3 -> 2 -> NULL
1 -> 3 -> 4 -> 2 -> NULL
1 -> 3 -> 5 -> 4 -> 2 -> NULL
Input: arr[] = {5, 4, 1, 2}
Output: 5 -> 1 -> 2 -> 4 -> NULL

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: There are two cases:

Number of elements present in the list are less than 2.
Number of elements present in the list are more than 2.
- The number of elements already present are even say N then the new element is inserted in the middle position that is (N / 2) + 1.
- The number of elements already present are odd then the new element is inserted next to the current middle element that is (N / 2) + 2.

We take one additional pointer ‘middle’ which stores the address of current middle element and a counter which counts the total number of elements.
If the elements already present in the linked list are less than 2 then middle will always point to the first position and we insert the new node after the current middle.
If the elements already present in the linked list are more than 2 then we insert the new node next to the current middle and increment the counter.
If there are an odd number of elements after insertion then the middle points to the newly inserted node else there is no change in the middle pointer.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <iostream>

using namespace std;
// Node structure

struct Node {

int value;

struct Node* next;
};
// Class to represent a node
// of the linked list

class LinkedList {

private:

struct Node *head, *mid;

int count;

public:

LinkedList();

void insertAtMiddle(int);

void show();
};
LinkedList::LinkedList()
{

head = NULL;

mid = NULL;

count = 0;
}
// Function to insert a node in
// the middle of the linked list

void LinkedList::insertAtMiddle(int n)
{

struct Node* temp = new struct Node();

struct Node* temp1;

temp->next = NULL;

temp->value = n;

// If the number of elements

// already present are less than 2

if (count < 2) {

if (head == NULL) {

head = temp;

}

else {

temp1 = head;

temp1->next = temp;

}

count++;

// mid points to first element

mid = head;

}

// If the number of elements already present

// are greater than 2

else {

temp->next = mid->next;

mid->next = temp;

count++;

// If number of elements after insertion

// are odd

if (count % 2 != 0) {

// mid points to the newly

// inserted node

mid = mid->next;

}

}
}
// Function to print the nodes
// of the linked list

void LinkedList::show()
{

struct Node* temp;

temp = head;

// Initializing temp to head

// Iterating and printing till

// The end of linked list

// That is, till temp is null

while (temp != NULL) {

cout << temp->value << " -> ";

temp = temp->next;

}

cout << "NULL";

cout << endl;
}
// Driver code

int main()
{

// Elements to be inserted one after another

int arr[] = { 1, 2, 3, 4, 5 };

int n = sizeof(arr) / sizeof(arr[0]);

LinkedList L1;

// Insert the elements

for (int i = 0; i < n; i++)

L1.insertAtMiddle(arr[i]);

// Print the nodes of the linked list

L1.show();

return 0;
}

Java

// Java implementation of the approach 

class GFG
{
// Node ure 

static class Node
{ 

int value;

Node next;
}; 
// Class to represent a node 
// of the linked list 

static class LinkedList
{ 

Node head, mid;

int count;
LinkedList() 
{ 

head = null;

mid = null;

count = 0;
} 
// Function to insert a node in 
// the middle of the linked list 

void insertAtMiddle(int n)
{ 

Node temp = new Node();

Node temp1;

temp.next = null;

temp.value = n;

// If the number of elements

// already present are less than 2

if (count < 2)

{

if (head == null)

{

head = temp;

}

else

{

temp1 = head;

temp1.next = temp;

}

count++;

// mid points to first element

mid = head;

}

// If the number of elements already present

// are greater than 2

else

{

temp.next = mid.next;

mid.next = temp;

count++;

// If number of elements after insertion

// are odd

if (count % 2 != 0)

{

// mid points to the newly

// inserted node

mid = mid.next;

}

}
} 
// Function to print the nodes 
// of the linked list 

void show()
{ 

Node temp;

temp = head;

// Initializing temp to head

// Iterating and printing till

// The end of linked list

// That is, till temp is null

while (temp != null)

{

System.out.print( temp.value + " -> ");

temp = temp.next;

}

System.out.print( "null");

System.out.println();
} 
}
// Driver code 

public static void main(String args[])
{ 

// Elements to be inserted one after another

int arr[] = { 1, 2, 3, 4, 5 };

int n = arr.length;

LinkedList L1=new LinkedList();

// Insert the elements

for (int i = 0; i < n; i++)

L1.insertAtMiddle(arr[i]);

// Print the nodes of the linked list

L1.show();
}
}
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach 
# Node ure 

class Node:

def __init__(self):

self.value = 0

self.next = None
# Class to represent a node 
# of the linked list 

class LinkedList:

def __init__(self) :

self.head = None

self.mid = None

self.count = 0

# Function to insert a node in

# the middle of the linked list

def insertAtMiddle(self , n):

temp = Node()

temp1 = None

temp.next = None

temp.value = n

# If the number of elements

# already present are less than 2

if (self.count < 2):

if (self.head == None) :

self.head = temp

else:

temp1 = self.head

temp1.next = temp

self.count = self.count + 1

# mid points to first element

self.mid = self.head

# If the number of elements already present

# are greater than 2

else:

temp.next = self.mid.next

self.mid.next = temp

self.count = self.count + 1

# If number of elements after insertion

# are odd

if (self.count % 2 != 0):

# mid points to the newly

# inserted node

self.mid = self.mid.next

# Function to print the nodes

# of the linked list

def show(self):

temp = None

temp = self.head

# Initializing temp to self.head

# Iterating and printing till

# The end of linked list

# That is, till temp is None

while (temp != None) :

print( temp.value, end = " -> ")

temp = temp.next

print( "None")
# Driver code 
# Elements to be inserted one after another 

arr = [ 1, 2, 3, 4, 5]

n = len(arr)

L1 = LinkedList()
# Insert the elements 

for i in range(n):

L1.insertAtMiddle(arr[i])
# Print the nodes of the linked list 
L1.show() 
# This code is contributed by Arnab Kundu

// C# implementation of the approach 

using System;

class GFG
{
// Node ure 

public class Node
{ 

public int value;

public Node next;
}; 
// Class to represent a node 
// of the linked list 

public class LinkedList
{ 

public Node head, mid;

public int count;

public LinkedList()
{ 

head = null;

mid = null;

count = 0;
} 
// Function to insert a node in 
// the middle of the linked list 

public void insertAtMiddle(int n)
{ 

Node temp = new Node();

Node temp1;

temp.next = null;

temp.value = n;

// If the number of elements

// already present are less than 2

if (count < 2)

{

if (head == null)

{

head = temp;

}

else

{

temp1 = head;

temp1.next = temp;

}

count++;

// mid points to first element

mid = head;

}

// If the number of elements already present

// are greater than 2

else

{

temp.next = mid.next;

mid.next = temp;

count++;

// If number of elements after insertion

// are odd

if (count % 2 != 0)

{

// mid points to the newly

// inserted node

mid = mid.next;

}

}
} 
// Function to print the nodes 
// of the linked list 

public void show()
{ 

Node temp;

temp = head;

// Initializing temp to head

// Iterating and printing till

// The end of linked list

// That is, till temp is null

while (temp != null)

{

Console.Write( temp.value + " -> ");

temp = temp.next;

}

Console.Write( "null");

Console.WriteLine();
} 
}
// Driver code 

public static void Main(String []args)
{ 

// Elements to be inserted one after another

int []arr = { 1, 2, 3, 4, 5 };

int n = arr.Length;

LinkedList L1=new LinkedList();

// Insert the elements

for (int i = 0; i < n; i++)

L1.insertAtMiddle(arr[i]);

// Print the nodes of the linked list

L1.show();
}
}
// This code contributed by Rajput-Ji

Javascript

<script>

// JavaScript implementation of the approach

// Node ure

class Node {

constructor() {

this.value = 0;

this.next = null;

}

}

// Class to represent a node

// of the linked list

class LinkedList {

constructor() {

this.head = null;

this.mid = null;

this.count = 0;

}

// Function to insert a node in

// the middle of the linked list

insertAtMiddle(n) {

var temp = new Node();

var temp1;

temp.next = null;

temp.value = n;

// If the number of elements

// already present are less than 2

if (this.count < 2) {

if (this.head == null) {

this.head = temp;

} else {

temp1 = this.head;

temp1.next = temp;

}

this.count++;

// mid points to first element

this.mid = this.head;

}

// If the number of elements already present

// are greater than 2

else {

temp.next = this.mid.next;

this.mid.next = temp;

this.count++;

// If number of elements after insertion

// are odd

if (this.count % 2 != 0) {

// mid points to the newly

// inserted node

this.mid = this.mid.next;

}

}

}

// Function to print the nodes

// of the linked list

show() {

var temp;

temp = this.head;

// Initializing temp to head

// Iterating and printing till

// The end of linked list

// That is, till temp is null

while (temp != null) {

document.write(temp.value + " -> ");

temp = temp.next;

}

document.write("null");

document.write("<br>");

}

}

// Driver code

// Elements to be inserted one after another

var arr = [1, 2, 3, 4, 5];

var n = arr.length;

var L1 = new LinkedList();

// Insert the elements

for (var i = 0; i < n; i++) L1.insertAtMiddle(arr[i]);

// Print the nodes of the linked list

L1.show();

</script>

Output: 1 -> 3 -> 5 -> 4 -> 2 -> NULL

Time Complexity : O(N)
Auxiliary Space: O(1)

Article Tags :

Data Structures

Linked List

Mathematical

Practice Tags :

Data Structures

Linked List

Mathematical

Read Full Article

Linked List | Set 2 (Inserting a node)

We have introduced Linked Lists in the previous post. We also created a simple linked list with 3 nodes and discussed linked list traversal.
All programs discussed in this post consider the following representations of linked list.

C++

// A linked list node 

class Node
{ 

public:

int data;

Node *next;
}; 
// This code is contributed by rathbhupendra

// A linked list node

struct Node
{

int data;

struct Node *next;
};

Java

// Linked List Class

class LinkedList
{

Node head; // head of list

/* Node Class */

class Node

{

int data;

Node next;

// Constructor to create a new node

Node(int d) {data = d; next = null; }

}
}

Python

# Node class

class Node:

# Function to initialize the node object

def __init__(self, data):

self.data = data # Assign data

self.next = None # Initialize next as null
# Linked List class

class LinkedList:

# Function to initialize the Linked List object

def __init__(self):

self.head = None

/* Linked list Node*/

public class Node
{

public int data;

public Node next;

public Node(int d) {data = d; next = null; }
}

Javascript

<script>
// Linked List Class

var head; // head of list

/* Node Class */

class Node {

// Constructor to create a new node

constructor(d) {

this.data = d;

this.next = null;

}

}
// This code is contributed by todaysgaurav 
</script>

In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list.