Linked List

Question

A linked list of length at most n is maintained in circular array C[0:n-1], clockwise or anticlock wise; two variables head and last are used to point to first and last element of the list respectively, for instance if linked list is of size x and if it is maintained in clock wise manner and head =p, then last = (p+x)mod n, then the best way for
I: deleting kth element in the linked list
II: reversing the elements of linked list can be done in

1.   O(1), O(1) time
2.   O(1), O(n) time
3.   O(n), O(1) time
4.   O(n), O(n) time

Answer 1

the kth element can be found by k=(p+k)mod n delete it and keep the pointer of the prev to the next----it is done in O(1)

to reverse the elements the head and tail of the previous list are swapped and they are accessed in anti clockwise order this can be done in O(1) time as we know the position of head and tail

Comments

i think after deleting element we need to rearrange elements ...

suppose 0 to 10 elements are there that is 0 to n-1 now circular array is full and u deleted 5th element and u want to insert new element , how to do it within constant time??

---

i gave for only deletion...for re arranging yes we should rearrange as they are implememted in a array so they must be shifted

---

Please explain correct answer to this?

Answer 2

S1: deletion operation= going  to the kth element(O(1)) -> deleting that element(O(1)) ->shift the elements(O(n))   total=O(n)

shifting is necessary in the deletion step otherwise free space will be created in between linked list

S2: just interchange the pointers and traverse from hgher index to lower index   O(1)

Comments

you can reset the value when the pointer reaches its extreme. If first pointer traverses to the beginning(first element) then you simply reset it to point to last element .

---

That is fine.I think you are suggesting something i ma not able to get,anyhow these both are constant operations.That is fine that pointer can reach to extreme then we will reset it.What i am asking that pointer say first having tow behaviour,it can goto left or to right depending on reverse performed or not.

So how will you know in program that you need to go left or not?Whether we will do front++ or front-- how u know?

---

in deletion, cant we just replace the element to be deleted by the last element, and decrement last by1??

it will take O(1) time.??