Insertion of an element at the middle of a linked list requires the modification of how many pointers?

Answer (Detailed Solution Below)

Option 3 : 2 pointers

Free

20 Qs. 20 Marks 15 Mins

Circular linked list:
In singly linked lists and doubly linked lists, the end of lists is indicated with a NULL value. But circular linked lists do not have ends. In circular linked lists, each node has a successor, and the last node points to the first node instead of NULL.

Example

Let x be a variable pointer and head.

Head is the pointer of the circular linked list.

Now to insert a new record (node) y, we have to loop through the linked list from the head to the last node like this pseudocode below.

x=head

while(x->next!=head)

{

x=x->next;

}

After finishing the loop x is now the last node and we will append the list. y is the next node of x Then the next of y will have to point to the head since the linked list is circular. The pseudocode for this task is below.

x->next=y;

y->next=head;

So There needs modification of two pointers.

So the correct answer is Option 3

India’s #1 Learning Platform

Start Complete Exam Preparation

Video Lessons & PDF Notes

Get Started for Free Download App

Trusted by 2,99,79,859+ Students

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.

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

def __init__(self, data):

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

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.

Add a node at the front: (4 steps process)
The new node is always added before the head of the given Linked List. And newly added node becomes the new head of the Linked List. For example, if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. Let us call the function that adds at the front of the list is push(). The push() must receive a pointer to the head pointer, because push must change the head pointer to point to the new node (See this)

Following are the 4 steps to add a node at the front.

void push(Node** head_ref, int new_data)

Node* new_node = new Node();

new_node->data = new_data;

new_node->next = (*head_ref);

void push(struct Node** head_ref, int new_data)

struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->next = (*head_ref);

public void push(int new_data)

Node new_node = new Node(new_data);

def push(self, new_data):

new_node = Node(new_data)

new_node.next = self.head

public void push(int new_data)

Node new_node = new Node(new_data);

var new_node = new Node(new_data);

We have a pointer to the head and we can directly attach a node and change the pointer. So the Time complexity of inserting a node at head position is O(1) as it does a constant amount of work.

Add a node after a given node: (5 steps process) We are given a pointer to a node, and the new node is inserted after the given node.

void insertAfter(Node* prev_node, int new_data)

cout << "The given previous node cannot be NULL";

Node* new_node = new Node();

new_node->data = new_data;

new_node->next = prev_node->next;

prev_node->next = new_node;

void insertAfter(struct Node* prev_node, int new_data)

printf("the given previous node cannot be NULL");

= (struct Node*)malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->next = prev_node->next;

prev_node->next = new_node;

public void insertAfter(Node prev_node, int new_data)

"The given previous node cannot be null");

Node new_node = new Node(new_data);

new_node.next = prev_node.next;

prev_node.next = new_node;

def insertAfter(self, prev_node, new_data):

print("The given previous node must inLinkedList.")

new_node = Node(new_data)

new_node.next = prev_node.next

prev_node.next = new_node

public void insertAfter(Node prev_node, int new_data)

