10 ms·
It is worth remembering that linked lists were invented back in the dawn of computing. This was when systems... often didn't even have cache memory at all. Ac
by ansible 6y ago
It is worth remembering that linked lists were invented back in the dawn of computing.
This was when systems... often didn't even have cache memory at all. Accessing different RAM values took the same amount of time, and sometimes with a single clock cycle. Fast! So jumping around a (large, for the time) linked list in heap memory wasn't nearly as slow as something comparable today, relative to other data structures.
- mcculley 6y agoIt is worse in Java. The standard LinkedList class in Java stores references to the data, not the data, in nodes, so there is more pointer chasing.
- sltkr 6y agoThis applies equally to ArrayList.
- mcculley 6y agoYes, but if you can use ArrayList, you can also use an array. If you want to be able to remove an object from the middle without moving objects around, you have no choice other than LinkedList and the extra references.
- pjmlp 6y agoFor the time being, value types will eventually fix that. Ironically some of the ideas how to proceed with value types integration were already present in Eiffel, but so are design decisions.
- xirbeosbwo1234 6y agoSo do arrays. You can never have an "inline" object. It's always a reference. Java has another problem because each node is an object, though. Every object has (I believe) about 16 bytes of overhead. That will double the size of each node.
- gpderetta 6y agomost importantly, those machines were not fully pipelined (if at all) and certainly not capable of out of order execution, so the inherent forced serialization of a linked list traversal was not an issue.