Friday 15 March 2013

Dynamic Double Linked List

For week 10 of OOP344, I was asked to do the insert function of a dynamic double linked list. Insert works back inserting a new node before the current pointer.

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