Linked List Class

Here is the node.h file where node class and methods definitions exist:

#ifndef NODE_H_
#define NODE_H_

template <typename Type>
class Node {
    Type data;
    Node<Type> * next;
    Node( ) { }
public:
    Node( Type );
    Type getData( ) const;
    Node * getNext( ) const;
    void setNext( Node<Type> * );
    ~Node( );
};

#endif

Here is the node.cpp file where Node Class methods are implemented.

template <typename Type>
Node<Type>::Node( Type _data ) {
    this->data = _data;
    this->next = 0;
}

template <typename Type>
Type Node<Type>::getData( ) const {
    return this->data;
}

template <typename Type>
Node<Type>* Node<Type>::getNext( ) const {
    return this->next;
}

template <typename Type>
void Node<Type>::setNext( Node<Type> *node ) {
    this->next = node;
}

template <typename Type>
Node<Type>::~Node( ) {
    this->next = 0;
}

Here is the list.h file where List Class and methods exist.

#ifndef LIST_H_
#define LIST_H_

#include "node.h"

template <typename Type>
class List {
    Node<Type> * head;
    Node<Type> * tail;
    unsigned int length;
public:
    List( ); 
    List( const List & );
    bool insert( Type data );
    bool remove( unsigned int );
    bool removeAtLast( unsigned int );
    void insertSorted( Type data );
    void reverse( );
    void print( std::ostream & out ) const;
    unsigned int size( ) const;
    bool isEmpty( ) const;
    Type get( unsigned int index ) const;
    const Node<Type> * getMidNode( ) const ; 
    const List<Type> & getFirstHalf( ) const ;
    const List<Type> & operator = ( const List<Type> & );
    List<Type> operator + ( const List<Type> & ) const;
    void operator += ( const List<Type> & );
    bool operator == ( const List<Type> & ) const;
    bool operator != ( const List<Type> & ) const;
    void clear( );
    ~List( );
};

#endif

Here is the list.cpp file where List Class methods are implemented:

#include "node.h"
template <typename Type>
List<Type>::List( ) {
    this->head = this->tail = 0;
    this->length = 0;
}

template <typename Type>
List<Type>::List( const List<Type> & list ) {
    this->head = this->tail = 0;
    this->length = 0;
    
    for ( Node<Type> * p = list.head; p; p = p->getNext( ) ) {
        this->insert( p->getData( ) );
    }
}

template <typename Type>
bool List<Type>::insert( Type data ) {
    Node<Type> * node = new Node<Type>( data );
    if ( 0 == node ) return false;
    if ( 0 == head ) {
        this->head = this->tail = node;
    } else {
        this->tail->setNext( node );
        this->tail = node;
    }
    this->length++;
    return true;
}

template <typename Type>
void List<Type>::insertSorted( Type data ) {
    if ( this->isEmpty( ) ) {
        this->insert( data );
    } else {
        Node<Type> * node = new Node<Type>( data );
        Node<Type> * p = head, * q; 
        while ( p->getNext( ) && data > p->getData( ) ) {
            q = p;
            p = p->getNext( );
        }
        if ( p == head ) { //insert beginning of the list
            node->setNext( head );
            head = node;
        } else if ( p->getNext( ) == 0 ) {  //insert end of the list
            p->setNext( node );
            this->tail = node;
        } else { //insert 
            node->setNext( p );
            q->setNext( node );
        }
        this->length++;
    }
}

template <typename Type>
void List<Type>::print( std::ostream & out ) const {
    for ( Node<Type> * p = head; p; p = p->getNext( ) ) {
        out << p->getData( ) << " - "; 
    }
    out << endl;
}

template <typename Type>
unsigned int List<Type>::size( ) const {
    return length;
}

template <typename Type>
Type List<Type>::get( unsigned int index ) const {
    if ( this->isEmpty( ) ) {
        throw "List is empty.";
    }

    if ( index >= this->length ) 
        throw "Index is out of boundary.";  
    
    int counter = 0;
    Node<Type> *p = this->head;
    while ( p && ( counter < index ) ) {
        counter++;
        p = p->getNext( );
    }
    return p->getData( );
}




