Middle of a link list

[ravi]

Can any body help in finding the middle element of a link list in an
effective manner

i know the simple solution of using two pointers and increment one
pointer by one and second by two.

but i want a effective algo both in terms of memory and time

[gw7rib]

On 21 Jul, 07:23, ravi <dceravigu...@g mail.comwrote:

Can any body help in finding the middle element of a link list in an
effective manner

i know the simple solution of using two pointers and increment one
pointer by one and second by two.

but i want a effective algo both in terms of memory and time

If the structure is simply a linked list, there is no quicker way to
locate the middle element than by starting at one end and moving along
one element at a time. If the structure is a doubly linked list you
could improve on the method you have suggested slightly by starting
one pointer at the front, one at the end, and seeing where they meet -
that way you only traverse the list once instead of one and a half
times.

Hope that helps.
Paul.

[ravi]

On Jul 22, 4:34 pm, [e-mail] wrote:

On 21 Jul, 07:23, ravi <dceravigu...@g mail.comwrote:

Can any body help in finding the middle element of a link list in an
effective manner

i know the simple solution of using two pointers and increment one
pointer by one and second by two.

but i want a effective algo both in terms of memory and time

If the structure is simply a linked list, there is no quicker way to
locate the middle element than by starting at one end and moving along
one element at a time. If the structure is a doubly linked list you
could improve on the method you have suggested slightly by starting
one pointer at the front, one at the end, and seeing where they meet -
that way you only traverse the list once instead of one and a half
times.

Hope that helps.
Paul.

But how i get address of the last element of the doubly link list

for eg. i am using

struct node
{
int data;
node* next;
node *previous;
};

[pete]

ravi wrote:

>
On Jul 22, 4:34 pm, [e-mail] wrote:

On 21 Jul, 07:23, ravi <dceravigu...@g mail.comwrote:

If the structure is a doubly linked list you
could improve on the method you have suggested slightly by starting
one pointer at the front, one at the end,
and seeing where they meet -
that way you only traverse the list once instead of one and a half
times.

But how i get address of the last element of the doubly link list

For that matter, how do you get address of the first element?

--
pete

[Barry]

"ravi" <dc**********@g mail.comwrote in message
news:11******** **************@ g12g2000prg.goo glegroups.com.. .

On Jul 22, 4:34 pm, [e-mail] wrote:

>On 21 Jul, 07:23, ravi <dceravigu...@g mail.comwrote:

Can any body help in finding the middle element of a link list in an
effective manner

i know the simple solution of using two pointers and increment one
pointer by one and second by two.

but i want a effective algo both in terms of memory and time

If the structure is simply a linked list, there is no quicker way to
locate the middle element than by starting at one end and moving along
one element at a time. If the structure is a doubly linked list you
could improve on the method you have suggested slightly by starting
one pointer at the front, one at the end, and seeing where they meet -
that way you only traverse the list once instead of one and a half
times.

Hope that helps.
Paul.

But how i get address of the last element of the doubly link list

for eg. i am using

struct node
{
int data;
node* next;
node *previous;
};

The same way you get the pointer to the head of the doubly
linked list.