C++ Data StructuresLesson 49Free preview

C++ List

This lesson is part of C++ · All levels

Summary

Std::list is a sequential container based on a doubly linked list, so that each element stores a pointer to the element before and after it. Consequently, insertion and deletion in the already known position is very rapid, but random access to the element ke-i is not supported and must be traced from the end. The list is suitable for data that is often inserted or deleted in the middle, rather than being read by index.

Key points

The list supports push_back, push_front, pop_back, and pop_front.
List does not support operators [] and at() because it has no random access.
Insert(iter, value) inserted before the iterator position, erase(iter) removed that position.
Access to the element to i takes linear time because it has to be traced.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.