3 ms·
In my experience, if you use a List supplied by the standard library of your language, it isn't a linked list. In fact it's usually an "ArrayList" style. (1) T
by SideburnsOfDoom 12y ago
In my experience, if you use a List supplied by the standard library of your language, it isn't a linked list. In fact it's usually an "ArrayList" style. (1)
This is so that length() and item = list[index] operations are not O(n), they are O(1). You do have to be aware of the tradeoffs, e.g. that inserts into the middle of the list can be slower (and YMMV with adding at the end. It depends on if a realloc is triggered).
It's worth checking which implementation you actually are using, but linked lists are the exception, for good reasons.
And when you have no choice but to walk the list, it's well known that instead of writing this (in c# functional style pseudocode)
if (someList.Count(item => someCond(item)) > 0) doSomething();
... it's better to write
if (someList.Any(item => someCond(item)) doSomething();
This is for much the same performance reasons - you don't need the exact count when all you want to know is if there are any, and the count can become expensive if the list is long.
1)
Java: http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList...
c#: https://msdn.microsoft.com/en-us/library/6sh2ey19%28v=vs.110%29.aspx https://msdn.microsoft.com/en-us/library/6sh2ey19%28v=vs.110...
python: http://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented http://stackoverflow.com/questions/3917574/how-is-pythons-li...
- theseoafs 12y agoErlang is a functional language; functional languages are different. They really need proper linked lists as a built-in default "list" data structure.
- SideburnsOfDoom 12y agoRight. Is that because functional languages prefer immutable data structures? e.g. cdr/ tail / list.skip(1) are easier and simpler if you can just return the first element's next pointer rather than copying an array.
- theseoafs 12y agoYes, that's the idea. ArrayLists don't work well at all if you want persistent data structures as your language's default. Also arrays are less sensible for pattern-matching. (Note that most functional languages offer normal stateful arrays as an option, if they're necessary; interestingly, Erlang does not.)