How is C++ STL list implemented internally

The previous article in this series called STLHow, showed how to implement STL Vector. This article will go into details about implementation of STL list.

Implementing STL List

The node

The STL list requires traversal in both the directions by means of forward and reverse iterator. Hence the list should be implemented as a doubly linked list. The node of the list is defined as below.

 List class

The list maintains pointers to head and tail of the list. Also the size of the list is stored explicitly. Because of the explicitly stored size, the size function can return the size of the list in constant time which would otherwise be O(n) had the list was required to be traversed to find out the size. The default constructor initializes all these private variables to zero.

Adding elements

 

 

Removing elements

 

 

Accessing elements

 

Destructor

 

Forward iterator

 

Reverse iterator