Program Listing for File doubly_linked_list.h

↰ Return to documentation for file (data_structures/doubly_linked_list.h)

#ifndef DATA_STRUCTURES_DOUBLY_LINKED_LIST_H
#define DATA_STRUCTURES_DOUBLY_LINKED_LIST_H

#include <iostream>
#include <stdexcept>

namespace DataStructures {

template <typename T>
class DoublyLinkedList {
public:
        DoublyLinkedList()
        {
                head = new Node(T());
                tail = new Node(T());
                head->next = tail;
                tail->prev = head;
                size = 0;
        }

        ~DoublyLinkedList()
        {
                while (size > 0) {
                        del_first();
                }
                delete head;
                delete tail;
        }

        /* Insert functions */
        void add_first(const T& data)
        {
                Node* x = new Node(data);
                Node* temp = head->next;
                temp->prev = x;
                x->next = temp;
                head->next = x;
                x->prev = head;
                size++;
        }

        void add_last(const T& data)
        {
                Node* x = new Node(data);
                Node* temp = tail->prev;
                temp->next = x;
                x->prev = temp;
                x->next = tail;
                tail->prev = x;
                size++;
        }

        void add(int pos_index, const T& data)
        {
                check_position_index(pos_index);
                if (pos_index == int(size)) {
                        add_last(data);
                        return;
                }
                Node* p = get_node(pos_index);
                Node* temp = p->prev;
                Node* x = new Node(data);
                temp->next = x;
                x->prev = temp;
                x->next = p;
                p->prev = x;
                size++;
        }

        /* Delete functions */
        T del_first()
        {
                if (size == 0) {
                        throw std::out_of_range("No elements to remove");
                }
                Node* x = head->next;
                Node* temp = x->next;
                head->next = temp;
                temp->prev = head;
                T data = x->data;
                delete x;
                size--;
                return data;
        }

        T del_last()
        {
                if (size == 0) {
                        throw std::out_of_range("No elements to remove");
                }
                Node* x = tail->prev;
                Node* temp = tail->prev->prev;
                tail->prev = temp;
                temp->next = tail;
                T data = x->data;
                x->prev = nullptr;
                x->next = nullptr;
                delete x;
                size--;
                return data;
        }

        T del(int index)
        {
                check_element_index(index);
                Node* x = get_node(index);
                Node* prev = x->prev;
                Node* next = x->next;
                prev->next = next;
                next->prev = prev;
                T data = x->data;
                x->prev = nullptr;
                x->next = nullptr;
                delete x;
                size--;
                return data;
        }

        /* Get Functions */
        T get_first() const
        {
                if (is_empty()) {
                        throw std::out_of_range("No nodes in the list");
                }
                return head->next->data;
        }

        T get_last() const
        {
                if (is_empty()) {
                        throw std::out_of_range("No nodes in the list");
                }
                return tail->prev->data;
        }

        T get(int index)
        {
                Node* p = get_node(index);
                return p->data;
        }

        /* Set function */
        T set(int index, T data)
        {
                Node* p = get_node(index);
                T old_val = p->data;
                p->data = data;
                return old_val;
        }

        /* Utility functions */
        size_t get_size() const { return size; }

        bool is_empty() const { return size == 0; }

        void display() const
        {
                std::cout << "Size = " << size << '\n';
                Node* p = head->next;
                while (p != tail) {
                        std::cout << p->data << " <-> ";
                        p = p->next;
                }
                std::cout << "nullptr" << '\n';
                std::cout << '\n';
        }

private:
        struct Node {
                T data;
                Node* prev;
                Node* next;

                Node(T val) : data(val), prev(nullptr), next(nullptr) {}
        };
        Node* head;
        Node* tail;
        size_t size;

        Node* get_node(int index)
        {
                check_element_index(index);
                Node* p = head->next;
                if (index < int(size) / 2) {
                        p = head->next;
                        for (int i = 0; i < index; i++) {
                                p = p->next;
                        }
                } else {
                        p = tail->prev;
                        for (int i = int(size) - 1; i > index; i--) {
                                p = p->prev;
                        }
                }
                return p;
        }

        bool is_element_index(int index) const
        {
                return index >= 0 && index < int(size);
        }

        bool is_position_index(int pos_index) const
        {
                return pos_index >= 0 && pos_index <= int(size);
        }

        void check_element_index(int index) const
        {
                if (!is_element_index(index)) {
                        throw std::out_of_range(
                                "Element Index: " + std::to_string(index) +
                                ", Size: " + std::to_string(size));
                }
        }

        void check_position_index(int pos_index) const
        {
                if (!is_position_index(pos_index)) {
                        throw std::out_of_range(
                                "Position Index: " + std::to_string(pos_index) +
                                ", Size: " + std::to_string(size));
                }
        }
};

} // namespace DataStructures

#endif // DATA_STRUCTURES_DOUBLY_LINKED_LIST_H