Linked List Deletion

What is the time complexity of deleting the last element in the linked list?

• O(n)

• O(1)

• O(n logn)

• None of the above

Answer explanation

Deleting the last element of the linked list requires a time complexity of O(n)

What keyword can be used to perform deletion operation in linked list?

• free

• remove

• null

• erase

Answer explanation

free keyword frees up the memory allocated for the particular node and performs the deletion operation

State True/False

A node in singly linked list can be deleted in O(1) if the pointer to node is given

• True

• False

Answer explanation

A node in singly linked list can be deleted in O(n) if the pointer to node is given

State true/false

A node in singly linked list can be deleted in O(1) if the pointer to previous node is given

• True

• False

Answer explanation

A node in singly linked list can be deleted in O(1) if the pointer to previous node is given

ALGORITHM

1. Traverse link list to second last element

2. Change its next pointer to null

3. Free the memory of the last node

Consider above algorithm being applied to the linked list 1->2->3->4->5

How does the linked list look like after the operation?

• 1->2->3->4->5

• 2->3->4->5

• 1->2->3->4

• 1->3->4->5

Answer explanation

The above algorithm perform deletion at the end .So the list would look like 1->2->3->4

What operation does the following algorithm represent?

1. Store the address of the first node in a pointer

2. Move the head node to the next node

3. Dispose or free memory of the pointer node

• Deletion at the beginning

• Deletion at the middle

• Deletion at the end

• None of the above

Answer explanation

Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only. Given the representation, which of the following operation can be implemented in O(1) time?

i) Insertion at the front of the linked list

ii) Insertion at the end of the linked list

iii) Deletion of the front node of the linked list

iv) Deletion of the last node of the linked list

• I and II

• I, II and III

• I and III

• I, II and III

Answer explanation

We know the head node in the given linked list. Insertion and deletion of elements at the front of the linked list completes in O (1) time whereas for insertion and deletion at the last node requires to traverse through every node in the linked list. Suppose there are n elements in a linked list, we need to traverse through each node. Hence time complexity becomes O(n).

What does the below code snippet represent?

for (int i = 2; i < position; i++) {

If(temp->next != NULL) { Temp = temp->next; }}

Temp->next = temp->next->next;

• Deletion at the beginning

• Deletion after specific node

• Deletion at the end

• None of the above

Answer explanation

The above snippet represents deletion after specific node

Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head and tail pointer. Given the representation, which of the following operation can be implemented in O(1) time?

i) Insertion at the front of the linked list

ii) Insertion at the end of the linked list

iii) Deletion of the front node of the linked list

iv) Deletion of the last node of the linked list

• I and II

• I and III

• I,II and III

• I,II and IV

Answer explanation

It is possible to execute insertion at front and end and deletion at front using O(1) time complexity when both head and tail pointers are given

10.Consider the linked list 1->2->3->4->5->6->7

When the node 4 is deleted the pointer to address of node 5 will be contained in which of the following node?

• 2

• 3

• 5

• 6

Answer explanation

Deletion of node 4 will make node 3 carry pointer to address of node 5