Console.WriteLine("The given previous node"

Node new_node = new Node(new_data);

new_node.next = prev_node.next;

prev_node.next = new_node;

function insertAfter(prev_node , new_data)

document.write("The given previous node cannot be null");

var new_node = new Node(new_data);

new_node.next = prev_node.next;

prev_node.next = new_node;

Time complexity of insertAfter() is O(n) as it depends on n where n is the size of the linked list

Space complexity: O(1) since using constant space to modify pointers

Add a node at the end: (6 steps process) The new node is always added after the last node of the given Linked List. For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30. Since a Linked List is typically represented by the head of it, we have to traverse the list till the end and then change the next to last node to a new node.

Following are the 6 steps to add node at the end.

void append(Node** head_ref, int new_data)

Node* new_node = new Node();

new_node->data = new_data;

while (last->next != NULL)

void append(struct Node** head_ref, int new_data)

struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

struct Node *last = *head_ref;

new_node->data = new_data;

while (last->next != NULL)

public void append(int new_data)

Node new_node = new Node(new_data);

head = new Node(new_data);

while (last.next != null)

def append(self, new_data):

new_node = Node(new_data)

public void append(int new_data)

Node new_node = new Node(new_data);

head = new Node(new_data);

while (last.next != null)

function append(new_data)

var new_node = new Node(new_data);

head = new Node(new_data);

while (last.next != null)

Time complexity of append is O(n) where n is the number of nodes in the linked list. Since there is a loop from head to end, the function does O(n) work.
This method can also be optimized to work in O(1) by keeping an extra pointer to the tail of the linked list/

Following is a complete program that uses all of the above methods to create a linked list.

 
void push(Node** head_ref, int new_data) 

    Node* new_node = new Node();

    new_node->data = new_data; 

    new_node->next = (*head_ref); 

void insertAfter(Node* prev_node, int new_data) 

        cout<<"The given previous node cannot be NULL"; 

    Node* new_node = new Node();

    new_node->data = new_data; 

    new_node->next = prev_node->next; 

    prev_node->next = new_node; 

void append(Node** head_ref, int new_data) 

    Node* new_node = new Node();

    new_node->data = new_data; 

    while (last->next != NULL)

void printList(Node *node) 

    insertAfter(head->next, 8); 

    cout<<"Created Linked list is: ";

 
void push(struct Node** head_ref, int new_data)

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;

    new_node->next = (*head_ref);

void insertAfter(struct Node* prev_node, int new_data)

      printf("the given previous node cannot be NULL");

    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;

    new_node->next = prev_node->next;

    prev_node->next = new_node;

void append(struct Node** head_ref, int new_data)

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    struct Node *last = *head_ref; 

    new_node->data  = new_data;

    while (last->next != NULL)

void printList(struct Node *node)

     printf(" %d ", node->data);

  struct Node* head = NULL;

  insertAfter(head->next, 8);

  printf("\n Created Linked list is: ");

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

    public void push(int new_data)

        Node new_node = new Node(new_data);

    public void insertAfter(Node prev_node, int new_data)

            System.out.println("The given previous node cannot be null");

        Node new_node = new Node(new_data);

        new_node.next = prev_node.next;

        prev_node.next = new_node;

    public void append(int new_data)

        Node new_node = new Node(new_data);

            head = new Node(new_data);

        while (last.next != null)

            System.out.print(tnode.data+" ");

    public static void main(String[] args)

        LinkedList llist = new LinkedList();

        llist.insertAfter(llist.head.next, 8);

        System.out.println("\nCreated Linked list is: ");

def __init__(self, data):

def push(self, new_data):

new_node = Node(new_data)

new_node.next = self.head

def insertAfter(self, prev_node, new_data):

print("The given previous node must inLinkedList.")

new_node = Node(new_data)

new_node.next = prev_node.next

prev_node.next = new_node

def append(self, new_data):

new_node = Node(new_data)

llist.insertAfter(llist.head.next, 8)

print('Created linked list is: ')

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

    public void push(int new_data)

        Node new_node = new Node(new_data);

    public void insertAfter(Node prev_node, int new_data)

            Console.WriteLine("The given previous" + 

        Node new_node = new Node(new_data);

        new_node.next = prev_node.next;

        prev_node.next = new_node;

    public void append(int new_data)

        Node new_node = new Node(new_data);

            head = new Node(new_data);

        while (last.next != null)

            Console.Write(tnode.data + " ");

    public static void Main(String[] args)

        llist.insertAfter(llist.head.next, 8);

        Console.Write("Created Linked list is: ");

 
     function push(new_data) {

        var new_node = new Node(new_data);

     function insertAfter(prev_node , new_data) {

            "The given previous node cannot be null"

         var new_node = new Node(new_data);

        new_node.next = prev_node.next;

        prev_node.next = new_node;

     function append(new_data) {

         var new_node = new Node(new_data);

            head = new Node(new_data);

        while (last.next != null)

            document.write(tnode.data + " ");

        insertAfter(head.next, 8);

        document.write("\nCreated Linked list is: ");

Output:

Created Linked list is: 1 7 8 6 4

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

Alternate method by using constructor call

However there is another method which uses constructor call inside the node class in order to minimize the memory allocation work. It also minimizes the number of lines of code.

 
void insertathead(node*& head, int val)

void insertafter(node* head, int key, int val)

    while (temp->data != key) {

void insertattail(node*& head, int val)

    while (temp->next != NULL) {

        cout << temp->data << " -> ";

    cout << "After insertion at head: ";

    cout << "After insertion at tail: ";

    cout << "After insertion at a given position: ";

Output After insertion at head: 2 -> 1 -> NULL After insertion at tail: 2 -> 1 -> 4 -> 5 -> NULL After insertion at a given position: 2 -> 1 -> 2 -> 4 -> 5 -> 6 -> NULL

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

You may like to try Practice MCQ Questions on Linked List Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :

Practice Tags :