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