Saturday, October 8, 2011

Doubly Linked List

#include <iostream>

using namespace std;

class Node {
private:
Node();
Node(string s, Node* p, Node* n);
string body;
Node* prev;
Node* next;
friend class DoublyLinkedList;
};

Node::Node(){
};

Node::Node(string s, Node* p, Node* n){
body = s;
prev = p;
next = n;
};

class DoublyLinkedList{
public:
DoublyLinkedList();
~DoublyLinkedList();
void AddInFront(string s);
void RemoveInFront();
void AddInBack(string s);
void RemoveInBack();
void ShowAll();
private:
Node* head;
Node* trail;
};

DoublyLinkedList::DoublyLinkedList(){
head = new Node();
trail = new Node();
head->next = trail;
trail->prev = head;
};

DoublyLinkedList::~DoublyLinkedList(){
while (head->next != trail){
RemoveInFront();
}
delete head;
delete trail;
};

void DoublyLinkedList::AddInFront(string s){
Node* nxFrontNode = head->next;
Node* n = new Node(s, head, head->next);
head->next = n;
nxFrontNode->prev = n;
};

void DoublyLinkedList::RemoveInFront(){
if(head->next != trail){
Node* nxFrontNode = head->next;
Node* nnxFrontNode = nxFrontNode->next;
head->next = nnxFrontNode;
nnxFrontNode->prev = head;
delete nxFrontNode;
}
};

void DoublyLinkedList::AddInBack(string s){
Node* nxBackNode = trail->prev;
Node* n = new Node(s, trail->prev, trail);
trail->prev = n;
nxBackNode->next = n;
};

void DoublyLinkedList::RemoveInBack(){
if(trail->prev != head){
Node* nxBackNode = trail->prev;
Node* nnxBackNode = nxBackNode->prev;
trail->prev = nnxBackNode;
nnxBackNode->next = trail;
delete nxBackNode;
}
};

void DoublyLinkedList::ShowAll(){
Node* n = head->next;
while(n != trail){
cout << n -> body << endl;
n = n -> next;
}
}

int main()
{
cout << "- Doubly Linked List exercise -" << endl;

cout << "Create a new DoublyLinkedList: " << endl;
DoublyLinkedList myDoublyLinkedList;
myDoublyLinkedList.ShowAll();
cout << endl;

cout << "Remove nothing in a empty Doubly Linked List: " << endl;
myDoublyLinkedList.RemoveInFront();
myDoublyLinkedList.ShowAll();
cout << endl;

cout << "Insert something in Front: " << endl;
myDoublyLinkedList.AddInFront("ABC");
myDoublyLinkedList.AddInFront("DEFGH");
myDoublyLinkedList.AddInFront("I");
myDoublyLinkedList.AddInFront("JK");
myDoublyLinkedList.AddInFront("LMN");
myDoublyLinkedList.ShowAll();
cout << endl;

cout << "Remove something in Front: " << endl;
myDoublyLinkedList.RemoveInFront();
myDoublyLinkedList.RemoveInFront();
myDoublyLinkedList.ShowAll();
cout << endl;

cout << "Insert something in Back: " << endl;
myDoublyLinkedList.AddInBack("RST");
myDoublyLinkedList.AddInBack("UVW");
myDoublyLinkedList.AddInBack("XYZ");
myDoublyLinkedList.ShowAll();
cout << endl;

cout << "Remove something in Back: " << endl;
myDoublyLinkedList.RemoveInBack();
myDoublyLinkedList.RemoveInBack();
myDoublyLinkedList.ShowAll();
cout << endl;

cout << "end!" << endl;
return 0;
}


Doubly Linked List


No comments:

Post a Comment