In C++, a List is essentially a doubly linked circular list with a head node. Sounds a bit convoluted, right?

Many friends struggle to understand the difference between List and vector when they first learn about it… Please take a look at this image 👇

Image: A doubly linked circular list with a head node, where the head node acts like a little captain, pointing to itself on both sides.

Imagine this:

• A List is like children holding hands in kindergarten👫👭👬, where each child (node) holds the hands of the previous and next child, forming a long line. Want to add a new friend? Just let the two neighboring children release their hands, pull in the new friend, and rejoin hands!
• A vector is more likea military formation during training, where everyone is lined up neatly, and each person has a fixed position number. Want to cut in line? Everyone behind has to move back one step!

The core advantage of the List structure is:insertion and deletion are super convenient! Just like adding a person to the line, you only need to let the children on either side release their hands and rejoin,without having to move the entire line like with a vector～

Part1Basic Concepts of List

(1) Functional Positioning

Data is stored inchain-like storage, unlike a vector where elements are “living together”, they are “living separately” and connected by “telephone lines” (pointers)!

(2) Essence of Linked List

A list is anon-contiguous storage structure on physical storage units, where the logical order of data elements is achieved throughpointers linking. It’s like your chain of stores, where each store is not located next to each other, but they are all connected through an internal system!

(3) Components of Linked List

A linked list consists of a series ofnodes, where each node is an independent entity!

(4) Node Structure

One part stores data, called the data field, like the candies a child carries in their pocket; the other part stores the address of the next node, called the pointer field, which is like the child knowing where the next person is.

(5) Special Design in STL

The list in STL is adoubly linked circular list, where each node knows who the next one is and who the previous one is, and the ends are connected to form a loop!

(6) Iterator Characteristics

Due to thenon-contiguous storage, the iterator in a list only supportsforward and backward movement, making it adoubly iterator. It’s like you can only walk along the chain in one direction at a time, and cannot jump to any position directly!

(7) Memory Aspects

The list usesdynamically allocated storage,which avoids memory waste and overflow. Performing insertion and deletion operations only requiresmodifying pointers,without needing to move a large number of elements. It’s like renting a house; if you want to add someone, just add a room without everyone squeezing together!

(8)We must also mention the drawbacksWhile flexibility is great, the pointer field takes up space, and traversing can be time-consuming, like carrying a lot of luggage when going out; it’s convenient but a bit heavy.(9) Important PropertyInsertion and deletion operations do not invalidate the original iterators, which is something Vector cannot do; if a Vector is modified, its iterators may become invalid.

Part2Framework Construction

Now we start implementing the list container, first considering theframework structure:

1. Node structure: (similar to the node in the source code) – the “bricks” of the linked list
2. List class: needs to have ahead node, making it easier for us to perform insertion and deletion operations – the “foundation” of the linked list
3. Iterator class – allows us to elegantly traverse using ++/– as a “magic wand”

That’s basically it, now let’s starthandcrafting!

2.1, Node Class: The DNA of the Linked List

// Node structure
template<class T>
struct ListNode {
    ListNode* _next;  // Pointer to the next node
    ListNode* _prev;  // Pointer to the previous node
    T _data;          // Data stored in the node

    // Constructor using initializer list (recommended but not mandatory)
    ListNode(T x = T()) :
        _next(nullptr),
        _prev(nullptr),
        _data(x) {}

    /*
    // Equivalent constructor without using initializer list
    ListNode(T x = T()) {
        _next = nullptr;
        _prev = nullptr;
        _data = x;
    }
    */

    // Destructor: to avoid dangling pointers, just set pointers to nullptr
    ~ListNode() {
        _next = nullptr;
        _prev = nullptr;
    }
};

Code Analysis:

• Usingtemplates to accommodate more data types, which is the standard practice in STL!
• Each node contains three core members:<span><span>_next</span></span>, <span><span>_prev</span></span>, and <span><span>_data</span></span>
• Provides aconstructor (using an initializer list is recommended, but not mandatory)
• The destructor is simple but effectively avoids dangling pointer issues

Thoughts: Is using an initializer list in the constructor necessary?

Answer: No, it’s not necessary, but it’s recommended! Initializer lists are more efficient, especially for class-type members.

