Write a method to count the number of items in a linked list

[kyleg033]

If I wanted to make a method to count the amount of items in a linked list, how would I go about doing that?
I want to make both an iterative solution and a recursive solution if possible...Thanks guys I really appreciate the help!

[helios]

Initialize a pointer to the first node and p=p->next while p is a valid pointer. This should only be done iteratively. Actually, the proper way to do this would be to keep a size variable in the list structure.

[Duthomhas]

Yes, only use recursion on unbounded structures if you can do it with proper tail recursion -- which is pretty much the same as doing it iteratively.

[kyleg033]

Thanks guys that makes sense, but how would I write a method that I could add to a project that I am working on that could accomplish this? Sorry, I'm just learning how to use NODEs and it would really help me understand them to know how to count them... Im pretty sure it would have something to do with the item->Next function that would visit each NODE but I dont know how exactly it would count the number of items....

[kyleg033]

anybody? I've looked everywhere on the net that I can think of and still cant figure out how to write this...

[Zhuge]

Exactly as helios said, just increment a counter variable as you are visiting each node.

[kempofighter]

Is this C or C++? Why don't you at least study the std::list class interface to see what the standard container can do. The examples on this site could give you a general idea of how to implement some of these concepts. By the way, why doesn't the list simply maintain a counter as nodes are inserted just as Helios suggested? The only good reason that I can think of for iteratively counting is for something like the count_if algorithm which counts only if some predicate returns true (count all nodes with a value within some range for instance).

[kyleg033]

This is C++, I will take a look at the std::list class interface, but I just don't really see how to transition from one node to the next while incrementing a counter variable. It may be something really easy to do but I have no experience with using Nodes/linked lists.

[Duthomhas]

Just to make it clear: you are being given a hard time because you are looking for a handout instead of solving the problem yourself. This is a very basic homework question tackled in "Introduction to Programming" 101 or 102. You must solve it yourself.

Here are some hints:

1. Your linked list must have links -- pointers to the next piece of the list.

struct node_t
  {
  int     datum;  // This is the thing stored in the list
  node_t* next;   // This is the link to the next node in the list.
  };

2. Get out a piece of paper and a pencil, and draw yourself a linked list. It might look something like:

+----+   +----+   +----+
| 42 |-->| 19 |-->| -3 |-->NULL
+----+   +----+   +----+

The numbers are, of course, the data, and the arrows are the next node pointers.

Everything you do to this list you should first draw how you would do it yourself. Then make the computer do what you drew.

In the case of counting your list, you know that you must have a node pointer to the first item in the list. What can I do with that pointer to find the number of items in the list?

Those are some pretty big hints. Good luck!

[kyleg033]

Ok, I understand that part. Sorry I should have made my question clearer. I am wondering how to use the counter, I'm unsure how to actually count the items. I think I would start with a pointer pointing at the head, lets call it cur. I was thinking I could run it through a while loop:

while(cur != NULL)
{
int count;
cur->next;
count++
}

Is this how you would this solve the problem?

[Duthomhas]

Yes. Good luck!

[kyleg033]

Thank you so much!