Doubly Linked List

Question 1

DoublyLinkedList isEmpty

Answer 1

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

Question 2

DoublyLinkedList addNodeFront

Answer 2

void addNodeFront(T value)
    {
        Node<T>* newNode = new Node<T>(value);
        if (isEmpty())
        {
            head = tail = newNode;
        }
        else
        {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size++;
    }

Question 3

DoublyLinkedList addNodeBack

Answer 3

void addNodeBack(T value)
    {
        Node<T>* newNode = new Node<T>(value);
        if (isEmpty())
        {
            head = tail = newNode;
        }
        else
        {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        size++;
    }

Question 4

DoublyLinkedList addNodeAtPosition

Answer 4

void addNodeAtPosition(T value, int position)
    {
        if (position <= 0)
        {
            addNodeFront(value);
            return;
        }
        if (position >= size)
        {
            addNodeBack(value);
            return;
        }

        Node<T>* newNode = new Node<T>(value);
        Node<T>* current;

        if (position < size / 2)
        {
            current = head;
            for (int i = 0; i < position - 1; ++i)
            {
                current = current->next;
            }
        }
        else
        {
            current = tail;
            for (int i = size - 1; i > position; --i)
            {
                current = current->prev;
            }
        }

        newNode->next = current->next;
        newNode->prev = current;
        current->next->prev = newNode;
        current->next = newNode;
        size++;
    }

Question 5

DoublyLinkedList deleteNodeFront

Answer 5

void deleteNodeFront()
    {
        if (isEmpty())
        {
            cout << "Sarasas yra tuscias. Negalima pasalinti elemento." << endl;
            return;
        }

        Node<T>* temp = head;
        head = head->next;
        if (head != nullptr)
        {
            head->prev = nullptr;
        }
        else
        {
            tail = nullptr;
        }
        delete temp;
        size--;
    }

Question 6

DoublyLinkedList deleteNodeBack

Answer 6

void deleteNodeBack()
    {
        if (isEmpty())
        {
            cout << "Sarasas yra tuscias. Negalima pasalinti elemento." << endl;
            return;
        }

        Node<T>* temp = tail;
        tail = tail->prev;
        if (tail != nullptr)
        {
            tail->next = nullptr;
        }
        else
        {
            head = nullptr;
        }
        delete temp;
        size--;
    }

Question 7

DoublyLinkedList deleteNodeAtPosition

Answer 7

void deleteNodeAtPosition(int position)
    {
        if (position < 0 || position >= size)
        {
            cout << "Pozicija yra uz saraso ribu." << endl;
            return;
        }

        if (position == 0)
        {
            deleteNodeFront();
            return;
        }
        if (position == size - 1)
        {
            deleteNodeBack();
            return;
        }

        Node<T>* current;
        if (position < size / 2)
        {
            current = head;
            for (int i = 0; i < position; ++i)
            {
                current = current->next;
            }
        }
        else
        {
            current = tail;
            for (int i = size - 1; i > position; --i)
            {
                current = current->prev;
            }
        }

        current->prev->next = current->next;
        current->next->prev = current->prev;
        delete current;
        size--;
    }

Question 8

DoublyLinkedList search

Answer 8

void search(T value)
    {
        Node<T>* current = head;
        int index = 0;
        bool found = false;

        while (current != nullptr)
        {
            if (current->data == value)
            {
                cout << "Reiksme " << value << " rasta pozicijoje: " << index << endl;
                found = true;
            }
            current = current->next;
            index++;
        }

        if (!found)
        {
            cout << "Reiksme " << value << " nerasta sarase." << endl;
        }
    }

Question 9

DoublyLinkedList display

Answer 9

void display() const
    {
        if (isEmpty())
        {
            cout << "Sarasas yra tuscias." << endl;
            return;
        }

        Node<T>* current = head;
        while (current != nullptr)
        {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

Question 10

DoublyLinkedList reverse

Answer 10

void reverse()
    {
        if (isEmpty() || head == tail)
            return;

        Node<T>* current = head;
        Node<T>* temp = nullptr;

        while (current != nullptr)
        {
            temp = current->prev;
            current->prev = current->next;
            current->next = temp;
            current = current->prev;
        }

        temp = head;
        head = tail;
        tail = temp;
    }