By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,144 Members | 1,267 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,144 IT Pros & Developers. It's quick & easy.

Middle of a link list

P: n/a
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

Jul 21 '07 #1
Share this Question
Share on Google+
4 Replies


P: n/a
On 21 Jul, 07:23, ravi <dceravigu...@gmail.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.

Jul 22 '07 #2

P: n/a
On Jul 22, 4:34 pm, gw7...@aol.com wrote:
On 21 Jul, 07:23, ravi <dceravigu...@gmail.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;
};

Jul 22 '07 #3

P: n/a
ravi wrote:
>
On Jul 22, 4:34 pm, gw7...@aol.com wrote:
On 21 Jul, 07:23, ravi <dceravigu...@gmail.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
Jul 22 '07 #4

P: n/a

"ravi" <dc**********@gmail.comwrote in message
news:11**********************@g12g2000prg.googlegr oups.com...
On Jul 22, 4:34 pm, gw7...@aol.com wrote:
>On 21 Jul, 07:23, ravi <dceravigu...@gmail.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.
Jul 22 '07 #5

This discussion thread is closed

Replies have been disabled for this discussion.