Program Listing for File singly_linked_list.h

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

#ifndef DATA_STRUCTURES_SINGLY_LINKED_LIST_H
#define DATA_STRUCTURES_SINGLY_LINKED_LIST_H

#include <iostream>
#include <stdexcept>

namespace DataStructures {

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

        ~SinglyLinkedList()
        {
                Node* cur = head;
                while (cur != nullptr) {
                        Node* next = cur->next;
                        delete cur;
                        cur = next;
                }
        }

        /* Add functions */
        void add_first(const T& data)
        {
                Node* x = new Node(data);
                x->next = head->next;
                head->next = x;
                if (size == 0) {
                        tail = x;
                }
                size++;
        }

        void add_last(const T& data)
        {
                Node* x = new Node(data);
                tail->next = x;
                tail = 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* prev = head;
                for (int i = 0; i < pos_index; i++) {
                        prev = prev->next;
                }
                Node* x = new Node(data);
                x->next = prev->next;
                prev->next = x;
                size++;
        }

        /* Erase functions */
        T del_first()
        {
                if (is_empty()) {
                        throw std::out_of_range("No nodes to remove");
                }
                Node* first = head->next;
                head->next = first->next;
                if (size == 1) {
                        tail = head;
                }
                size--;
                T data = first->data;
                delete first;
                return data;
        }

        T del_last()
        {
                if (is_empty()) {
                        throw std::out_of_range("No nodes to remove");
                }
                Node* prev = head;
                while (prev->next != tail) {
                        prev = prev->next;
                }
                T data = tail->data;
                delete tail;
                prev->next = nullptr;
                tail = prev;
                size--;
                return data;
        }

        T del(int index)
        {
                check_element_index(index);
                Node* prev = head;
                for (int i = 0; i < index; i++) {
                        prev = prev->next;
                }
                Node* x = prev->next;
                prev->next = x->next;
                if (index == int(size) - 1) {
                        tail = prev;
                }
                size--;
                T data = x->data;
                delete x;
                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->data;
        }

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

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

        /* 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* next;
                Node(T val) : data(val), next(nullptr) {}
        };
        Node* head;
        Node* tail;
        size_t size;

        Node* get_node(int index) const
        {
                check_element_index(index);
                Node* p = head->next;
                for (int i = 0; i < index; i++) {
                        p = p->next;
                }
                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(
                                "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(
                                "Index: " + std::to_string(pos_index) +
                                ", Size: " + std::to_string(size));
                }
        }
};

} // namespace DataStructures

#endif // DATA_STRUCTURES_LINKED_LIST_H