开发者

diff between ADT list and linked list

What is the ( real | significiant ) difference (s) between ADT list implementation and linked list implementation with respect to queue ?

Moreover, Can you suggest any website with visual example of these typ开发者_运维技巧e of lists ?


It is REALLY hard to understand this question, but in an attempt to ask what the actual question is, I believe to have figured it out. So my assumption is, that the question is: "What is the difference between std::list and std::queue. @fatai: Please correct me, when I am wrong.

The std::list is a doubly-linked list. Each element of the list "knows" the next and previous element. And the list "knows" it's beginning and end. Look here: http://www.cplusplus.com/reference/stl/list/

The std::queue is a list, with special functionality. This functionality allows you to easily insert elements at the front, and remove elements from the back. Have a look here: http://www.cplusplus.com/reference/stl/queue/

If you want to have minimal functionality, I'd use queue. The queue is optimized for its purpose. It also prevents you from doing things accidentally wrong (such as remove an element from the middle).

I hope that answers your (confusing) question. ;-)


Erasing and inserting into middle of the list by using iterator has O(n) complexity because in the background it has to shift all the other elements. (uses special model of vector ADT, but you cant even access to list element with index mechanism).

In linked-lists erasing and inserting to list has O(1) complexity. It doesn't needs to shift the elements for the operations. Even searching an element in linked lists has O(n) complexity like the list ADT.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