IntList.cpp

#include <iostream>

class IntList {
public:
  int first;
  IntList *rest;

  IntList(int f, IntList *r = nullptr) {
    first = f;
    rest = r;
  }

  ~IntList() {
    first = 0;
    if (rest != nullptr)
      delete rest;
  }

  /** Return the size of this IntList using recursion. */
  int size() const {
    if (rest == nullptr) {
      return 1;
    }
    return 1 + rest->size();
  }

  /** Return the size of this IntList. */
  int iterativeSize() const {
    const IntList *p = this;
    int totalSize = 0;
    while (p != nullptr) {
      totalSize += 1;
      p = p->rest;
    }
    return totalSize;
  }

  /** Return the i-th element. */
  int get(int i) const {
    if (i == 0)
      return first;
    return rest->get(i - 1);
  }
};

/** Returns an IntList with all values in L incremented by x. */
IntList *incrList(const IntList *L, int x) {
  if (L == nullptr)
    return nullptr;
  IntList *Q = new IntList(L->first + x);
  IntList *ret = Q;
  L = L->rest;
  while (L != nullptr) {
    Q->rest = new IntList(L->first + x);
    Q = Q->rest;
    L = L->rest;
  }
  return ret;
}

/** Returns an IntList with all values in L incremented by x. */
IntList *dincrList(IntList *L, int x) {
  IntList *ret = L;
  while (L != nullptr) {
    L->first += x;
    L = L->rest;
  }
  return ret;
}

int main() {
  IntList *L = new IntList(15);
  L = new IntList(10, L);
  L = new IntList(5, L);

  std::cout << L->size() << std::endl;
  std::cout << L->iterativeSize() << std::endl;

  std::cout << L->get(0) << std::endl;
  std::cout << L->get(1) << std::endl;

  IntList *Q = incrList(L, 2);
  std::cout << Q->get(0) << " " << Q->get(1) << " " << Q->get(2) << std::endl;
  std::cout << L->get(0) << " " << L->get(1) << " " << L->get(2) << std::endl;

  IntList *Q2 = dincrList(L, 2);
  std::cout << Q2->get(0) << " " << Q2->get(1) << " " << Q->get(2) << std::endl;
  std::cout << L->get(0) << " " << L->get(1) << " " << L->get(2) << std::endl;

  delete L, delete Q;
}