Doubly linked lists (and stacks, and queues, and multiple sorting algorithms) in C++.

list.cpp

#include <cassert>
#include <initializer_list>
#include <iostream>

struct node {
  int elem;
  node* next;
  node* prev;
};

class list {
  int size_;
  node* front_;
  node* back_;

public:
  list();
  list(const std::initializer_list<int>& il);
  ~list();

  int size();
  bool empty();

  int& front();
  int& back();

  void push_front(int elem);
  void push_back(int elem);
  int pop_front();
  int pop_back();

  int& operator[](int n);

  void debug();
};

list::list() {
  size_ = 0;
  front_ = back_ = nullptr;
}

list::list(const std::initializer_list<int>& il) : list() {
  for(const int elem : il) {
    push_back(elem);
  }
}

list::~list() {
  while(front_) {
    pop_front();
  }
}

int list::size() {
  return size_;
}

bool list::empty() {
  return size_ == 0;
}

int& list::front() {
  assert(front_);
  return front_->elem;
}

int& list::back() {
  assert(back_);
  return back_->elem;
}

void list::push_front(int elem) {
  node* new_node = new node;
  new_node->elem = elem;
  new_node->next = new_node->prev = nullptr;
  if(front_) {
    new_node->next = front_;
    front_->prev = new_node;
    front_ = new_node;
  } else {
    front_ = back_ = new_node;
  }
  ++size_;
}

void list::push_back(int elem) {
  node* new_node = new node;
  new_node->elem = elem;
  new_node->next = new_node->prev = nullptr;
  if(back_) {
    new_node->prev = back_;
    back_->next = new_node;
    back_ = new_node;
  } else {
    front_ = back_ = new_node;
  }
  ++size_;
}

int list::pop_front() {
  assert(front_);
  int elem = front_->elem;
  if(front_->next) {
    front_ = front_->next;
    delete front_->prev;
    front_->prev = nullptr;
  } else {
    delete front_;
    front_ = nullptr;
  }
  --size_;
  return elem;
}

int list::pop_back() {
  assert(back_);
  int elem = back_->elem;
  if(back_->prev) {
    back_ = back_->prev;
    delete back_->next;
    back_->next = nullptr;
  } else {
    delete back_;
    back_ = nullptr;
  }
  --size_;
  return elem;
}

int& list::operator[](int n) {
  assert(0 <= n && size_ > n);
  node* nth_node = front_;
  for(int i = 0; i < n; ++i) {
    nth_node = nth_node->next;
  }
  return nth_node->elem;
}

void list::debug() {
  if(front_) {
    for(node* iter = front_; iter; iter = iter->next) {
      std::cerr << iter->elem << " ";
    }
    std::cerr << std::endl;
  }
}

class stack : private list {
public:
  stack() : list() {}
  stack(const std::initializer_list<int>& il) : list(il) {}

  int size() {
    return list::size();
  }

  bool empty() {
    return list::empty();
  }

  int& peek() {
    return front();
  }

  void push(int elem) {
    push_front(elem);
  }

  int pop() {
    return pop_front();
  }
};

class queue : private list {
public:
  queue() : list() {}
  queue(const std::initializer_list<int>& il) : list(il) {}

  int size() {
    return list::size();
  }

  bool empty() {
    return list::empty();
  }

  int& front() {
    return list::front();
  }

  int& back() {
    return list::back();
  }

  void enqueue(int elem) {
    push_back(elem);
  }

  int dequeue() {
    return pop_front();
  }
};

void select_sort(list& l) {
  for(int i = 0; i < l.size(); ++i) {
    int min = i;
    for(int j = i; j < l.size(); ++j) {
      if(l[j] < l[min]) min = j;
    }
    int tmp = l[i];
    l[i] = l[min];
    l[min] = tmp;
  }
}

void insert_sort(list& l) {
  for(int i = 1; i < l.size(); ++i) {
    int current = l[i];
    int j = i;
    while(j > 0 && l[j - 1] > current) {
      l[j] = l[j - 1];
      --j;
    }
    l[j] = current;
  }
}

void shell_sort(list& l) {
  for(int gap = l.size() / 2; gap > 0; gap /= 2) {
    for(int i = gap; i < l.size(); ++i) {
      int tmp = l[i];
      int j = i;
      while(j >= gap && l[j - gap] > tmp) {
        l[j] = l[j - gap];
        j -= gap;
      }
      l[j] = tmp;
    }
  }
}

#define test_sort(sort, ...) { \
  list l { __VA_ARGS__ };             \
  sort(l);                            \
  for(int i = 0; i < l.size(); ++i) { \
    assert(l[i] == i + 1);            \
  }                                   \
}

#define test(...) \
  test_sort(select_sort, __VA_ARGS__) \
  test_sort(insert_sort, __VA_ARGS__) \
  test_sort(shell_sort, __VA_ARGS__)

int main() {
  test(1, 2, 6, 9, 8, 3, 10, 7, 5, 4);
  test(7, 10, 2, 9, 1, 8, 5, 4, 6, 3);
  test(5, 10, 3, 8, 6, 4, 7, 1, 9, 2);
  test(3, 8, 10, 1, 9, 5, 7, 6, 2, 4);
  test(2, 1, 8, 5, 4, 10, 7, 6, 9, 3);
  test(6, 8, 3, 9, 5, 7, 2, 1, 10, 4);
  test(1, 2, 6, 5, 9, 4, 8, 3, 7, 10);
  test(1, 2, 8, 6, 5, 7, 10, 4, 3, 9);
  test(3, 5, 4, 6, 8, 2, 10, 9, 7, 1);
  test(9, 4, 3, 6, 1, 7, 2, 10, 8, 5);

  list l;
  assert(l.empty());

  l.push_front(1);
  l.push_back(2);
  l.push_back(3);
  assert(l.front() == 1);
  assert(l.back() == 3);
  assert(l.size() == 3);

  assert(l.pop_front() == 1);
  assert(l.size() == 2);

  assert(l.pop_back() == 3);
  assert(l.size() == 1);

  l.push_front(1);
  l.push_back(3);
  l.push_back(4);
  l.push_back(5);
  assert(l[0] == 1);
  assert(l[1] == 2);
  assert(l[2] == 3);
  assert(l[3] == 4);
  assert(l[4] == 5);
  assert(l.size() == 5);

  stack s;
  assert(s.empty());

  s.push(1);
  s.push(2);
  s.push(3);
  assert(s.peek() == 3);
  assert(s.size() == 3);

  assert(s.pop() == 3);
  assert(s.pop() == 2);
  assert(s.pop() == 1);

  queue q;
  assert(q.empty());

  q.enqueue(1);
  q.enqueue(2);
  q.enqueue(3);
  assert(q.size() == 3);

  assert(q.dequeue() == 1);
  assert(q.dequeue() == 2);
  assert(q.dequeue() == 3);

  return 0;
}