DoubleLinkedList.hpp

Go to the documentation of this file.

#ifndef LIST_DOUBLE_LINKED_LIST_HPP
#define LIST_DOUBLE_LINKED_LIST_HPP

#include "AbstractList.hpp"

template<typename T>
class DoubleLinkedList : public AbstractList<T> {
  class Entry : public AbstractList<T>::AbstractEntry {
    Entry *prev = nullptr;
    Entry *next = nullptr;

   public:
    ~Entry() {
      next = nullptr;
      prev = nullptr;
    }

    Entry *getNext() const { return next; }

    void setNext(Entry *nextEntry) { next = nextEntry; }

    Entry *getPrev() const { return prev; }

    void setPrev(Entry *prevEntry) { prev = prevEntry; }
  };

  Entry *head = nullptr;
  Entry *tail = nullptr;

 protected:
  T *getPointer(int index) override {
    if (this->isIndexOutOfBounds(index)) {
      return nullptr;
    }

    Entry *current;
    // optimize searching in large lists
    if (index > abs(this->getSize() / 2)) {
      current = tail;
      for (int i = this->getSize(); i > index + 1; --i) {
        current = current->getPrev();
      }
    } else {
      current = head;
      for (int i = 0; i < index; i++) {
        current = current->getNext();
      }
    }

    return current->getValue(this->isMutable());
  }

 public:
  explicit DoubleLinkedList<T>(bool mutableList = false)
      : AbstractList<T>(mutableList) {}

  ~DoubleLinkedList() { this->clear(); }

  using AbstractList<T>::addAtIndex;

  void addAtIndex(int index, T &value) override {
    // it is allowed, that index == this->getSize() to insert it behind the last
    // entry
    if (extendedIsIndexOutOfBounds(index)) {
      return;
    }

    Entry *entry = new Entry();
    entry->setValue(value, this->isMutable());

    if (index == 0) {
      if (this->getSize() == 0) {
        // Add entry to an empty list
        tail = entry;
      } else {
        // Add entry to not empty list
        entry->setNext(head);
        head->setPrev(entry);
      }
      head = entry;
    } else if (index == this->getSize()) {
      // Add entry at not empty list but at last position
      tail->setNext(entry);
      entry->setPrev(tail);
      tail = entry;
    } else {
      // Add entry to a not empty list, somewhere in the middle
      Entry *current;

      // optimize searching in large lists
      if (index >= abs(this->getSize() / 2)) {
        current = tail;
        for (int i = this->getSize(); i > index + 1; --i) {
          current = current->getPrev();
        }
        entry->setNext(current);
        entry->setPrev(current->getPrev());
        entry->getPrev()->setNext(entry);
        current->setPrev(entry);
      } else {
        current = head;
        for (int i = 0; i < index - 1; ++i) {
          current = current->getNext();
        }
        entry->setNext(current->getNext());
        entry->setPrev(current);
        entry->getNext()->setPrev(entry);
        current->setNext(entry);
      }
    }

    this->increaseSize();
  };

  void clear() override {
    if (this->getSize() == 0) {
      return;
    }

    Entry *current = head;
    Entry *next;
    for (int i = 0; i < this->getSize(); ++i) {
      next = current->getNext();

      delete current;
      current = next;
    }

    this->resetSize();
    head = nullptr;
    tail = nullptr;
  }

  void remove(int index) override {
    if (this->isIndexOutOfBounds(index)) {
      return;
    }

    Entry *current = head;

    // optimize searching in large lists
    if (index >= abs(this->getSize() / 2)) {
      if (index != 0) {
        current = tail;
        int i = this->getSize() - 1;
        while (i > index - 1) {
          current = current->getPrev();
          --i;
        }
      }
    } else {
      if (index != 0) {
        int i = 0;
        while (i < index - 1) {
          current = current->getNext();
          i++;
        }
      }
    }

    if (index == this->getSize() - 1) {
      tail = current;
    }

    if (index == 0) {
      head = current->getNext();
    }

    Entry *toDelete;
    if (index == 0) {
      toDelete = current;
      head = current->getNext();
    } else {
      toDelete = current->getNext();
      current->setNext(current->getNext()->getNext());
      if (current->getNext() != nullptr) {
        current->getNext()->setPrev(current);
      }
    }

    delete toDelete;

    this->decreaseSize();

    if (this->getSize() == 0) {
      head = nullptr;
      tail = nullptr;
    }
  }
};

#endif// LIST_DOUBLE_LINKED_LIST_HPP