Question

You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?

(a) Delete the first element

(b) Insert a new element as a first element

(c) Delete the last element of the list

(d) Add a new element at the end of the list

This intriguing question originated from Singly Linked List Operations topic in section Abstract Data Types of Data Structures & Algorithms I

The question was posed to me during an online exam.

Answer 1

Right choice is (c) Delete the last element of the list

Explanation: Deletion of the first element of the list is done in O (1) time by deleting memory and changing the first pointer.

Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data and points to the head of the given linked list. The head pointer was changed to a newly created node.

Deletion of the last element requires a pointer to the previous node of last, which can only be obtained by traversing the list. This requires the length of the linked list.

Adding a new element at the end of the list can be done in O (1) by changing the pointer of the last node to the newly created node and last is changed to a newly created node.