CANEHDN said:
I do have to write a shuffle() function for the linked list. Any suggestions on the best way to do that? The reason I'm asking the stuff on linked lists is I was never too good at the data structures stuff. Arrays I'm ok with. Any ideas would be great. Thanks
Benchmarks show that linked lists are only better than vectors when dealing with many hundreds of thousands, or millions, of objects. And even then, you typically have to have a doubly linked list.
- Heap allocation can be expensive. A vector makes less and less heap allocations as it grows, whereas a linked list makes a constant number of allocations as it grows.
- Cache locality #1. A Java Object has at least 16 bytes of overhead. A typical linked list node, with one "next" pointer will take up 20 bytes (16 byte overhead + 4 byte next pointer), wasting 80% of memory. This will spread the real data over more pages, and reduce the CPU cache effectiveness.
- Cache locality #2. A vector will place all references adjacent to each other, meaning they're on the same page. A naive linked list node class will have each node allocated from the heap as the list is grown, which might result in each node residing on different pages. Of course the refered to data object can still be anywhere.
- Iteration. It's much faster to increment an index and dereference the next slot in an array than to follow a "next" pointer.
On the other hand, a linked list, for sufficiently large data sets, can be faster at head insertion, or inserting into the middle. But, if you're always inserting to the head, then you can simply use a vector backwards. And inserting to the middle still requires traversing to the middle for a linked list.
