edited by
15,848 views
4 votes
4 votes

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
edited by

7 Answers

Best answer
16 votes
16 votes

     A. Delete the first element of the list

        Pointer F will be set to the next node, so it does not depend on the length of the 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 the length of the 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 the 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 the length of the linked list. 

   D. Add an element at the end of the list

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

edited by
7 votes
7 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)
3 votes
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
Answer:

Related questions

4 votes
4 votes
5 answers
1
go_editor asked Jul 1, 2016
5,929 views
Consider the following binary search tree T given below: Which node contains the fourth smallest element in T?QVWX
9 votes
9 votes
9 answers
2
ajit asked Sep 23, 2015
14,496 views
How many different trees are there with four nodes $\text{A, B, C}$ and $\text{D}?$$30$$60$$90$$120$
5 votes
5 votes
5 answers
3
5 votes
5 votes
2 answers
4