template <typename Type>
void List<Type>::reverse( ) {
    Node<Type> * p, * q, * r;
    p = q = r = 0;
    r = this->head;
    while ( r ) {
        q = p;
        p = r;
        r = r->getNext( );
        p->setNext( q );
    }
    this->head = p;
}

template <typename Type>
const List<Type> & List<Type>::getFirstHalf( ) const {
    List<Type> *list = new List( );
    Node<Type> *p, *q;
    q = p = this->head;
    
    int counter = 1;
    while ( p ) {
        p = p->getNext( );
        if( counter++ % 2 == 0 ) {
            list->insert( q->getData( ) );
            q = q->getNext( );
        }
    }
    return *list;
}

template <typename Type>
const Node<Type> * List<Type>::getMidNode( ) const {
    Node<Type> *p, *q;
    q = p = this->head;
    
    int counter = 1;
    while ( p ) {
        p = p->getNext( );
        if( counter++ % 2 == 0 ) {
            q = q->getNext( );
        }
    }
    return q;
}


template <typename Type>
bool List<Type>::isEmpty( ) const {
    if ( 0 == this->head ) return true;
    return false;
}

/*********************************
** n between 0 and length - 1 
**********************************/
template <typename Type>
bool List<Type>::remove( unsigned int n ) {
    if ( n >= this->length ) return false;
    if ( this->length == 1 ) {
        this->clear( );
        return true;
    }
    
    int counter = 0;
    Node<Type> *p, *q;
    q = p = this->head;
    while ( counter++ < n && p ) {
        q = p;
        p = p->getNext( );
    }
    if ( counter <= n ) return false;
    
    if ( p == this->head ) {
        this->head = p->getNext( );
    } 
    else {
        q->setNext( p->getNext( ) );
    }
    if ( p == this->tail ) {
        this->tail = q;
    } 
    
    delete p;
    this->length--;
    return true;
}

/******************************
** n between 0 and length - 1
*******************************/
template <typename Type>
bool List<Type>::removeAtLast( unsigned int n ) {
    return this->remove( this->length - n - 1 );    
}

template <typename Type>
const List<Type> & List<Type>::operator =( const List<Type> & list ) {
    this->clear( );
    
    for ( Node<Type> * p = list.head; p; p = p->getNext( ) ) {
        this->insert( p->getData( ) );
    }

    return *this;
}

template <typename Type>
List<Type> List<Type>::operator +(const List<Type> & list) const {
    List<Type> result;
    
    for ( Node<Type> * p = this->head; p; p = p->getNext( ) ) {
        result.insert( p->getData( ) );
    }

    for ( Node<Type> * p = list.head; p; p = p->getNext( ) ) {
        result.insert( p->getData( ) );
    }

    return result;
}

template <typename Type>
void List<Type>::operator += ( const List<Type> & list ) {
    for ( Node<Type> *p = list.head; p; p = p->getNext( ) ) {
        this->insert( p->getData( ) );
    }
}

template <typename Type>
bool List<Type>::operator == ( const List<Type> & list ) const {
    if ( this->length != list.length ) return false;
    Node<Type> *p = this->head, *q = list.head;
    while ( p && q ) {
        if ( p->getData( ) != q->getData( ) ) return false;
        p = p->getNext( );
        q = q->getNext( );
    }
    if ( (p && !q) || (!p && q) ) return false;
    return true;
}

template <typename Type>
bool List<Type>::operator != ( const List<Type> & list ) const {
    return !( this->operator==( list ) );
}

template <typename Type>
void List<Type>::clear( ) {
    Node<Type> *p = this->head, *next;
    while ( p ) {
        next = p->getNext( );
        delete p;
        p = next;
    }
    this->head = 0;
    this->tail = 0;
    this->length = 0;
}

template <typename Type>
List<Type>::~List( ) {
    this->clear( );
}