GATEBOOK exam

Question

consider a linked list of the form

Where F is pointer to the first element in the list and L is a pointer to the last element in the list.

The time of which of the following operations depends on the length of the list?

A) Delete the last element of the list

B) Delete the first element of the list

C) Add an element after the last element of the list

D) Add an element before first element

Answer 1

A)O(length) Delete the last element.

Becasue we have no other way in O(1) to move L pointer to the second last and delete the last element. What we can do,

• Assign an extra pointer in the first position (say P)
• Forward P towards the end of list and.
• Stop at 2nd last. (how ? just check P->next->next = NULL ).
• Delete Last node and assign P to L.
• => O(n) => depends on the length of the linked list.

Comments

option C) should also depend on the lenght of the list right?

---

No. you have L pointer. create one node and assign L->next = new Node. and then L = new Node.

---

in case of deletion if we point L to the second last and delete the last node then can't we do it in O(1) time?

---

How you are supposed to go from L to second last ?