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.
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
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 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
template <typename T> ListNode<T> *list<T>::insertInternal(const T &e, ListNode<T> *pos) { ListNode<T> *n = new ListNode<T>(e); size_++; // no operation below this should throw // as state of the list has changed and memory allocated n->next = pos; if(pos) { n->prev = pos->prev; pos->prev = n; } else { // pos is null that is at the very end of the list n->prev = tail_; tail_ = n; } if(n->prev) { n->prev->next = n; } else { // at the very begining of the list head_ = n; } return n; }
template <typename T> void list<T>::push_back(const T &e) { // inserts before the position, // 0 is the end() iterator // hence insert at the end insertInternal(e, 0); } template <typename T> void list<T>::push_front(const T &e) { // insert before the head insertInternal(e, head_); }
Removing elements
template <typename T> void list<T>::removeInternal(ListNode<T> *pos) { if(pos) { if(pos->prev) pos->prev->next = pos->next; if(pos->next) pos->next->prev = pos->prev; if(pos == head_) head_ = pos->next; if(pos == tail_) tail_ = pos->prev; delete pos; size_--; } }
template <typename T> void list<T>::pop_back() { removeInternal(tail_); } template <typename T> void list<T>::pop_front() { removeInternal(head_); }
Accessing elements
T &front() { return head_->data; } T &back() { return tail_->data; }
Destructor
template <typename T> list<T>::~list() { ListNode<T> *current( head_ ); while(current) { ListNode<T> *next( current->next ); delete current; current = next; } }
Forward iterator
class iterator { public: iterator(ListNode<T> *p=0) : pos_(p) { } T &operator*() { return pos_->data; } T *operator->() { return &(pos_->data); } bool operator!=(const iterator &rhs) { return this->pos_ != rhs.pos_; } iterator operator++(int) { pos_ = pos_->next; return *this; } iterator operator--(int) { pos_ = pos_->prev; return *this; } private: ListNode<T> *pos_; }; iterator begin() { return iterator(head_); } iterator end() { return iterator(0); }
Reverse iterator
class reverse_iterator { public: reverse_iterator(ListNode<T> *p=0) : pos_(p) { } T &operator*() { return pos_->data; } T *operator->() { return &(pos_->data); } bool operator!=(const reverse_iterator &rhs) { return this->pos_ != rhs.pos_; } reverse_iterator operator++(int) { pos_ = pos_->prev; return *this; } reverse_iterator operator--(int) { pos_ = pos_->next; return *this; } private: ListNode<T> *pos_; }; reverse_iterator rbegin() { return reverse_iterator(tail_); } reverse_iterator rend() { return reverse_iterator(0); }