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 | 2.9k views

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....

Answer : Delete the last element of the list

by Boss (45.4k points)

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)
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)