Doubly Circular Linked List

CDLL.cc

/**
 * Circular Double Linked List
 *
 */

#include "iostream"

using namespace std;

struct Node {
    unsigned int id;
    string name;
    Node *previous;
    Node *next;

    Node(unsigned int id, string name) :
            id(id), name(name) {}
};

class CDLL {
private:
    struct Node *head = nullptr;
    struct Node *tail = nullptr;

    void insert(unsigned int id, string name, bool at_start = true) {
        struct Node *n = new Node(id, name);

        if (head == nullptr) {
            head = n;
            tail = n;

            n->previous = n;
            n->next = n;

            return;
        }

        n->next = head;
        n->previous = head->previous;
        head->previous->next = n;
        head->previous = n;

//        n->next = head;
//        n->previous = tail;
//        head->previous = n;
//        tail->next = n;

        if (at_start)
            head = n;
        else
            tail = n;
    }

public:
    CDLL() {
        head = nullptr;
        tail = nullptr;
    }

    void insert_at_start(unsigned int id, string name) {
        insert(id, name, true);
    }

    void insert_at_end(unsigned int id, string name) {
        insert(id, name, false);
    }

    bool insert_at(unsigned int needle, unsigned int id, string name) {
        if (head == nullptr)
            return false;

        Node *tmp = head;

        do {
            if (tmp->id == needle) {
                Node *n = new Node(id, name);

                n->previous = tmp->next->previous;
                n->next = tmp->next;
                tmp->next->previous = n;
                tmp->next = n;

                if (tmp == tail)
                    tail = n;

                return true;
            }

            tmp = tmp->next;
        } while (tmp != head);

        return false;
    }

    int delete_node(unsigned int id) {
        if (head == nullptr)
            return 0;

        Node *current = head;

        do {
            if (current->id == id) {

                if (current == head || current == tail) {
                    head = current->next;
                    tail = current->previous;
                }

                current->previous->next = current->next;
                current->next->previous = current->previous;
                delete current;

                return 1;
            }

            current = current->next;
        } while(current != head);

        return 0;
    }

    void sort() {
        Node *current = nullptr;
        bool swapped;

        do {
            current = head;
            swapped = false;

            while (current->next != head) {
                if (current->id < current->next->id) {

                    if (current == head)
                        head = current->next;

                    Node *tmp = current->previous->next;

                    current->previous->next = current->next;
                    current->next->previous = current->previous;
                    current = current->next;

                    tmp->previous = current->next->previous;
                    tmp->next = current->next;

                    current->next = tmp;
                    tmp->next->previous = tmp;

                    if (current == tail)
                        tail = current->next;

                    swapped = true;
                }

                current = current->next;
            }

        } while (swapped);
    }

    void print() {
        if (head == nullptr)
            return;

        Node *tmp = head;

        do {
            cout << "previous: " << tmp->previous->id << " [" << tmp->id << "] next: " << tmp->next->id;
            // cout << tmp->id << ' ' << tmp->name << endl;

            if (tmp == head)
                cout << " Head";
            if (tmp == tail)
                cout << " tail";

            cout << endl;

            tmp = tmp->next;
        } while (tmp != head);
    }

    ~CDLL() {
        Node *current = head;
        do {
            Node *tmp = current;
            delete tmp;
            current = current->next;
        } while (current != head);

        head = nullptr;
        tail = nullptr;
    }
};

int main() {
    CDLL cdll;

    cdll.insert_at_start(11, "Eleven");
    cdll.insert_at_start(5, "five");
    cdll.insert_at_start(2, "two");
    cdll.insert_at_start(1, "one");
    cdll.insert_at_start(4, "four");
    cdll.insert_at_start(3, "three");
    cdll.insert_at_start(6, "six");
    cdll.insert_at_end(7, "seven");
    cdll.insert_at_end(12, "twelve");

    cdll.insert_at(4, 8, "eight");
    cdll.insert_at(6, 9, "nine");
    cdll.insert_at(7, 10, "ten");

    cdll.delete_node(12);
    cdll.delete_node(9);
    cdll.delete_node(1);
    cdll.delete_node(13);

    cdll.print();

    cdll.sort();
    cout << endl;
    cdll.print();

    return 0;
}

Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by the previous and next pointer and the last node points to the first node by the next pointer and also the first node points to the last node by the previous pointer.

What Are the Types of Linked Lists?

• Singly linked lists.
• Doubly linked lists.
• Circular linked lists.
• Circular doubly linked lists.