AlternativeLinkedList.h

#ifndef ALTERNATIVELINKEDLIST_H
#define ALTERNATIVELINKEDLIST_H

#include "Item.h"
#include "List.h"

/*
 * Deklariert hier die AlternativeLinkedList ohne Dummy-Element.
 *
 * Diese Liste soll keine FreeList verwenden, denn die move-Methoden
 * erlauben es in dieser Implementierung nicht Elemente aus anderen
 * Listen einzufügen (dafür benötigten wir einen Pointer auf die Liste,
 * aus denen die Elemente stammen).
 *
 * In CodeBlocks könnt ihr die Liste bauen und testen, indem ihr in der
 * Target-DropDown-Liste "AlternativeLinkedList" auswählt.
 */

class AlternativeLinkedList : public List {
  Item* _head;

 public:
  AlternativeLinkedList() : _head{nullptr} {}

  void splice(Item* a, Item* b, Item* t) override {
    // lel
  }

  Item* head() override { return _head; }
  bool isEmpty() override { return _head == nullptr; }
  Item* first() override { return _head; }

  Item** internal_last() {
    /*
     * Returns pointer to pointer to the last element.
     * The returned element may or may not exist, depending on whether the list
     * is empty or not.
     */
    Item** p = &_head;
    for (; *p && (*p)->next; p = &(*p)->next)
      ;
    return p;
  }

  /*
   * Returns a place to insert a new Element at the back of a list.
   */
  Item** internal_next() {
    Item** p = internal_last();
    /*
     * If `*p` is non null, there must be a `next` pointer in it which is null.
     * We then return the address of that so that when we do `*internal_next() =
     * new Item();` we initialize the next pointer directly.
     *
     * If `*p` is null, then there is nothing to initialize and we just return
     * `p`.
     */
    return *p ? &(*p)->next : p;
  }

  Item* last() override { return *internal_last(); }

  void moveAfter(Item* b, Item* a) override {
    // Remove b from the list.
    remove(b);
    // Place `b` between `a` and `a->next`.
    b->next = a->next;
    a->next = b;
  }

  void moveToFront(Item* b) override {
    remove(b);
    b->next = _head;
    _head = b;
  }

  void moveToBack(Item* b) override { moveAfter(b, last()); }

  /*
   * prev returns a pointer to the `next` element of the thing before `b`.
   * Setting *prev thus overwrites that next element.
   */
  Item** prev(Item* b) {
    Item** p = &_head;
    for (; *p && *p != b; p = &(*p)->next)
      ;
    return p;
  }

  void remove(Item* b) override { *prev(b) = b->next; }

  void popFront() override { remove(_head); }
  void popBack() override { remove(last()); }

  Item* insertAfter(int x, Item* a) override {
    Item* b = new Item(x, nullptr);
    moveAfter(b, a);
    return b;
  }

  Item* insertBefore(int x, Item* a) override {
    Item** p = prev(a);
    *p = new Item(x, *p);
    return *p;
  }

  void pushFront(int x) override { _head = new Item(x, _head); }

  void pushBack(int x) override { *internal_next() = new Item(x, nullptr); }

  Item* find(int x) override {
    Item* p = _head;
    for (; p && p->e != x; p = p->next)
      ;
    return p;
  }

  int size() override {
    int i = 0;
    for (Item* p = _head; p; p = p->next, ++i)
      ;
    return i;
  }
};

#endif  // ALTERNATIVELINKEDLIST_H

Item.h

#ifndef ITEM_H
#define ITEM_H

/*
 * Die Klasse Item repräsentiert die Listenelemente.
 */
class Item {
 public:
  Item() : e{0}, next{nullptr}, prev{nullptr} {}
  Item(int _e, Item* _next) : e{_e}, next{_next}, prev{nullptr} {}

  int e;
  Item* prev;
  Item* next;
};

#endif  // ITEM_H