2.2, List Class: The “Skeleton” of the Doubly Circular Linked List

template<class T>
class list {
public:
    // Set the alias for the adaptable node type (for later use)
    typedef ListNode<T> Node;

    // Empty initialization: create head node and form a loop
    void empty_init() {
        _head = new Node;           // Create head node (sentinel node)
        _head->_next = _head;       // Head node's next points to itself
        _head->_prev = _head;       // Head node's prev also points to itself
        _size = 0;                  // Initial size is 0
    }

    // Constructor
    list() : _head(nullptr) {
        empty_init();               // Call initialization function
    }
private:
    Node* _head;    // Head pointer (actually the sentinel node)
    size_t _size;   // Size of the linked list
};

Why have a sentinel node? Because it makes the operation logic of “empty list” and “non-empty list” completely consistent, without special handling for head and tail boundaries!

2.3, Iterator Class: Allowing Elegant Traversal of the Linked List

This is the most essential part! Let’s consider:Can we use raw pointers to perform iterator operations (++, –, ==, !=)?

The answer is certainly no!

Because the physical addresses of the linked list are not contiguous, performing ++ or — operations on raw pointers ismeaningless! Therefore, we need towrite our own iterator class to encapsulate raw pointers and satisfy our special ++ and — operations!

Basic Iterator Implementation

// The template can be upgraded again, let's start simple

template<class T>
class ListIterator {
public:
    // Renaming for convenience (type alias is a good tradition in C++)
    typedef ListNode<T> Node;
    typedef ListIterator<T> Self;

    Node* _node;  // Pointer to the current node

    // Constructor
    ListIterator(Node* x) : _node(x) {}

    // Prefix ++ ( ++it )
    Self& operator++()    // Note: return reference to support consecutive operations like ++++it
    {
        _node = _node->_next;  // Move to the next node
        return *this;          // Return current iterator reference
    }

    // Postfix ++ ( it++ )
    Self operator++(int)     // int parameter is only for distinguishing prefix and postfix
    {
        Self tmp(*this);       // Save current state (shallow copy is enough)
        _node = _node->_next;  // Move to the next node
        return tmp;            // Return state before moving
    }

    // Prefix -- ( --it )
    Self& operator--()    {
        _node = _node->_prev;  // Move to the previous node
        return *this;
    }

    // Postfix -- ( it-- )
    Self operator--(int)    {
        Self tmp(*this);       // Save current state
        _node = _node->_prev;  // Move to the previous node
        return tmp;
    }

    // Check for equality (compare pointer addresses)
    bool operator!=(const Self& it) const  // Adding const is more standard
    {
        return _node != it._node;
    }

    // Check for equality
    bool operator==(const Self& it) const    {
        return _node == it._node;
    }

    // Dereference operation (*it) returns a reference to the node's data (can be modified)
    T& operator*()     {
        return  _node->_data;
    }

    // -> operator overload (because only pointers can use ->, so return address/pointer)
    T* operator->()  // Compiler will perform -> omission
    {
        return &_node->_data;
    }
};

Analysis:

• ++it / it++: Moves the iterator to the next node (no longer just memory address +1!)
• –it / it–: Moves the iterator to the previous node
• it: Dereferences to get the current node’s data (returns reference, supports modification)
• it->: Accesses the current node’s data members (compiler will handle it automatically)
• == / !=: Compares whether two iterators point to the same node

Key Point: Prefix ++ returns a reference, while postfix ++ returns a temporary object! This is the standard practice for C++ iterators!

Generally, our iterators should also supportconst, otherwise, if we pass a non-modifiable list (const list), it will cause an error! Therefore, we need to write a const version of the iterator. If we write everything separately, thenmost of the code will be duplicated (++, –, ==, != are all the same), only<span><span>operator*()</span></span> and <span><span>operator->()</span></span> have different return values:

• Normal iterator: can modify data, returns <span><span>T&</span></span> and <span><span>T*</span></span>
• Const iterator: read-only data, returns <span><span>const T&</span></span> and <span><span>const T*</span></span>

Thus, we discover the pain point:Different iterators have most of the same code, only the return value types differ!!

