Hacker News Reader

Comment by klysm | Hacker News Reader

Care to demonstrate why? I have the same experience

the linked list has a wonderful capability that's frequently seen in C where you can do O(1) removal from a list. E.g. you can have an "object" detach itself. This is not possible in Java's standard linked list implementation, among other languages.

in general, inserting and removing elements from a vector requires a memory copying.

There are programming languages that have linked lists as their fundamental data structure, like Lisp and Erlang.

For situations where I don't need random access, linked lists are hard to beat.

Linked lists also make wonderful immutable data structures.

linked lists have wonderful filter and flatmap performance. how much memory copying would a vector require?

The problem with your analysis is that you're using big-O notation. Big-O notation is based on an abstract machine that is pretty unrepresentative of real computers. In practice, the memcpy is always going to be faster (until you get to really big sizes). Put another way, linked list is O(1) with a massive constant, and memcpy is O(n) with a tiny constant.

And actually this logic extends to other algorithms too. My rule of thumb is that a linear search (despite being O(n)) will be faster up to around n=100 than binary search (which is O(log n)) just due to the way the CPU operates.

Yes, but in practice the coefficients on the O() almost always end up working in the dense arrays favor because of memory locality.

This is assuming you already have a pointer of the element you're removing, or a neighbor thereof. Otherwise, you'd have to traverse a portion of the linked list, which has a significant amount of per-element overhead.

Reply on news.ycombinator.com