3 ms·
Most C++ implementations of linked lists are bad, including std::list and apparently, this course's. People misunderstand linked lists so badly, that they actu
by Peaker 13y ago
Most C++ implementations of linked lists are bad, including std::list and apparently, this course's.
People misunderstand linked lists so badly, that they actually list the motivation for linked lists as fine-grained growth, as opposed to an array-based list.
The main benefits of linked lists over array-lists are:
* Can put data structures in lists even if they are already in some other data structure. For example, have some ordering between array elements.
* In intrusive style (can find the list links based on the item), can add after that position in O(1).
* In intrusive style with doubly-linked list, can also delete an item in that position in O(1).
Non-intrusive lists are incompatible with having the same O() while also allowing an item to be in multiple data structures simultaneously.
std::list indeed does not allow this, and is almost useless.
It's sad to see this taught incorrectly in courses, too, perpetuating the uselessness of std::list.
- deleted 13y ago[deleted]
- betterunix 13y ago1. You can maintain a linked list whose elements are already stored in another data structure. This allows you to impose a different order on the elements without having to copy them. 2. http://www.boost.org/doc/libs/1_45_0/doc/html/intrusive/intrusive_vs_nontrusive.html http://www.boost.org/doc/libs/1_45_0/doc/html/intrusive/intr... Were there any other terms you had trouble with?
- deleted 13y ago[deleted]
- zerohp 13y agoYour points 2 and 3 are satisfied by using an iterator to keep track of the position.
- ambrop7 13y agoBut then you have to pull those iterators into almost everything that deals with your objects, making the code hard to follow, and wasting memory. The problem also gets worse when your objects are in more than one list (which you can't literally do with std::list anyway) since you have to keep several iterators around.
- deleted 13y ago[deleted]
- dnautics 13y agopoint one satisfied using a dynamic array of pointers.
- Peaker 13y agoWith O(N) rather than O(1) costs for any list operations.
- dnautics 13y agoin my experience, most array operations are read, not change.
- Peaker 13y agoI work on a high performance system which needs to handle lots of concurrency of requests with various possible scenarios. In order to efficiently time out requests, need to have the requests sit in a chronological list. But they also need to be quickly found by other orderings, so they also sit in hash tables. When a request is complete, I need to efficiently delete it from all these structures. Using ptr arrays rather than lists would be catastrophic for our performance. There is virtually no advantage whatsoever to the array approach over the list approach in our case and in many others.