Fork me on GitHub
Menu

Doubly LinkedList Implementation in C++

21 January 2017 - c++, data structures
Doubly LinkedList Implementation in C++

Here is my doubly linkedlist code. I coded this for my homework. List consists of nodes.

#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_

#include <iostream>
#include <cstddef>
#include <stdexcept>
#include <iomanip>

using namespace std;

template<class T>
class Node;

template<class T>
ostream &operator<<(ostream &out, const Node<T>& n);

/* node class for linked list */
template<class T>
class Node {

    private:
        Node<T> *prev;
        Node<T> *next;
        T data;

    public:
        /*** Do not modify the interface ***/
        Node();
        Node(const T& d);

        Node<T>* getNext() const;
        Node<T>* getPrev() const;
        T getData() const;
        T* getDataPtr();
        
        void setNext(Node<T> *newNext); 
        void setPrev(Node<T> *newPrev);
        void setData(const T& data);

        friend ostream &operator<< <> (ostream &out, const Node<T>& n);

        /*** Do not modify the interface ***/
};

/* TO-DO: method implementations here */
template<class T>
Node<T>::Node(){	 	  	  	  	     	    	    	 	
    prev=next=NULL;
}

template<class T>
Node<T>::Node(const T& d){
	data = d;
}

template<class T>
Node<T>* Node<T>::getNext() const{
	return next;
}

template<class T>
Node<T>* Node<T>::getPrev() const{
	return prev;
}

template<class T>
T Node<T>::getData() const{
	return data;
}

template<class T>
T* Node<T>::getDataPtr(){
	return *data;
}

template<class T>
void Node<T>::setNext(Node<T> *newNext){
	next = newNext;
	//newNext->prev = this;
}	 	  	  	  	     	    	    	 	

template<class T>
void Node<T>::setPrev(Node<T> *newPrev){
	prev = newPrev;
	//newPrev->next = this;
}

template<class T>
void Node<T>::setData(const T& data){
	this->data = data;
}
template<class T>
ostream &operator<<(ostream &out, const Node<T>& n){
    out << setfill('.') << setw(10) << (void*)n.prev 
        <<" <-| "<< (void*)&n <<" |-> " 
        << setfill('.') << setw(10) << (void*)n.next << " : "
        << n.data ; 
    return out;
};

template <class T> 
class LinkedList {
    private:
        /* pointer to the first node */
        Node<T>* front;
        /* pointer to the last node */
        Node<T>* back;

    public:
        /*** Do not modify the interface ***/
        LinkedList();
        LinkedList(const LinkedList<T>& ll);
        LinkedList<T>& operator=(const LinkedList<T>& ll);
        ~LinkedList();

        /* returns the first node of the linked list */
        Node<T>& getFront() const;
        /* returns the last node of the linked list */
        Node<T>& getBack() const;
        /* returns the node in given "pos"ition of the linked list */
        Node<T>& getNodeAt(int pos) const;
        /* returns the pointer of the node in given 
           "pos"ition of the linked list */
        Node<T>* getNodePtrAt(int pos) const;
        
        /* inserts a new node containing "data" 
           after the node "prev" 
           */
        void insert(Node<T>* prev, const T& data);
        /* inserts a new node containing "data" 
           at "pos"ition in the linked list 
           */
        void insertAt(int pos, const T& data);
        /* erases the given "node" from the linked list */
        void erase(Node<T>* node);
        /* erases the node in given "pos"ition from the linked list */
        void eraseFrom(int pos);
        /* clears the contents of the linked list */
        void clear();

        /* inserts a new node containing "data" 
           to the front of the linked list 
           */
        void pushFront(const T& data);
        /* inserts a new node containing "data" 
           to the back of the linked list
           */
        void pushBack(const T& data);

        /* removes the first node */
        void popFront();
        /* removes the last node */
        void popBack();

        /* returns true if the list is empty, false otherwise */
        bool isEmpty() const;
        /* returns the number of items in the list */
        size_t getSize() const;
        /* prints the contents of the linked list 
           one node data per line
           assumes the objects in the node have operator<< overloaded 
           */
        void print() const;

        /*** Do not modify the interface ***/
};

/* TO-DO: method implementations here */
template <class T> 
LinkedList<T>::LinkedList(){	 	  	  	  	     	    	    	 	
	front = NULL;
	back  = NULL;
} 

template <class T> 
LinkedList<T>::LinkedList(const LinkedList<T>& ll){
	front = NULL;
	clear();
		Node<T>* tmp = ll.getNodePtrAt(0);
    for(int i = 0; tmp != NULL; i++)
    {
        insertAt(i, tmp->getData());
        tmp = tmp->getNext();
    }
}

template <class T> 
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& ll){
	front = NULL;
	clear();
	Node<T>* tmp = ll.getNodePtrAt(0);
    for(int i = 0; tmp != NULL; i++)
    {
        insertAt(i, tmp->getData());
        tmp = tmp->getNext();
    }
}

template <class T> 
LinkedList<T>::~LinkedList(){
	Node<T>* tmp = front;
	while(tmp!=NULL) {
	tmp->setPrev(NULL);
	Node<T>* nextt = tmp->getNext();
	delete tmp;
	tmp = nextt;
	}	 	  	  	  	     	    	    	 	
	front=NULL;
	back=NULL;
}

template <class T> 
Node<T>& LinkedList<T>::getFront() const{
	return *front;
}

template <class T> 
Node<T>& LinkedList<T>::getBack() const{
	return *back;
}

template <class T> 
Node<T>& LinkedList<T>::getNodeAt(int pos) const{
	Node<T>* tmp;
	tmp = front;
	if(pos<0)
	throw domain_error("not possible");
	for(int i=0;i<pos;i++){
		if(tmp->getNext()==NULL)
		throw domain_error("not possible");
		tmp=tmp->getNext();
	}
	return *tmp;
}

