C++ Basics

C++ Functions

C++ Classes

C++ Errors

C++ Reference

C++ Data Structures

C++ List

❮ Previous Next ❯

C++ List: Doubly Linked Lists

While vectors are great for fast data access, they can be slow when inserting or deleting elements in the middle of the collection. This is where the C++ List comes in handy.

A list in C++ is essentially a doubly linked list. It allows for extremely fast insertions and deletions anywhere in the list.

1. Using a List

To use a list, you must include the <list> header file.

Unlike a vector, elements in a list are not stored in contiguous (side-by-side) memory blocks. Because of this, you cannot access a list element directly by its index (like myList[2]). You must traverse the list.

List Example

#include <iostream>
#include <list>
using namespace std;


int main() {
  // Create a list of integers
  list<int> myNumbers;


  // Add elements to the back
  myNumbers.push_back(10);
  myNumbers.push_back(20);


  // Add elements to the front
  myNumbers.push_front(5);


  // Accessing elements (First and Last)
  cout << "First element: " << myNumbers.front() << "\n"; // Outputs 5
  cout << "Last element: " << myNumbers.back() << "\n";   // Outputs 20


  return 0;
}

2. Vector vs. List: When to use which?

Understanding when to use a vector versus a list is a common interview question!

Feature std::vector std::list
Access Speed Fast (O(1) time complexity) Slow (O(N) time complexity)
Insertion/Deletion (at end) Fast Fast
Insertion/Deletion (in middle) Slow (Requires shifting items) Fast (Only updates pointers)
Memory Layout Contiguous (Next to each other) Scattered across memory

Summary: Use a vector if you need to access elements frequently by their position. Use a list if your program frequently adds and removes elements from the middle of the dataset.

Exercise

?

Why can't you access a list element using an index like myList[3]?

❮ Previous Next ❯