difference between std::list and linked lists
Hello
i am new in C++ and i was thinking of what is the difference between std::list and linked list and why we learn linked lists if std::list is available.
i am new in C++ and i was thinking of what is the difference between std::list and linked list and why we learn linked lists if std::list is available.
| std::list is a container that supports constant time insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is usually implemented as a doubly-linked list. |
Learning about data structures and algorithms is easier if you do it yourself.
| why we learn linked lists if std::list |
Because learning std::list excludes knowing how the list works internally.
Why should we care how it work internally?
Because std::list is not a magic wand, you may want to have additional functionality in std::list, and this means you'll need to implement your own list.
However to be able to do this, you need to know how lists work.
It's like saying, why do I need to know how to hammer planks together if I can order construction of a complete wooden house?
Well maybe someone robs you and you'd have no other choice but to spit in your hands and start construction on your own.
My guess is that many courses or books started as C and in C you have to create your own.
Data structures and algorithms are a whole topic in Computer Science - and are often taught as such.
Last edited on
Another way of looking at it, with a rhetorical question: Are you learning to use a list or are you using a list to learn other things?
someday, probably soon, you will have to work in a language that does not have built in data structures. Many do not. What will you do then? Learning to write a list will also let you build a tree or graph, neither of which are in C++ for you. The knowledge on how to do this is useful in many places, from other languages to extending what you know for new ideas.
| what is the difference ... |
Last edited on
| what is the difference between std::list and linked list |
A "linked list" is a generic term for a dynamic data structure that uses pointers to connect the contained elements (nodes) in a chain. std::list is a specific container implementation of that generic idea.
A linked list can be be implemented as:
1. a "doubly-linked" list with nodes that contain two pointers to the previous and next nodes in the list. Allows for iterating through the container bidirectionally.
2. a "singly-linked" list that consists of nodes that typically contain a single pointer to the next node of the list. Allows for iterating the container in one direction.
std::list is implemented as a doubly-linked container.
http://www.cplusplus.com/reference/list/list/
C++11's std::forward_list is a singly-linked container implementation.
http://www.cplusplus.com/reference/forward_list/forward_list/
On the theory side of linked lists there is a third variation, known as a "circular linked list." Instead of having discrete head and tail nodes that mark the beginning and end of the list the pointers "wrap around" so the head and tail nodes point to each other.
Hand-rolling a linked list is a good learning experience, but that IMO is not something a beginner needs to contend with. Learning how to USE a linked list should be first priority, with what C++ has to offer. Learning how to construct a linked list is an intermediate task once one becomes familiar with the concept.
Last edited on
as far as alternates go, there is also the skip-list, which has extra pointers so instead of ->next you may have ->next1000, to make large jumps until you get closer to the item you are searching for (really only useful if the list is ordered) or even by say a first letter (skip to first item with next letter in a alpha-sorted list to speed up search).
one of the best things about vectors is using push_back as 'new' and swap/pop_back() as 'delete'. The index is the 'pointer' so it can be saved and loaded instead of rebuilt. Then you have a hidden vector that your pointer soup container is built from, which can be iterated faster and in alternate ways, or saved directly to a binary file in one write operation, etc. Very practical to use them on the back-end of list/tree/graph/etc.
one of the best things about vectors is using push_back as 'new' and swap/pop_back() as 'delete'. The index is the 'pointer' so it can be saved and loaded instead of rebuilt. Then you have a hidden vector that your pointer soup container is built from, which can be iterated faster and in alternate ways, or saved directly to a binary file in one write operation, etc. Very practical to use them on the back-end of list/tree/graph/etc.
Last edited on
Topic archived. No new replies allowed.