3 ms·
"So we have ~doubled the memory usage of a list, in that we need both a pointer (to the contents), and an integer, for each cell of the list." While I'm not go
by dllthomas 12y ago
"So we have ~doubled the memory usage of a list, in that we need both a pointer (to the contents), and an integer, for each cell of the list."
While I'm not going to say storing the length with each cell is advisable, this exaggerates the cost of it. First, you're forgetting the links between cells, so it shouldn't be "double" in any case. Second, of course much of the time the list items will dwarf the spine of the list. Finally, you should be able to get away with a smaller representation for list length than for pointers.