4 ms·
Insertion and deletion are prime examples, often requiring you to move large chunks of memory. The same operation just requires pointer changes (after finding w
by bmon 9y ago
Insertion and deletion are prime examples, often requiring you to move large chunks of memory. The same operation just requires pointer changes (after finding where you want to insert or delete). I think in this example it would be common to be removing structs from the center of the list.
- signa11 9y ago> Insertion and deletion are prime examples, often requiring you to move large chunks of memory. on modern cpu's with huge caches, i seriously doubt this claim. fwiw, i have played around with synthetic problems where: i insert sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequence of positions. and almost always, vectors outperform lists by at least couple of orders of magnitude. or to put it another way, it is almost never about either lists / vectors or something else, and boils down to couple of 'rules' e.g. access data predictably (avoid trashing the cache), keep data compact (more cache utilization) etc. etc.
- jstimpfle 9y ago> i insert sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequence of positions. Which means that you scan the list twice for each node. First for insertion and then for deletion. Starting at maybe a hundred that would be much more efficient with a balanced search tree. They have a good Red-black tree in Linux. But if it's only arrays vs lists - with linked lists, pointers to items are never invalidated. With dynamic arrays, they are. Dynamic arrays are fine for plain old data arrays. But it's harder for data that has "identity" and is frequently mutated. And if a node is in multiple lists, I guess arrays are out. You'd need to store the data redundantly. Extra bad if you need atomic mutations.
- yongjik 9y agoWell on a 64-bit machine each node of a singly-linked list of integers will be 16 bytes (8 byte pointer + 4 byte integer + 4 byte for padding). That's 300% overhead. Becomes 500% for doubly-linked lists. So it's not surprising that linked lists perform very poorly in such circumstances.
- sclangdon 9y agoInsertion and deletion _were_ prime examples. It's not necessarily the case with today's hardware, especially until you reach some threshold of the number of elements (usually hundreds of thousands). You say "the same operation just requires pointer changes (after finding where you want to insert or delete)" like it's some trivial thing that doesn't enter the equation. But finding where you want to insert or delete in a non-contiguous linked list is not a consideration that should be an afterthought in brackets. Furthermore, when you have found the location, it's still not _just_ pointer changes. You actually have to allocate the memory for the node, too. Traversing pointers and allocating memory is a lot slower than working with a contiguous block of memory (assuming you don't have to re-allocate the contiguous block of memory, of course). Either way, don't take my word for it. If you're a C++ programmer, just benchmark std::vector against std::list, or watch this video - https://youtu.be/YQs6IC-vgmo https://youtu.be/YQs6IC-vgmo
- jstimpfle 9y agoDon't forget that there are valid uses of linked lists even in 2017. If there are more insertions / removals than scans, an array makes no sense. Reallocating a big dynamic array is also a no-go in many time-constrained situations. > You actually have to allocate the memory for the node, too. The way this is done is by intrusive linking (the data must include list pointers). The data usually knows in which lists it is linked, so there is no point in having a version of the data without a list head.