====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:
<cli>
g++ -o d_main d_main.cpp -g
</cli>

===ltdl.hpp===
<code>
#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(); }
};
</code>

===d_main.cpp===
<code>
#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;
}
</code>