Solution: Usetemplate parameter techniques to let the compiler handle the type differences!

// Upgraded iterator template (three parameters: data type, reference type, pointer type)
template<class T, class Ref, class Ptr>
class ListIterator {
public:
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self;

    Node* _node;
    ListIterator(Node* x) : _node(x) {}
    // Move operations (++, --) remain unchanged
    Self& operator++() { _node = _node->_next; return *this; }
    Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; }
    Self& operator--() { _node = _node->_prev; return *this; }
    Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; }
    // Comparison operations remain unchanged
    bool operator!=(const Self& it) const { return _node != it._node; }
    bool operator==(const Self& it) const { return _node == it._node; }
    // Key point: use template parameters Ref and Ptr to handle return value type differences
    Ref operator*() { return  _node->_data; }
    Ptr operator->() { return &_node->_data; }
};

Usage:

// Define iterator type aliases in the list class
typedef ListIterator<T, T&, T*> iterator;            // Normal iterator
typedef ListIterator<T, const T&, const T*> const_iterator;  // Const iterator

At this point, we have implemented the three core components of an STL-style linked list: node storage structure, container main framework, and safe traversal mechanism. Isn’t it simple?

Part3Function Implementation

Let’s continue discussing how to implement various functions of the list container.

3.1, begin() and end(): The Start and End of the Iterator

We need to clarify the starting and ending positions of the iterator. begin() is the next node of the head node, and end() is directly the head node itself.

Why? Because when traversing, after one full circle, we return to the head node, so checking if it’s the head node can determine whether to stop.

// Normal iterator
typedef ListIterator<T, T&, T*> iterator;
// Const iterator
typedef ListIterator<T, const T&, const T*> const_iterator;
iterator begin() { return _head->_next; }
iterator end() { return _head; }
const_iterator begin() const { return _head->_next; }
const_iterator end() const { return _head; }

Code Analysis:

• begin(): Returns an iterator pointing tothe first actual data node (i.e., the node next to the head node)
• end(): Returns an iterator pointing tothe sentinel node (head node), which is the end of the traversal!
• Why is end() the head node? Because our linked list isdoubly circular, after traversing the last node, its next points back to the head node!
• Const overload: provides read-only access for const list objects

The core idea: Use the sentinel node as a unified “end marker” to make the traversal logic of empty and non-empty lists completely consistent! In an empty list, begin() also equals end() (both point to the head node).

3.2, Insertion Operation: Inserting New Nodes into the Linked List

Tail insertion operation push_back()

void push_back(const T& x = T()) {
    // 1. Create a new node
    Node* node = new Node(x);
    // 2. Find the tail (the previous node of the head node is the tail node)
    Node* tail = _head->_prev;
    // 3. Perform the insertion operation (modify four pointers)
    node->_next = _head;     // New node's next points to head node
    node->_prev = tail;      // New node's prev points to the original tail node
    tail->_next = node;      // Original tail node's next points to the new node
    _head->_prev = node;     // Head node's prev also points to the new node
    // 4. Update size
    _size++;
}

Visualization of Insertion Logic:

Original tail node(tail)        New node(node)         Head node(_head)
    |                   |                   |
    |                   |                   |
    V                   V                   V
[prev] ---> [next]    [prev] ---> [next]    [prev] ---> [next]
    ^                   ^                   ^
    |                   |                   |
    |                   |                   | Original tail node's predecessor      Original tail node            New node's successor

Insert at any position insert()

void insert(iterator pos = begin(), T x = T()) {
    // 1. Create a new node
    Node* node = new Node(x);
    // 2. Find the previous and next nodes at the insertion position
    Node* prev = pos._node->_prev;  // Previous node of pos
    Node* next = pos._node;         // The pos node itself
    // 3. Handle the pointers of the new node
    node->_prev = prev;    // New node's predecessor points to the previous node of pos
    node->_next = next;    // New node's successor points to the pos node
    // 4. Handle the pointers of the previous and next nodes
    prev->_next = node;    // The next of the previous node points to the new node
    next->_prev = node;    // The predecessor of the pos node points to the new node
    // 5. Update size
    _size++;
}

The core idea: Complete the insertion by adjusting four pointers, without needing to move any existing elements.

