SingleLinkedList.hpp

Go to the documentation of this file.

#ifndef LIST_SINGLE_LINKED_LIST_HPP
#define LIST_SINGLE_LINKED_LIST_HPP

#include "AbstractList.hpp"

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

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

    Entry *getNext() const { return next; };

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

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

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

    Entry *current = head;
    int i = 0;
    while (i != index) {
      current = current->getNext();
      i++;
    }
    return current->getValue(this->isMutable());
  }

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

  ~SingleLinkedList() { 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;

    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 a not empty list
        entry->setNext(head);
      }
      head = entry;
    } else if (index == this->getSize()) {
      // Add entry at not empty list but at last position
      tail->setNext(entry);
      tail = entry;
    } else {
      // Add entry to not empty list, somewhere in the middle
      Entry *current = head;
      for (int i = 0; i < index - 1; ++i) {
        current = current->getNext();
      }
      entry->setNext(current->getNext());
      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;
    // current is either the element to delete if index == 0, or the previous
    // element
    if (index != 0) {
      int i = 0;
      while (i < index - 1) {
        current = current->getNext();
        i++;
      }
    }

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

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

    delete toDelete;

    this->decreaseSize();

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

#endif// LIST_SINGLE_LINKED_LIST_HPP