head & last ptrs in linked lists

[sahil_m]

Hi,
To quote Prelude's FAQ on linked lists

For code that maintains both a head and tail pointer, the first and last functions will never even be used! The only reason I put them there is because I'm usually too lazy to maintain head and tail pointers. But just so that you know the issues, regular use of first and last can be a big performance hit for large lists.

My question is that, how is maintaining a head and tail pointer more expensive than, say traversing the entire list each time you want to add a node at the end?

Thanks,
Sahil

[rockytriton]

it's not

[Prelude]

>how is maintaining a head and tail pointer more expensive than,
>say traversing the entire list each time you want to add a node at the end?
In general, an O(N) operation like walking down the list to insert a new node at the end is way more expensive than caching the current end of the list and making the same insertion O(1) because you usually spend a lot more time finding a place to insert than you do for the actual insertion. So it's not more expensive performance-wise, but it could be space-wise if you have certain space constraints.