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]

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]

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]

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?

 

[Barry]

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.