std::list
- C++ course
- Intermediate
- Lesson 54/116
- 5 min
Learn doubly linked lists with std::list.
std::list
std::list is a doubly linked list. push_front adds to the beginning, push_back to the end. front() returns the first element.
Example: std::list<int> l; l.push_front(10); l.push_front(20);. Now the list is 20 -> 10. l.front() returns 20. Because push_front adds at the head, the last added element is first. A linked list does O(1) insert/erase in the middle.
list vs vector
list offers O(1) insert/erase in the middle (given an iterator). But there is NO random access: l[2] won't compile. Sequential access uses iterators.
vector offers O(1) random access (v[2]), but middle insertion is O(n). Choose: frequent middle inserts need list; frequent random access needs vector. Memory: vector is contiguous; list is node-by-node with overhead.
Practice Work with list
Create std::list<int> l;. Call push_front(10) then push_front(20). Print l.front() with std::cout.
Starter code
#include <iostream>
#include <list>
// create a list and add two elements at the front
int main() {
// print the first element
return 0;
}Sample solution
#include <iostream>
#include <list>
int main() {
std::list<int> l;
l.push_front(10);
l.push_front(20);
std::cout << l.front() << std::endl;
return 0;
}Expected output
20
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Complete the push_front call
l.push_front(____);l.push_front(10);Explanation: l.push_front(10); adds 10 to the head of the list.
2 Which operation is NOT possible on a list?
std::list<int> l;- push_front
- push_back
- front()
- access with l[2] Correct answer
Explanation: list has no random access; l[2] won't compile.
3 Match method to role
| Term | Meaning |
|---|---|
push_front |
Add to head |
push_back |
Add to tail |
front() |
First element |
size() |
Element count |