user:dblanch1:portfolio:dataproject2_data_structures_-_doubly_linked_list_menu_programme
Doubly Linked List Menu Programme
The purpose of this project was to gain familiarity and become comfortable with manipulating doubly linked lists of our own creation. In addition, this and the singly linked variant were the first projects we split into multiple files. The functions I implemented build list, two display lists (one graphical representation, the other a 'detailed' view, actually printing the memory addresses involved), insert before/after, view, remove, delete, and grab node, swap nodes, sort list (in ascending order), and clear list. As this is an interactive programme, I won't be including the output here, but it's been thoroughly tested and anyone is free to compile it if they like. The source code for the two files is listed below, and the command to compile the programme is:
g++ -o d_main d_main.cpp -g
ltdl.hpp
#ifndef LTDL
#define LTDL
template <class T> struct DNode{
T data;
DNode *next, *prev;
DNode(){ next = NULL; prev = NULL; }
};
template <class T> class DList{
private:
DNode<T>* head, * tail;
unsigned long long capacity;
bool destroy;
public:
DList(){ head = NULL; tail = NULL; capacity = 0; destroy = true; }
unsigned long long get_capacity(){ return capacity; }
void set_destroy(bool d){ destroy = d; }
void reset(){ capacity = 0; head = NULL; tail = NULL; }
DNode<T>* find_node(unsigned long long i){
if (capacity == 0) return NULL;
else if (i == 0) return this->head;
else if (i == (capacity - 1)) return this->tail;
else if ((i >= 0) && (i < capacity)){
DNode<T>* curr = head;
for (unsigned long long c = 0; c < i; c++){
curr = curr->next;
}
return curr;
}
else return NULL;
}
DNode<T>* grab_node(unsigned long long i){
if ((i >= 0) && (i < capacity)){
DNode<T>* curr = find_node(i);
if (curr != NULL){
if (curr->next != NULL) curr->next->prev = curr->prev;
if (curr->prev != NULL) curr->prev->next = curr->next;
if (curr == head) head = curr->next;
if (curr == tail) tail = curr->prev;
capacity--;
return curr;
}
}
else return NULL;
}
bool remove_node(DNode<T>* node){
DNode<T>* curr = head;
while (curr != NULL){
if (curr == node){
break;
}
curr = curr->next;
}
if (curr != NULL){
if (curr->prev != NULL) curr->prev->next = curr->next;
if (curr->next != NULL) curr->next->prev = curr->prev;
return false;
}
else return true;
}
bool delete_node(unsigned long long i){
DNode<T>* tmp = grab_node(i);
if (tmp != NULL){
capacity--;
delete tmp;
return false;
}
else return true;
}
bool eliminate_node(DNode<T>* node){
if (remove_node(node) == false){
delete node;
return false;
}
else return true;
}
void clear(){
DNode<T>* curr = head;
DNode<T>* curr_n = NULL;
if (curr != NULL) curr_n = curr->next;
while (curr != NULL){
delete curr;
curr = curr_n;
if (curr != NULL) curr_n = curr->next;
}
reset();
}
bool prepend_node(DNode<T>* node){
if (node != NULL){
if (head != NULL){
head->prev = node;
}
node->next = head;
head = node;
head->prev = NULL;
capacity++;
return false;
}
else return true;
}
bool append_node(DNode<T>* node){
if (node != NULL){
if (tail != NULL){ tail->next = node; }
if (head == NULL){ head = node; }
else { node->prev = tail; }
tail = node;
capacity++;
return false;
}
else return true;
}
bool insert_before(unsigned long long i, DNode<T>* node){
if ((i >= 0) && ((i < capacity) || (capacity == 0))){
if (head == NULL){
head = node;
head->prev = NULL;
head->next = NULL;
tail = node;
capacity++;
return false;
}
else {
DNode<T>* curr = find_node(i);
if (curr != NULL){
if (curr == head){
node->prev = NULL;
node->next = head;
head->prev = node;
head = node;
capacity++;
return false;
}
else {
node->next = curr;
node->prev = curr->prev;
if (curr->prev != NULL) curr->prev->next = node;
curr->prev = node;
capacity++;
return false;
}
}
}
}
return true;
}
bool insert_before(DNode<T>* dest, DNode<T>* src){ }
bool insert_after(unsigned long long i, DNode<T>* node){
if ( (i >= 0) && ((i < capacity) || (capacity == 0)) ){
if (head == NULL){
node->prev = NULL;
node->next = NULL;
head = node;
tail = node;
capacity++;
return false;
}
else {
DNode<T>* curr = find_node(i);
if (curr != NULL){
if (curr == tail){
node->prev = tail;
node->next = NULL;
tail->next = node;
tail = node;
capacity++;
return false;
}
else {
node->prev = curr;
node->next = curr->next;
if (curr->next != NULL) curr->next->prev = node;
curr->next = node;
capacity++;
return false;
}
}
}
}
else return true;
}
bool insert_after(DNode<T>* dest, DNode<T>* src){ }
bool swap_nodes(DNode<T>* node1, DNode<T>* node2){
if (((node1 != NULL)&&(node2 != NULL)) && (node1 != node2)){
DNode<T> tmp;
if (node1->next == node2){
tmp.prev = node1->prev;
tmp.next = node1->next;
node1->next = node2->next;
if (node2->next != NULL) node2->next->prev = node1;
else tail = node1;
node2->next = node1;
node2->prev = node1->prev;
if (node1->prev != NULL) node1->prev->next = node2;
else head = node2;
node1->prev = node2;
return false;
}
else if (node2->next == node1){
tmp.prev = node2->prev;
tmp.next = node2->next;
node2->next = node1->next;
if (node1->next != NULL) node1->next->prev = node2;
else tail = node2;
node1->next = node2;
node1->prev = node2->prev;
if (node2->prev != NULL) node2->prev->next = node2;
else head = node1;
node2->prev = node1;
return false;
}
else{
tmp.prev = node1->prev;
tmp.next = node1->next;
node1->next = node2->next;
node1->prev = node2->prev;
if (node1->next != NULL) node1->next->prev = node1;
if (node1->prev != NULL) node1->prev->next = node1;
node2->next = tmp.next;
node2->prev = tmp.prev;
if (node2->next != NULL) node2->next->prev = node2;
if (node2->prev != NULL) node2->prev->next = node2;
if (head == node1) head = node2;
else if (head == node2) head = node1;
if (tail == node1) tail = node2;
else if (tail == node2) tail = node1;
return false;
}
}
return true;
}
bool swap_nodes(unsigned long long a, unsigned long long b){
if ((a!=b) && ((a>=0)&&(a<capacity)) && ((b>=0)&&(b<capacity))){
DNode<T>* A = find_node(a);
DNode<T>* B = find_node(b);
return swap_nodes(A, B);
}
else return true;
}
void sort(){
DNode<T>* lowest = NULL;
DNode<T>* curr = NULL;
DNode<T>* new_head = NULL;
DNode<T>* new_tail = NULL;
unsigned long long tmp_cap = capacity;
while (tmp_cap > 0){
curr = head;
lowest = head;
while (curr != NULL){
if (curr->data < lowest->data){
lowest = curr;
}
curr = curr->next;
}
if (lowest->prev != NULL){
lowest->prev->next = lowest->next;
}
else {
head = lowest->next;
}
if (lowest->next != NULL){
lowest->next->prev = lowest->prev;
}
else {
tail = lowest->prev;
}
tmp_cap--;
if (new_head == NULL){
new_head = lowest;
new_head->prev = NULL;
new_head->next = NULL;
new_tail = new_head;
}
else {
if (new_head->next == NULL){
new_head->next = lowest;
lowest->prev = new_head;
new_tail = lowest;
}
else {
new_tail->next = lowest;
lowest->prev = new_tail;
new_tail = lowest;
}
}
}
head = new_head;
tail = new_tail;
}
void append_list(DList<T> &other){
DNode<T>* other_head = other.find_node(0);
DNode<T>* other_tail = other.find_node(other.get_capacity - 1);
other_head->prev = tail;
tail->next = other_head;
tail = other_tail;
other.reset();
}
~DList(){ if (destroy == true) clear(); }
};
d_main.cpp
#include <iostream>
#include "ltdl.hpp"
int main(){
DList<double> dlist;
char option = 'Q';
bool running = true;
std::cout << " *** Linked Lists Demo Programme ***"
<< std::endl;
while (running == true){
std::cout << std::endl;
std::cout << " *** Options ***" << std::endl;
std::cout << "(B) - Build List" << std::endl;
std::cout << "(P) - Print List" << std::endl;
std::cout << "(D) - Print Detailed List" << std::endl;
std::cout << "(I) - Insert New Node Before" << std::endl;
std::cout << "(i) - Insert New Node After" << std::endl;
std::cout << "(p) - Prepend New Node" << std::endl;
std::cout << "(A) - Append New Node" << std::endl;
std::cout << "(V) - View Node" << std::endl;
std::cout << "(R) - Remove Node" << std::endl;
std::cout << "(G) - Grab Node" << std::endl;
std::cout << "(d) - Delete Node" << std::endl;
std::cout << "(S) - Swap Nodes" << std::endl;
std::cout << "(s) - Sort List (Ascending)" << std::endl;
std::cout << "(C) - Clear List" << std::endl;
std::cout << "(Q) - Quit Demo Programme" << std::endl;
std::cout << std::endl << "Choice: ";
std::cin >> option;
if (option == 'P'){
std::cout << std::endl;
DNode<double>* curr = dlist.find_node(0);
unsigned long long c = 0;
std::cout << "NULL ";
while (curr != NULL){
std::cout << "<-> (" << c << "[" << curr->data << "]) ";
curr = curr->next;
if (curr == NULL) std::cout << "<-> NULL";
c++;
}
std::cout << std::endl;
}
else if (option == 'D'){
std::cout << std::endl;
DNode<double>* curr = dlist.find_node(0);
unsigned long long c = 0;
std::cout << " list.capacity: " << dlist.get_capacity() << std::endl;
std::cout << " list.head: " << dlist.find_node(0) << std::endl;
while (curr != NULL){
std::cout << "Node[" << c << "]->value: " << curr->data << std::endl;
std::cout << "Node[" << c << "] : " << curr << std::endl;
std::cout << "Node[" << c << "]->prev : " << curr->prev << std::endl;
std::cout << "Node[" << c << "]->next : " << curr->next << std::endl;
if (curr->next == NULL){
std::cout << " list.tail: " << curr <<std::endl;
}
std::cout << std::endl;
curr = curr->next;
c++;
}
std::cout << std::endl;
}
else if (option == 'V'){
unsigned long long i = 0;
std::cout << "Node to view: ";
std::cin >> i;
DNode<double>* tmp = dlist.find_node(i);
std::cout << "Node: " << tmp << std::endl;
if (tmp != NULL){
std::cout << "Node value: " << tmp->data << std::endl;
std::cout << "Node->next: " << tmp->next << std::endl;
std::cout << "Node->prev: " << tmp->prev << std::endl;
}
}
else if (option == 'B'){
unsigned long long c = 0;
bool build = true;
char cont = 'y';
while (build == true){
std::cout << "Node[" << c << "] value? : ";
DNode<double>* tmp = new DNode<double>;
std::cin >> tmp->data;
dlist.append_node(tmp);
std::cout << "Add more nodes? y/n: ";
std::cin >> cont;
if (cont != 'y') build = false;
c++;
}
}
else if (option == 'A'){
DNode<double>* tmp = new DNode<double>;
std::cout << "New node value: ";
std::cin >> tmp->data;
dlist.append_node(tmp);
}
else if (option == 'p'){
DNode<double>* tmp = new DNode<double>;
std::cout << "New node value: ";
std::cin >> tmp->data;
dlist.prepend_node(tmp);
}
else if (option == 'C'){
dlist.clear();
}
else if (option == 'Q'){
std::cout << "Demo programme is exiting. Good-bye." << std::endl;
return false;
}
else if (option == 's'){
dlist.sort();
}
else if (option == 'd'){
unsigned long long i = 0;
std::cout << "Node to delete: ";
std::cin >> i;
dlist.delete_node(i);
}
else if (option == 'G'){
unsigned long long i = 0;
std::cout << "Node to grab: ";
std::cin >> i;
DNode<double>* tmp = dlist.grab_node(i);
std::cout << "Grabbed node : " << tmp << std::endl;
if (tmp != NULL){
std::cout << "Grabbed node value: " << tmp->data << std::endl;
std::cout << "Grabbed node->next: " << tmp->next << std::endl;
std::cout << "Grabbed node->prev: " << tmp->prev << std::endl;
std::cout << "Deleting grabbed node..." << std::endl << std::endl;
delete tmp;
}
}
else if (option == 'I'){
DNode<double>* tmp = new DNode<double>;
unsigned long long i = 0;
std::cout << "Node to insert before: ";
std::cin >> i;
std::cout << "Value of new node: " << std::endl;
std::cin >> tmp->data;
bool fail = dlist.insert_before(i, tmp);
if (fail == true){
std::cout << "Sorry. Cannot insert before the specified node."
<< std::endl;
}
}
else if (option == 'i'){
DNode<double>* tmp = new DNode<double>;
unsigned long long i = 0;
std::cout << "Node to insert after: ";
std::cin >> i;
std::cout << "Value of new node: ";
std::cin >> tmp->data;
bool fail = dlist.insert_after(i, tmp);
if (fail == true){
std::cout << "Sorry. Cannot insert after the specified node."
<< std::endl;
}
}
else if (option == 'S'){
bool fail = false;
unsigned long long a = 0;
unsigned long long b = 0;
std::cout << "Node 1: ";
std::cin >> a;
std::cout << "Node 2: ";
std::cin >> b;
if ((a>=0)&&(a<dlist.get_capacity()) && (b>=0)&&(b<dlist.get_capacity())){
DNode<double>* A = dlist.find_node(a);
DNode<double>* B = dlist.find_node(b);
fail = dlist.swap_nodes(A, B);
} else fail = true;
if (fail == true){
std::cout << "Sorry. There was an error swapping the specified nodes."
<< " The results may not be what you expected." << std::endl;
}
}
}
return false;
}
user/dblanch1/portfolio/dataproject2_data_structures_-_doubly_linked_list_menu_programme.txt · Last modified: 2013/10/30 04:45 by dblanch1