MADE EASY TEST SERIES

Question

Consider a linked list of length n is implemented using a circular array P[0, n – 1], two variables first and last are used to point the first and last element of the list present in array respectively i.e., first = P and last = (P + x) mod n, where x is the size of linked list.

Consider the following operations:

S₁: Delete k^th element in linked list.

S₂: Reverse the elements of linked list.

Which of the following represent the time complexity of above two operations respectively?

• O(n), O(n)
• O(n), O(1)
• O(1), O(1)
• O(1), O(n)

Comments

is ans. A????

---

Think A

Answer 1

Solution by made easy.

But in S2 I feel it cannot be done in constant time.

Why?

Lets say we have an array :

0	1	2	3	4
a (first)	b	c	d	e (last)

Now, first=0 and last=4;

Now if we reverse say first=4 and last=0

0	1	2	3	4
a (last)	b	c	d	e (first)

Normally,

Deletion : first=(first+1) mod n

Insertion: last=(last+1) mod n

Now, if we delete from above, We get : e

and first=(4+1)mod 5=0

Next delete gives output a[first]=a[0]=a (WRONG)

If linked list is reversed :

e (first)

d

c

b

a (last)

First Delete output : e

Second Delete output : d

So, I feel just swaping first and last if not enough.

So,I think we can do like :

1)Keep a ptr to first node say f and a ptr to last node say l;

2)Swap contents of f and l;

3)f++ and l--

4)Repeat till f==l or f==l-1

So, time complexity =O(n)

Comments

I think you are right to a certain extent :)

What I mean that if we do not consider how the Insertion and Deletion are implemented in the original linked list, then you are right.

Then, what could be done is just swap first and last  & also change the way Insertion and Deletion code is implemented.

I think question is ambiguous Better we don't waste our time on such questions :)

---

Hmmm you are right :)

---

@vamp_vaibhav  is correct. 

@Vs ,you should not bothered how we will delete the element and insert.We can keep track that whether linked list is from left to right (start to end) or from right to traverse,Based upon this we can adjust insertion and deletion.It should be 0(1)