C++ list

std::list is a doubly-linked list container from the STL, offering fast insertion and removal at any position, at the cost of slower random access compared to vector.

In this page:

What is std::list?
Adding Elements
Removing Elements
Iterating Through a list
list vs vector

What is std::list?

std::list is a container from the Standard Template Library implemented as a doubly-linked list, where each element is linked to its neighbors, offering fast insertion and removal anywhere in the sequence.

Example: What is std::list?

cpp

#include <iostream>
#include <list>

int main() {
	std::list<int> nums = {1, 2, 3};
	std::cout << nums.front() << " " << nums.back() << std::endl;
	return 0;
}

Adding Elements

Elements can be added to either end of a list with push_front and push_back, or inserted anywhere in the middle using an iterator, all in constant time since no shifting of other elements is required.

Example: Adding Elements

cpp

#include <iostream>
#include <list>

int main() {
	std::list<int> nums = {2, 3};
	nums.push_front(1);
	nums.push_back(4);
	for (int n : nums) std::cout << n << " ";
	std::cout << std::endl;
	return 0;
}

Removing Elements

pop_front and pop_back remove the first or last element, while erase removes an element at a given iterator position, all without needing to shift any other elements.

Example: Removing Elements

cpp

#include <iostream>
#include <list>

int main() {
	std::list<int> nums = {1, 2, 3};
	nums.pop_front();
	nums.pop_back();
	for (int n : nums) std::cout << n << " ";
	std::cout << std::endl;
	return 0;
}

Iterating Through a list

A list doesn't support square-bracket indexing since it isn't stored contiguously in memory, so elements are accessed through iterators or a range-based for loop instead.

Example: Iterating Through a list

cpp

#include <iostream>
#include <list>

int main() {
	std::list<int> nums = {1, 2, 3};
	for (int n : nums) std::cout << n << " ";
	std::cout << std::endl;
	return 0;
}

list vs vector

list offers constant-time insertion and removal anywhere, but only sequential access with no indexing, while vector offers fast random access via [] but slower insertion or removal in the middle.

Example: list vs vector

cpp

#include <iostream>
#include <list>
#include <vector>

int main() {
	std::vector<int> v = {1, 2, 3};
	std::cout << v[1] << std::endl;
	std::list<int> l = {1, 2, 3};
	l.push_front(0);
	std::cout << l.front() << std::endl;
	return 0;
}

🔒

Chapter Quiz — Complete all 15 topics to unlock

0/15 topics done

Complete these topics first:

← Previous Lesson C++ vector Next Lesson → C++ deque