Head insertion operation push_front(): Elegant Reuse

void push_front(const T& x = T()) {
    insert(begin(), x);  // Directly reuse the insert interface, inserting at the begin() position
}

Head insertion is essentially “inserting at the first position”, which can be completely achieved using insert(begin(), x) to avoid duplicate code!

3.3, Deletion Operation: Removing Nodes from the Linked List

Tail deletion operation pop_back()

void pop_back() {
    // 1. Find the tail node (the previous node of the head node)
    Node* tail = _head->_prev;
    // 2. Find the predecessor of the tail node (the new tail node)
    Node* prev = tail->_prev;
    // 3. Adjust pointers: bypass the tail node
    prev->_next = _head;    // New tail node's next points to head node
    _head->_prev = prev;    // Head node's prev points to the new tail node
    // 4. Free memory (important! Avoid memory leaks)
    delete tail;
    // 5. Update size
    _size--;
}

Head deletion operation pop_front()

void pop_front() {
    // 1. Find the next node of the head (the first actual node)
    Node* head = _head->_next;
    // 2. Find the second node (the new head node)
    Node* next = head->_next;
    // 3. Adjust pointers: bypass the head node
    _head->_next = next;    // Head node's next points to the second node
    next->_prev = _head;    // Second node's prev points to head node
    // 4. Free memory
    delete head;
    // 5. Update size
    _size--;
}

Delete at any position erase(): Returns the next valid iterator

iterator erase(iterator pos) {
    // 1. Get the node to be deleted and its previous and next nodes
    Node* cur = pos._node;    // Current node to be deleted
    Node* prev = cur->_prev;  // Previous node of the current node
    Node* next = cur->_next;  // Next node of the current node
    // 2. Adjust pointers: bypass the cur node
    prev->_next = next;    // The next of the previous node points to the next node
    next->_prev = prev;    // The prev of the next node points to the previous node
    // 3. Free memory
    delete cur;
    // 4. Update size
    _size--;
    // 5. Return the iterator of the next node (important!)
    return iterator(next);
}

Key Points:

• Memory Management: Always remember to delete the nodes that are removed, otherwise, memory leaks will occur!
• Iterator Invalidation Handling: Return the iterator of the next node after the deleted node, which is the standard practice in STL, allowing users to continue traversing safely
• Boundary Safety: Even when deleting the last node, it can be handled correctly (next is the head node at this time)

3.4, Copy Constructor: Deep Copying Linked List Data

list(const list<T>& l) {
    empty_init();  // First initialize an empty linked list (create sentinel node)
    // Traverse the original linked list, inserting data one by one
    iterator it = l.begin();
    while (it != l.end()) {
        push_back(*it);  // Copy data to the new linked list
        it++;
    }
}

If pursuing higher performance, a move constructor can be implemented to avoid unnecessary data copying!

3.5, Destructor: Cleaning Up All Resources

void clear() {
    // Release all data nodes one by one
    iterator it = begin();
    while (it != end()) {
        it = erase(it);  // erase will return the next valid iterator
    }
}
~list() {
    clear();      // First clear all data nodes
    // Release the head node space separately
    delete _head;     _head = nullptr;  // Avoid dangling pointer
}

3.6, Other Useful Functions

Return the size of the linked list

size_t size() const { return _size; }

Maintain a _size member variable, making the operation to get the sizeO(1) time complexity, rather than traversing to calculate!

Check if the linked list is empty

bool empty() {
    return _size == 0;  // Directly checking _size is the most reliable way
}

Although it can also be checked by judging<span><span>begin() == end()</span></span> to determine if it is empty, directly checking _size is more intuitive and efficient!

Clear the linked list data

void clear() {
    iterator it = begin();
    while (it != end()) {
        it = erase(it);  // Loop to delete all data nodes
    }
}

Reusability: Reuse clear() in the destructor to maintain code consistency!

3.7, Assignment Operator Overloading: Supporting Deep Copy and Move Semantics

In C++, if you do not explicitly define the assignment operator, the compiler will generate a default version, but for classes that manage resources (like our list), the default assignment operator simplycopies pointers by member, which can lead tomultiple objects sharing the same memory, potentially causingdouble free issues!

