linked list operations

[techietone]

i hope till now everybody is familiar with these linked list
operations:

1)creation
2)traversing
3)insert a node in front , back ,middle
4)delete a node in front , back ,middle
5)search for a particular data in linked list


Now here is one interesting question :

Assume that any n-bit positive integer x is stored as a linked list of
bits so that the first element of the list
is the least significant bit. For example, x =14 (1110) is stored as
the linked list 0, 1, 1, 1 of size n 4.
like 0->1->1->1
For this data structure, the operation that replaces x by x/8.
can be done in:

(A) constant time
(B) log n time
(C) n (linear time)
(D) n log n time
(E) n^2 time


You can ignore this question if u want,

[vishal]

(C) n (linear time)

Explanation:
===================
Correct me if i am wrong....

Assumptions:
1.Singly linked list
2.u have to convert x to y where y=x/8....which means three times
right shift.....

So we have to delete last three nodes of list.....so its always
removing last three nodes.....
So we need to traverse the entire list which is O(n)...(use 2 pointers
and start the second after first pointer travels 3 nodes) and delete
list from second ptr....

node *ptr1,*ptr2;
ptr1=ptr2=head;
while(i<3 && ptr->next != NULL)
{
ptr1=ptr->next;
}
if(i != 3) return 0;
while(ptr1->next != NULL)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
//Set the last but third node's next to NULL
ptr2->next = NULL;
return head;
}

Doubly linked list:
If u have the ptr to last node its O(1)...always three operations....

[Vishwas B Sharma]

For the question you sent the answer is Constant time right ??? Cauz all that we need to do is 

head = head->link->link->link;

But here its always integer division that happens or the right shift operation that happens. Pythons "//" and not "/".

[pritesh kumar]

hi

For the first question answer is constant time ,

For the second question its single linked list .

[Avinash Ega]

Vishal,

your answer will be right if the most significant bit is at the head.

here, the answer is head=head->next->next->next;

--

Thanks & Regards,

Avinash E.

Phone: +919916193163

http://www.timesofcommerce.com

[techietone]

in a singly linked list also a tail pointer can be mainatained and can
be operated in fifo manner .
Now we come to 3rd point , where i found it a little confusing . but
assuming that in a doubly linked list there are 2 pointers to be
maintained
i came to conclusion that answer should be singly linked list

you can provider ur views related to this

[vishal]

Sorry for my confusion with head......:)