Timeline for What are concrete rules for using a linked list instead of an array?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 11, 2015 at 18:05 | comment | added | Kate Gregory | the question has morphed over the years to invite performance-based rules for choosing between linked lists and arrays. This answer was written to explain how linked lists save the recopying of an entire list after an insertion or deletion. Comments on it are really not the place for discussion of the perf aspects (though I realized the edited question is now all about the perf aspect.) | |
| Nov 11, 2015 at 17:57 | comment | added | 5gon12eder | I don't think that this analogy is very accurate. As humans, we can (at least for such a short list) find an element in O(1). But if you want to do a random insert in a linked list, you'll have to traverse half the elements on average which costs you O(n) only to find the position where you want to insert. The actual insert then only costs O(1) but with an array, your cost is also “only” O(n). So the reason is not only due to move semantics but algorithmic. The constant factor hidden by the big-O is much larger for the liked list, however, due to the non-contiguous memory access. | |
| May 7, 2015 at 15:13 | comment | added | Ray | Oh yeah. Sorting. Good point. Also, I suppose, if you expect to insert to head or tail a lot and not many middle insertions, then linked lists would be better since head and tail insertions on linked lists are O(1) whereas on trees they're still O(log(n)). | |
| May 7, 2015 at 1:00 | comment | added | David Stone | @Ray: A linked list can outperform a tree structure if you expect there to be on the order of 4 elements and comparisons are relatively cheap. I do not know exactly where the cut-off is where this is not the case. Also, a tree structure requires that your data can be sorted, whereas a list structure allows you to maintain insertion order (or any arbitrary order). | |
| May 6, 2015 at 15:42 | comment | added | Kate Gregory | the question, @Ray, was not "What data structure to use?" but "when you do insert and delete a lot in some real life situation I understand?" Bringing trees (or even the relative truth of the insert/delete cost compared to vector) into the conversation just muddies that. | |
| May 6, 2015 at 15:37 | comment | added | Ray | I'm also wondering about lists, as I can't seem to find many advantages. @KateGregory seems to argue mainly based on insertion, then why not use trees for example, where insertion and deletion and lookup can be done in log time? Is it because for small sequences, lists perform better? @DavidStone? | |
| Jan 10, 2015 at 21:08 | comment | added | David Stone | @KateGregory: It has nothing to do with moves, at least not in general. His data type was a 4-byte int, for which a move and a copy are the same thing. The point was more that when copies are fairly cheap, the cost of iteration outweighs the cost of insertion. | |
| Jan 10, 2015 at 5:55 | comment | added | David Stone | @Dennis: I gave a presentation at C++Now 2014 that looked into this topic in more detail. youtube.com/watch?v=mMpBw7S2cqw Starting at 11:55 and going for a while, I look at whether this advantage of linked lists really does exist on modern hardware, comparing vector (dynamic array), a linked list (double-linked list), deque (a bit more complex than fits in this comment), and a vector of pointers to the data. | |
| May 22, 2014 at 14:23 | comment | added | Dennis | @KateGregory fair enough, but it's still good to point out that "basic" data structures are often better than the cool data structures we learn about in school (or elsewhere). I don't want new grads to use LLs everywhere because it's theoretically appropriate while possibly being a poor choice realistically. Using the right data structure is important, and sometimes people overcomplicate it. Slightly related is this talk by Jonathan Blow (creator of "Braid") on data structures. | |
| May 22, 2014 at 1:38 | comment | added | Kate Gregory | @Dennis yes, I know, thanks to move semantics. However this is not true for all languages so the example stands. | |
| May 21, 2014 at 23:54 | comment | added | Dennis | According to Bjarne Stroustrup, LLs may not be as quick and easy for copying the whole list as you think. | |
| Jan 5, 2012 at 17:35 | vote | accept | CommunityBot | ||
| Jan 5, 2012 at 13:48 | history | answered | Kate Gregory | CC BY-SA 3.0 |