How to count the number of nodes in a linked list without traversing it?

I have been asked i开发者_开发百科n an interview how to count the number of nodes in a linked list without traversing the list? Is there any way to achieve this?

The only way I can think of is to add a counter of the number of nodes which is incremented each time the add or insert methods are invoked, and decremented when delete is invoked. You cannot make assumptions about memory occupied because, being a linked list, you cannot guarantee that all nodes will be in the same memory block (indeed, this is highly improbable).

If you are doing allocation dynamically with something like malloc then there is no way other than updating a counter each time you insert/delete. If you're not doing allocation dynamically then you probably haven't implemented a linked list.

What these other guys are saying is totally right. How can you know how many items are in something before you look at them?

You're going to need to maintain a count, and increment/decrement it on inserts/deletes. It's the (most|only) reliable way.

Add a counter to your struct and make the linked list circular instead of singly. Instead of traversing through the entire list just traverse to the initial node's prev node.