std::list

A list in C++ is what is called a doubly linked list. Before you read this, please see the description of the singly linked list container std::forward_list.

A doubly linked list is one where each node stores the address of both the node after it and the node before it. This allows for significantly more functionality than a singly linked list. For example,

1. we can push or pop entries at both the front and the back of the doubly linked list, and
2. we can insert or erase an entry at a location indicated by the iterator, not after.

That is, it is a linked list where each node stores the address of the node before it, and the node after it.

If you look at the linked list class implementation we referred to in the above page, the major difference will be the definition of the Node class, where we will now have a "previous" pointer:

    struct Node {
      T     value_;
      Node *p_prev_;
      Node *p_next_;
    };

The functions std::push_front(...) and pop_front() will need to be updated to correctly initialize and manipulate p_prev_, and we will also need std::push_back(...) and pop_back() member functions.

The iterators will also require operators so that --itr and itr-- both return to the previous node in the linked list.

Also, to track the number of nodes in the class, we will need a private member variable of type std::size_t and this will be initialized to zero, incremented whenever a node is added to the linked list, and decremented whenever a node is removed from the linked list. This value will be accessed through a new member function:

template 
std::size_t Linked_list::size() const {
  return size_;
}

You can see the use of the std::list class at replit.com.

You will notice that there is not a member function to find(...) an entry.