Copy assignment operator (deep copy version)

// Copy assignment operator (traditional method: copy first, then swap)
list<T>& operator=(const list<T>& other) {
    // 1. Prevent self-assignment (very important!)
    if (this != &other) {
        // 2. First clear the current linked list
        clear();
        // 3. Then deep copy the data from the other linked list
        iterator it = other.begin();
        while (it != other.end()) {
            push_back(*it);  // Add elements one by one
            it++;
        }
    }
    // 4. Return a reference to the current object to support chained assignment
    return *this;
}

Move assignment operator (efficient version introduced in C++11)

// Move assignment operator (C++11 move semantics)
list<T>& operator=(list<T>&& other) noexcept {
    // 1. Prevent self-assignment
    if (this != &other) {
        // 2. First clean up the resources of the current linked list
        clear();
        // 3. Directly "steal" the resources of other (efficiently transfer ownership)
        _head = other._head;
        _size = other._size;
        // 4. Set other to a valid but empty state (in line with move semantics conventions)
        other._head = nullptr;
        other._size = 0;
    }
    return *this;
}

3.8, Iterator Invalidation Handling

Iterator invalidation is an important but often overlooked issue. For the list, due to itsnon-contiguous memory layout, most operations will not invalidate all iterators, but there are special cases to be aware of!

In our previous implementation,

except for the iterator of the deleted node, other iterators remain valid after insertion and deletion operations! This is a significant advantage of the list over the vector!

Special Note: When calling <span><span>erase(iterator pos)</span></span>, the iterator pos of the deleted node will become invalid, but the function returnsthe iterator of the next valid node, which is the standard practice in STL!

// Our previous erase implementation has already considered this
iterator erase(iterator pos) {
    // ... [pointer adjustment and memory release code as before] ...
    // Key point: return the iterator of the next node to ensure iterator continuity
    return iterator(next);  // Users can safely continue using the returned iterator
}

Best Practice Recommendations (Advice for List Users)

// Typical safe usage pattern:
iterator it = myList.begin();
while (it != myList.end()) {
    if (condition to delete the current element) {
        // erase will return the next valid iterator, directly assign to it
        it = myList.erase(it);  // ✅ Safe!
    } else {
        // Only increment the iterator when not deleting
        ++it;  // ✅ Safe!
    }
}

3.9, Adding More STL-Compatible Interfaces

To make our handcrafted list more like the original STL version, we can add some commonly used STL-compatible interfaces!

Insert elements before a specified position (another form of insert)

// Insert elements before a specified iterator position (consistent with existing insert semantics)
// Our existing insert actually inserts before the pos position (STL standard practice)
// So this function can serve as an alias or be clearly documented
iterator insert_before(iterator pos, const T& x) {
    return insert(pos, x);  // Reuse existing implementation
}

Insert elements at the end of the linked list (another form of push_back)

// Another representation of tail insertion (exactly the same as push_back, just for interface richness)
void emplace_back(const T& x) {
    push_back(x);  // Current simple implementation, can be expanded for in-place construction later
}

Insert elements at the head of the linked list (another form of push_front)

// Another representation of head insertion (exactly the same as push_front, just for interface richness)
void emplace_front(const T& x) {
    push_front(x);  // Current simple implementation, can be expanded for in-place construction later
}

Find elements (convenient function, not STL standard but practical)

// Find elements (linear search, returns the iterator of the first matching element)
iterator find(const T& x) {
    iterator it = begin();
    while (it != end()) {
        if (*it == x)  // Assume T type supports == operator
        {
            return it;
        }
        ++it;
    }
    return end();  // Return end if not found
}

Understanding the underlying principles is more important than merely using the API. Once you have implemented a list yourself, using STL’s list will become much easier!

Previous Recommendations

Handcrafted Thread Pool: A Test of C++ Programmer’s Skills

Deconstructing Memory Pool: The Underlying Secrets of High-Performance C++ Programming

[Big Company Standard] Linux C/C++ Backend Advanced Learning Path

Click below to follow 【Linux Tutorials】 to get programming learning paths, project tutorials, resume templates, big company interview questions in PDF format, big company interview experiences, programming communication circles, and more.