Below is the header file for the two classes, Node and DDL:
class DLL; class Node{ int _data; Node* _prev; Node* _next; Node(int data, Node* prev=(Node*)0, Node* next=(Node*)0); friend class DLL; }; class DLL{ Node* _head; Node* _curr; Node* _tail; void copy(DLL& D); public: DLL(); DLL(DLL& D); virtual ~DLL(); bool isEmpty(); void append(int data); DLL& operator=(DLL& D); int remove(); // removes the current node and returns the data bool del(); // removes the current node returns false if is empty void insert(int data); // insterts before current bool goHead(); bool goTail(); bool goNext(); bool goPrev(); int visit(); // returns the current data };Here is the full implmentation of the two classes:
#include "dll.h" Node::Node(int data, Node* prev, Node* next){ _data = data; _prev = prev; _next = next; } DLL::DLL(){ _head = _tail = _curr = 0; } DLL::~DLL(){ while(del()); } void DLL::copy(DLL& D){ int curpos; for(curpos=0;D.goPrev();curpos++); // findout where is current if(!D.isEmpty()){ do{ this->append(D.visit()); }while(D.goNext()); } for(D.goHead(), this->goHead();curpos;D.goNext(), this->goNext(),curpos--); } DLL::DLL(DLL& D){ _head = _tail = _curr = 0; copy(D); } DLL& DLL::operator=(DLL& D){ if (this != &D){ while(del()); copy(D); } return *this; } void DLL::append(int data){ Node* newnode = new Node(data); if(_tail){ // ! empty _tail->_next = newnode; newnode->_prev = _tail; _tail = _curr = newnode; } else{ _tail = _curr = _head = newnode; } } int DLL::remove(){ int data = visit(); del(); return data; } bool DLL::del(){ bool ok = false; bool tailMoved = false; if(_curr){ ok = true; Node* todel = _curr; if(_curr->_next){ _curr->_next->_prev = _curr->_prev; } else{ _tail = _tail->_prev; tailMoved = true; } if(_curr->_prev){ _curr->_prev->_next = _curr->_next; } else{ _head = _head->_next; } if (!tailMoved){ _curr = _curr->_next; } else { _curr = _curr -> _prev; } delete todel; } return ok; } void DLL::insert(int data){ //Create a new node Node* newNode = new Node (data); if (_curr){ Node* temp = _curr -> _prev; //Connect the new node to the current node _curr -> _prev = newNode; newNode -> _next = _curr; if (temp){ //Connect the new node to the previous node temp -> _next = newNode; newNode -> _prev = temp; } else { _head = newNode; } } else { _head = _tail = newNode; } //Move current pointer to the new node _curr = newNode; } int DLL::visit(){ // retruns data of current return _curr ->_data; } bool DLL::goHead(){ bool success = false; if (!isEmpty()){ _curr = _head; success = true; } return success; } bool DLL::goTail(){ bool success = false; if (!isEmpty()){ _curr = _tail; success = true; } return success; } bool DLL::goNext(){ bool success = false; if (!isEmpty() && _curr -> _next){ _curr = _curr ->_next; success = true; } return success; } bool DLL::goPrev(){ bool success = false; if (!isEmpty() && _curr -> _prev){ _curr = _curr ->_prev; success = true; } return success; } bool DLL::isEmpty(){ return (!_curr)?true:false; }
No comments:
Post a Comment