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

Question

I was asked in an interview how to count the number of nodes in a linked list without going through the list? Is there any way to achieve this?

Answer 1

The only way I can think of is to add a counter for the number of nodes, which increases each time I call the add or insert methods and decreases when I call delete. You cannot make assumptions about the occupied memory, because being a linked list, you cannot guarantee that all nodes will be in one memory block (indeed, this is very unlikely).

Answer 2

If you are doing the distribution dynamically with something like malloc, then every time you insert / remove, there is no way other than updating the counter. If you are not performing the distribution dynamically, you probably have not implemented a linked list.

Answer 3

What these other guys are saying is perfectly true. How can you find out how many objects are in something before looking at them?

You will need to maintain the counter and increase / decrease it on inserts / deletes. This is a reliable method (most | only).

Answer 4

Add a counter to your structure and make the linked list circular rather than one by one. Instead of going through the whole list, just go to the source node prev node.