Why is it linked list is being taught ?
As a data structure there doesn't seem to be anything good coming from the use of linked list. Most argument is about bad for cache because of random location. I have watch one of bjarne presentation that one should always use vector instead of linked list. If there is really no good use for them why teach them in every data structure intro ?
Its implementation is a great training actually. And it is fairly easy to implement.
| Its implementation is a great training actually. And it is fairly easy to implement. |
what is being trained actually ?
| it's used all the time in advanced data structures and algorithms. |
which algorithm use linked list ?
I haven't read many other people code and I've only found it once in the box2d body class.
and another question pop up in my mind.
Many has claim that linked list is a bad data structure... but beginner wouldn't know that.
I am quite ignorance of this data structure because I don't really know the use case. Once I want to try using it, I began searching then I stumble upon a lot of prove saying linked list is bad for performance.
Why wasn't it mentioned in intro of data structure that linked list is bad for performance ?
It's amazing how often people come and make some assertion that they could have easily disproved for themselves by simply googling it.
Anything with trees and graph traversal (and I guarantee you have no idea how encompassing that is -- enjoy using the internet? there you go), constant time memory needs (like in hash tables), any kind of language design and often in implementation (functional languages use them almost exclusively), resource management (like anything your OS does -- which again is a whole lot more than you think, or the C memory manager, or the call stack, for examples), advanced mathematical applications (polynomials, matrices, solvers, etc), uh, compilers use them, AIs use them, games use them, ...
Stick with trivial tasks and sure, you can argue you'll never need a linked list (even if you're using one underneath without even knowing it).
I've been doing this for nearly 30 years, and I've never seen anyone who knows what they're doing claim that a linked list is a 'bad' data structure. (I've seen people recommend a different data structure, based on requirements, but that's not the same thing.)
What people say has nothing to do with proving anything.
Element access in a linked list is O(n), compared to an array's O(1). But this only counts if you have a 1:1 integer key lookup.
I can't answer for the quality of instruction you have received -- or lack of it, apparently.
| which algorithm use linked list |
| I haven't read many other people code and I've only found it once in the box2d body class. |
| Many has claim that linked list is a bad data structure... but beginner wouldn't know that. |
| began searching then I stumble upon a lot of prove saying linked list is bad for performance. |
Element access in a linked list is O(n), compared to an array's O(1). But this only counts if you have a 1:1 integer key lookup.
| Why wasn't it mentioned in intro of data structure that linked list is bad for performance ? |
Linked lists have some inherent properties which make it the sequence container of choice under certain circumstances:
a. A good list implementation provides strong exception guarantees for modifiers.
http://stroustrup.com/3rd_safe.pdf
b. Modifiers of a linked list do not invalidate iterators, references or pointers to the other elements in the list.
c. Elements can be transferred from one list to another without requiring a move or a copy of the elements involved.
http://en.cppreference.com/w/cpp/container/list/splice
a. A good list implementation provides strong exception guarantees for modifiers.
http://stroustrup.com/3rd_safe.pdf
b. Modifiers of a linked list do not invalidate iterators, references or pointers to the other elements in the list.
c. Elements can be transferred from one list to another without requiring a move or a copy of the elements involved.
http://en.cppreference.com/w/cpp/container/list/splice
| what is being trained actually ? |
| Why wasn't it mentioned in intro of data structure that linked list is bad for performance ? |
For example custom linked list can be a heterogeneous container without too many layers of indirection and actually outperform vector in some cases. Chain of responsibility pattern often implemented using intrusive single linked list.
@Duoas
I didn't know graph and trees is a linked list. If it's then I've seen a lot linked list being used. It's true I haven't touch that kind of code you mention above.
I am talking about how it jump around in unpredictable manner.
Beside although vector only take O(1) to access but still need O(n) search to know which to access... Therefore I don't think that's linked list weakness
@MiiNiPa
I didn't know what is "Chain of responsibility pattern"
@JLBorges, @Duoas, @MiiNiPa, @LB
Thank you for the answer.
It has pretty much answer my question.
I didn't know graph and trees is a linked list. If it's then I've seen a lot linked list being used. It's true I haven't touch that kind of code you mention above.
| Element access in a linked list is O(n), compared to an array's O(1). But this only counts if you have a 1:1 integer key lookup. |
I am talking about how it jump around in unpredictable manner.
Beside although vector only take O(1) to access but still need O(n) search to know which to access... Therefore I don't think that's linked list weakness
@MiiNiPa
I didn't know what is "Chain of responsibility pattern"
@JLBorges, @Duoas, @MiiNiPa, @LB
Thank you for the answer.
It has pretty much answer my question.
Another reason why linked list is often outperformed, is that modern CPU are optimised for sequental access. In embedded programming you might run into CPU with, for example, no cache at all or really small/not that fast cache which makes linked list a valid choice in many cases.
> Beside although vector only take O(1) to access but still need O(n) search to know which to access...
Not necessarily. With a vector, algorithms which need random access are feasible. For instance, with a list we can't use a quick sort or a heap sort. A priority queue (heap data structure) can be efficiently implemented over a vector.
Unless heavily used, large lists are used in conjunction with a custom pool allocator (they usually are), they may induce fragmentation of the free store, impacting overall program performance.
A practical consideration to shun std::list<> in portable code is that the GNU library is widely used.
http://www.cplusplus.com/forum/lounge/145092/#msg764753
Not necessarily. With a vector, algorithms which need random access are feasible. For instance, with a list we can't use a quick sort or a heap sort. A priority queue (heap data structure) can be efficiently implemented over a vector.
Unless heavily used, large lists are used in conjunction with a custom pool allocator (they usually are), they may induce fragmentation of the free store, impacting overall program performance.
A practical consideration to shun std::list<> in portable code is that the GNU library is widely used.
http://www.cplusplus.com/forum/lounge/145092/#msg764753
Topic archived. No new replies allowed.