The Gateway to Computer Science Excellence
+3 votes
2.9k views

Consider a single linked list where F and L are pointers to the first and last elements respectively of the linked list. The time for performing which of the given operations depends on the length of the linked list?

  1. Delete the first element of the list
  2. Interchange the first two elements of the list
  3. Delete the last element of the list
  4. Add an element at the end of the list
in DS by Veteran (105k points) | 2.9k views

4 Answers

+15 votes
Best answer

     A. Delete the first element of the list

        Pointer F will be set to next node, so does not depends on length of linked list. 

    B.Interchange the first two elements of the list.

      Again this can be performed using a temp node and does not depends on length of linked list. 

   C. Delete the last element of the list

       In this we need to get the address of the node just before the last node, because let address of node before last node is (1000) then we need to set this address to (1000)->next=NULL. So calculating this address we need to linear search the linked list and so it  depends on length of linked list. 

   D.Add an element at the end of the list

Here , we know the address of last node due pointer L.So just do L->next=new node.So does not depends on length of linked list. .

by Active (2.8k points)
selected by
0
what does they mean by saying element ,? does it mean node itself or value stored inside the node ?
0
here element doesnot specify anything unless u read in options ,and in options it means the node....
+6 votes

Answer : Delete the last element of the list

by Boss (45.4k points)
+6 votes

Time complexity for the following operations on Singly Linked Lists of n nodes:

  • Add a new node to the beginning of list: O(1)
  • Add a new node to the end: O(n)
  • Add a new node after k'th node: O(n)
  • Search a node with a given data: O(n)
  • Add a new node after a node with a given data: O(n)
  • Add a new node before a node with a given data: O(n)
  • Traverse all nodes: O(n)
  • Delete a node from the beginning: O(1)
  • Delete a node from the end: O(n)
  • Delete a node with a given data: O(n)
  • Delete the k'th node: O(n)
  • Modify the data of all nodes in a linked list: O(n)

Time complexity for the following operations on Doubly Linked Lists of n nodes:

  • Add a new node to the beginning of list: O(1)
  • Add a new node to the end: O(n)
  • Add a new node after k'th node: O(n)
  • Search a node with a given data: O(n)
  • Add a new node after a node with a given data: O(n)
  • Add a new node before a node with a given data: O(n)
  • Traverse all nodes: O(n)
  • Delete a node from the beginning: O(1)
  • Delete a node from the end: O(n)
  • Delete a node with a given data: O(n)
  • Delete the k'th node: O(n)
  • Modify the data of all nodes in a linked list: O(n)

Time complexity for the following operations on Circular Singly Linked Lists of n nodes:

  • Add a new node to the beginning of list: O(n)
  • Add a new node to the end: O(n)
  • Add a new node after k'th node: O(n)
  • Search a node with a given data: O(n)
  • Add a new node after a node with a given data: O(n)
  • Add a new node before a node with a given data: O(n)
  • Traverse all nodes: O(n)
  • Delete a node from the beginning: O(n)
  • Delete a node from the end: O(n)
  • Delete a node with a given data: O(n)
  • Delete the k'th node: O(n)
  • Modify the data of all nodes in a linked list: O(n)

Time complexity for the following operations on Circular Doubly Linked Lists of n nodes:

  • Add a new node to the beginning of list: O(1)
  • Add a new node to the end: O(1)
  • Add a new node after k'th node: O(n)
  • Search a node with a given data: O(n)
  • Add a new node after a node with a given data: O(n)
  • Add a new node before a node with a given data: O(n)
  • Traverse all nodes: O(n)
  • Delete a node from the beginning: O(1)
  • Delete a node from the end: O(1)
  • Delete a node with a given data: O(n)
  • Delete the k'th node: O(n)
  • Modify the data of all nodes in a linked list: O(n)
by Loyal (9.9k points)
+3 votes
Answer should be (C) because for deletion in linked list we have to maintain previous pointer and this is a singly linked list so we have to traverse the length
by Junior (945 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,370 answers
198,506 comments
105,272 users