Traversing the link list from end

[plmanikandan]

Hi,
I am new to link list programming.I need to traverse from the end of
link list.Is there any way to find the end of link list without
traversing from start(i.e traversing from first to find the next for
null).Is there any way to find the length of linked list in c.My need
is to traverse from the end to 5th node


Regards,
Mani

 

[Nelu]

Hi,
I am new to link list programming.I need to traverse from the end of
link list.Is there any way to find the end of link list without
traversing from start(i.e traversing from first to find the next for
null).Is there any way to find the length of linked list in c.My need
is to traverse from the end to 5th node


Regards,
Mani

If each of the element in the list is connected to the
next element of the list then there's no way to know what
element links to a given element without traversing the
list from the top to the preceding element. You can't
come up with the last element without traversing the whole
list unless you store some additional information.
You need to use a double linked list in order to do reverse
traversing properly.

Let's say you have a simple list structure defined as:
struct list_node {
void *info;
struct list_node *next;
};
Then your last list node will have some information in the
info element and next=NULL. You don't know anything about the
element preceding the last element. Actually, you can have
a lot of pointers pointing to an element. How is the
language supposed to know which one is part of your list
and which one to pick?
The logic of the program depends entirely on you. The
compiler can't figure out what you want to accomplish.

A node in a double linked list would look something like this:
struct dlist_node {
void *info;
struct dlist_node *previous;
struct dlist_node *next;
};
In this case it is possible to start from the last node and go
back. The top node would have previous=NULL and the last node
would have next=NULL;
If you traverse the list to the end and count the nodes then
you will know how many elements you have and how to go back.
If you use another structure like this:
struct dlist_controller {
struct dlist_node *top;
struct dlist_node *bottom;
int dlist_count;
};
and write the proper functions to increment dlist_count
when you add something new, decrement dlist_count when
you remove a node and make sure that top and bottom always
point to the top and bottom elements of the list, then
it's easy to find the last element(bottom), know exactly
how many elements you have in the list without traversing the
list (dlist_count) and be able to move backwards through the
list.
I'll leave it to you to implement something like this if you
think this is what you need.

 

[santosh]

Hi,
I am new to link list programming.I need to traverse from the end of
link list.Is there any way to find the end of link list without
traversing from start(i.e traversing from first to find the next for
null).Is there any way to find the length of linked list in c.My need
is to traverse from the end to 5th node


Regards,
Mani

I assume you are talking about the single linked list.

You can keep track of the "last node" and the "count" of the nodes when
creating new nodes.

In this way you can easily add new nodes to the list.

Just create another node like *head node , call it *tail node.
Now whenever you create new node, do the following:
tail->ptr = NEW_NODE ;
tail = NEW_NODE ;
count++ ;

That's all............


For the record, there is no way in C to find out the last node without
traversing the single linked list.

 

[stathis gotsis]

If each of the element in the list is connected to the
next element of the list then there's no way to know what
element links to a given element without traversing the
list from the top to the preceding element. You can't
come up with the last element without traversing the whole
list unless you store some additional information.
You need to use a double linked list in order to do reverse
traversing properly.

Let's say you have a simple list structure defined as:
struct list_node {
void *info;
struct list_node *next;
};
Then your last list node will have some information in the
info element and next=NULL. You don't know anything about the
element preceding the last element. Actually, you can have
a lot of pointers pointing to an element. How is the
language supposed to know which one is part of your list
and which one to pick?
The logic of the program depends entirely on you. The
compiler can't figure out what you want to accomplish.

A node in a double linked list would look something like this:
struct dlist_node {
void *info;
struct dlist_node *previous;
struct dlist_node *next;
};
In this case it is possible to start from the last node and go
back. The top node would have previous=NULL and the last node
would have next=NULL;

Everything nicely written. I would add that one might want a cyclic
double-linked list. In that case: the top node whould have previous=last
node and the last node would have next=top node. Then, going back six nodes
from top node, you can find the fifth node from tail.

 

[Nelu]

Everything nicely written. I would add that one might want a cyclic
double-linked list. In that case: the top node whould have previous=last
node and the last node would have next=top node. Then, going back six nodes
from top node, you can find the fifth node from tail.

Yes. I skipped that to keep it simple, so he takes things one
at a time . But you're right, it would've painted a nicer
picture with cyclic double linked list.

It didn't cross my mind at the time but he can use another list
as a stack and transfer the information from the list to the
stack in one go. Then iterate the stack and it gives the reversed
order. Using a single linked list for the info and another
temporary single linked-list for the stack. This, if he doesn't
want to use a double-linked list. If he stores information about
the size of the list so it's readily available without parsing the
list, then he can use an array for the stack and make things even
faster.