Individual node of a list. Since we are building a doubly linked list each node has a prev and next pointer in addition to the data stored in the list.
template <typename Object>
class Node
{
public:
Object data;
Node *prev;
Node *next;
Node( const Object & d=Object (), Node *p=nullptr,
Node *n=nullptr)
:data(d),prev(p),next(n){}
};
The list class proper. We have to keep track of the head and tail. Note that we are using sentinel nodes.
template <typename Object>
class list{
private:
int _size;
Node<Object> *head;
Node<Object> *tail;
void init();
The iterator interface of a list. Declare the usual operations.
public:
class iterator{
protected:
Node<Object> *current;
public:
iterator(){}
iterator(Node<Object> *p):current(p){}
Object & operator*();
iterator & operator++();
iterator & operator++(int in);
iterator & operator--();
iterator & operator--(int in);
bool operator==(const iterator & rhs) ;
//the operator != is typically used in
// a for loop as itr!=list.end()
//since end and begin return a temp value
//then != should take a constant argument
bool operator!=(const iterator &rhs) ;
friend class list<Object>;
};
The list interface.
list();
list(const list &rhs);
~list();
list & operator=(const list &);
iterator begin() const;//it is used by constant lists, for example in copy constructor
iterator end() const;// same as above
int size() ;
bool empty();
void clear();
void push_front( const Object & x );//const so it can be used with literals
void push_back(const Object & x );//const so it can be used with literals
void pop_front( );
void pop_back( );
iterator insert( iterator itr, const Object & x ) ;//const so it can be used with literals
iterator erase( iterator );
};
Implementation of the iterator class
template<typename Object>
Object & list<Object>::iterator::operator*(){
return current->data;
}
template<typename Object>
typename list<Object>::iterator & list<Object>::iterator::operator++(){
current=current->next;
return *this;
}
template <typename Object>
typename list<Object>::iterator & list<Object>::iterator::operator++(int in){
current=current->next;
return *this;
}
template<typename Object>
typename list<Object>::iterator & list<Object>::iterator::operator--(){
current=current->prev;
return *this;
}
template<typename Object>
typename list<Object>::iterator & list<Object>::iterator::operator--(int in){
current=current->prev;
return *this;
}
template<typename Object>
bool list<Object>::iterator::operator==(const typename list<Object>::iterator & rhs) {
return current==rhs.current;
}
template<typename Object>
bool list<Object>::iterator::operator!=(const typename list<Object>::iterator & rhs) {
return (current!=rhs.current);
}
Implementation of the list class.
template<typename Object>
void list<Object>::init()
{
_size=0;
head = new Node<Object>{};
tail = new Node<Object>{};
head->next=tail;
head->prev=nullptr;
tail->prev=head;
tail->next=nullptr;
}
template<typename Object>
list<Object>::list()
{ init(); }
template<typename Object>
list<Object>::~list()
{
clear();
delete head;
delete tail;
}
Since head is a sentinel node then the first node is head->next;
template<typename Object>
typename list<Object>::iterator list<Object>::begin() const
{ return iterator(head->next);}
Recall that iterators are typically used in “half open” intervals, e.g. itr=list::begin() and itr!=list::end()
template<typename Object>
typename list<Object>::iterator list<Object>::end() const
{ return iterator(tail);}
template<typename Object>
int list<Object>::size()
{ return _size;}
template<typename Object>
bool list<Object>::empty()
{return size()==0;}
template <typename Object>
void list<Object>::clear(){
while(!empty())
erase(begin());
}
Push and pop make use of the insert and erase method.
template<typename Object>
void list<Object>::push_front(const Object & x){
insert( begin( ), x );
}
template<typename Object>
void list<Object>::push_back(const Object & x){
insert( end( ), x );
}
template<typename Object>
void list<Object>::pop_front(){
erase( begin() );
}
template<typename Object>
void list<Object>::pop_back(){
erase( --end() );
}
Copy constructor.
template<typename Object>
list<Object>::list(const list<Object> &rhs)
{ init();
for( list<Object>::iterator itr=rhs.begin();itr!=rhs.end();++itr)
push_back(*itr);
}
Assignment operator.
template<typename Object>
list<Object> & list<Object>::operator=(const list<Object> &rhs)
{
if(this==&rhs)
return *this;
clear();
for(typename list<Object>::iterator itr=rhs.begin();itr!=rhs.end();++itr)
push_back(*itr);
return *this;
}
Please refer to the lecture notes for an explanation of the insertion and deletion operations.
template<typename Object>
typename list<Object>::iterator list<Object>::insert( typename list<Object>::iterator itr,
const Object & x)
{
Node<Object> *q=itr.current;
_size++;
Node<Object> *newNode=new Node<Object>(x,q->prev,q);
q->prev->next=newNode;
q->prev=newNode;
return iterator(newNode);
}
template<typename Object>
typename list<Object>::iterator list<Object>::erase( typename list<Object>::iterator itr){
Node<Object> *t=itr.current;
iterator ret(t->next);
t->prev->next=t->next;// p---t---q;
t->next->prev=t->prev;
delete t;
_size--;
return ret;
}