206 views

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:

S1: Delete kth element in linked list.

S2: 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)
in DS | 206 views
0
is ans. A????
0
Think A

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)

by Boss (10.9k points)
0
@VS

1. How did you calculate last from the given formulae?

(P+x)%n, here n and x both will be number of elements.Now P is base address of array or is  it index 0?and how did you calculate last from this?From you example P=0,size of linked is x=5,and n=5.

0

See,@rahul ,

In question

first=P

last=(P+x) mod n //I think this is an ERROR  Why?

Lets say we have an array :

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

Now,

first=P = 0

last=(P+x) mod n = (0+4) mod 5 =4 (NOT POSSIBLE)

as question says :

two variables first and last are used to point the first and last element of the list present in array respectively

Here,in my answer I just considered that first points to first element and last points to the last element of the linked list as the question setter intended us to assume.

+1
I think it can be done in O(1)

From the starting you were right swap the first and last pointers.. After that you can traverse from higher to lower index will give you linked list in reverse order.

Nd in the solution of made easy i think they have done the same see the sign p-x
0

@vamp_vaibhav

But, how we update first and last pointers has to be fixed Right?

What you are saying means we have changed the way we were updating the first and last pointers!

0
I m just suggesting that.. Since we have circular array instead of linked list we don't have to worry about all the internal pointers we can access elements just by decrementing x from last which will give you value in reverse order same as linked list in reverse.
0
But, the question is not about accessing the elements in reverse order :) It is about reversal of linked list .
0
I am absolutely getting your point.. But here we have to implement linked list using circular array.. it make difference isn't?? In circular array ending and starting can be anything.. So if we consider that array during implementation do we need to reverse the links..no we just have to produce output such that it is reverse of linked list.. Am I going wrong somewhere in understanding question?
+2
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 :)
+1
Hmmm you are right :)
+2

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

+1 vote