## 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.

1 2 3 4 5 6 7 8 9 10 11 |
template <typename T> struct ListNode { ListNode(const T &e) : data(e), next(0), prev(0) { } T data; ListNode<T> *next; ListNode<T> *prev; }; |

List class

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
template <typename T> class list { public: list() : head_(0), tail_(0), size_(0) { } int size() { return size_; } private: ListNode<T> *head_; ListNode<T> *tail_; int size_; }; |

The list maintains pointers to […]