template <class T> 
Node<T>* LinkedList<T>::getNodePtrAt(int pos) const{
	Node<T>* tmp;
	tmp =front;
	for(int i=0;i<pos;i++){	 	  	  	  	     	    	    	 	
		tmp=tmp->getNext();
	}
	return tmp;
}

template <class T> 
void LinkedList<T>::insert(Node<T>* prev, const T& data){
	Node<T>* newNode = new Node<T>;
	newNode->setData(data);
	newNode->setNext(prev->getNext());
	if(prev!=back)
	prev->getNext()->setPrev(newNode);
	else
	back=newNode;
	prev->setNext(newNode);
	newNode->setPrev(prev);
}

template <class T> 
void LinkedList<T>::insertAt(int pos, const T& data){
	Node<T>* newNode = new Node<T>;
	int nullchecker=0;
	newNode->setData(data);
	if(front == NULL){
	front = newNode;
	back = newNode;
	} else {
	Node<T>* tmp;
	tmp =front;
	for(int i=0;i<pos;i++){
		if(tmp->getNext()!=NULL)
		tmp=tmp->getNext();
		else
		nullchecker=1;
	}
	if(pos>getSize()){	 	  	  	  	     	    	    	 	
	back = newNode;
	}
	if(nullchecker!=1 and pos!=0){
	newNode->setNext(tmp);
	newNode->setPrev(tmp->getPrev());
	tmp->getPrev()->setNext(newNode);
	tmp->setPrev(newNode);
	} else if(pos!=0){
		tmp->setNext(newNode);
		newNode->setPrev(tmp);
		newNode->setNext(NULL);
	} else {
	newNode->setNext(tmp);
	tmp->setPrev(newNode);
	newNode->setPrev(NULL);
	front = newNode;
	}
	}
}

template <class T> 
void LinkedList<T>::erase(Node<T>* node){
	Node<T>* tmp;
	if ( node != front){
	if(getSize()!=1){
	tmp = node->getPrev();
	if(node->getNext()!=NULL){
	tmp->setNext(node->getNext());
	node->getNext()->setPrev(tmp);
	} else {
		tmp->setNext(NULL);
		back=tmp;
	}
	} else {
		front = NULL;
		back  = NULL;
	}	 	  	  	  	     	    	    	 	
	delete node;
	}
	else {
		tmp = node->getNext();
		tmp->setPrev(NULL);
		delete node;
		front = tmp;
	}
}

template <class T> 
void LinkedList<T>::eraseFrom(int pos){
	Node<T>* tmp;
	Node<T>* prev;
	tmp =front;
	if ( pos !=0){
	for(int i=0;i<pos;i++){
		tmp=tmp->getNext();
	}
	prev = tmp->getPrev();
	if(tmp->getNext()!=NULL){
	prev->setNext(tmp->getNext());
	tmp->getNext()->setPrev(prev);
	}
	else{
	prev->setNext(NULL);
	}

	delete tmp;
	}  else {
		prev = tmp->getNext();
		prev->setPrev(NULL);
		delete tmp;
		front = prev;
	}
}	 	  	  	  	     	    	    	 	

template <class T> 
void LinkedList<T>::clear(){
while(front != NULL)
	popFront();
}

template <class T> 
void LinkedList<T>::pushFront(const T& data){
	Node<T>* newNode = new Node<T>;
	newNode->setData(data);
	if (front != NULL) {
	newNode->setNext(front);
	front->setPrev(newNode);
	front = newNode;
	front->setPrev(NULL);
	} else {
	front = newNode;
	front->setPrev(NULL);
	back  = newNode;
	back->setNext(NULL);
	}
}

template <class T> 
void LinkedList<T>::pushBack(const T& data){
	Node<T>* newNode = new Node<T>;
	newNode->setData(data);
	if(front==NULL){
	front = newNode;
	front->setPrev(NULL);
	back  = newNode;
	front->setNext(back);
	back->setNext(NULL);
	back->setPrev(front);
	} else if(back!=NULL){	 	  	  	  	     	    	    	 	
	newNode->setPrev(back);
	back->setNext(newNode);
	newNode->setNext(NULL);
	}
	back = newNode;
}

template <class T> 
void LinkedList<T>::popFront(){
	Node<T>* tmp;
	if(front->getNext()!=NULL and back!=front){
	tmp=front->getNext();
	delete front;
	front = tmp;
	front->setPrev(NULL); } else {
		back = NULL;
		front = NULL;
		delete front;
	}
}

template <class T> 
void LinkedList<T>::popBack(){
	Node<T>* tmp;
	tmp=back->getPrev();
	tmp->setNext(back);
	delete back;
	back = tmp;
	back->setNext(NULL);
}

template <class T> 
bool LinkedList<T>::isEmpty() const{
	if (front == NULL)
	return 1;
	else
	return 0;
}	 	  	  	  	     	    	    	 	

template <class T> 
size_t LinkedList<T>::getSize() const{
	Node<T>* tmp;
	size_t x;
	tmp = front;
	x=0;
	if (tmp!=NULL ){
	while(tmp->getNext()!=NULL){
		tmp=tmp->getNext();
		x++;
	}
	x++;
	return x;
	}
	else
	return 0;
}

template <class T> 
void LinkedList<T>::print() const{
	Node<T>* tmp;
	int i=0;
	tmp = front;
	if (front != NULL){
	while(tmp->getNext()!=NULL or tmp->getNext()!=0){
		i++;
		cout << tmp->getData() << endl;
		tmp = tmp->getNext();
	}
	cout << tmp->getData() << endl;
	}
}

#endif

Leave a Reply

Your email address will not be published. Required fields are marked *