C++で単方向リスト

C++ 30分プログラム

30分プログラム、その745。C++で単方向リストを書いてみた。
さっきBoostのインストールを開始したんですが、なかなか時間かかりますね。で、その間の暇つぶしに単方向リスト書いてました。
いたるところでnewしてますが、まったくdeleteしてません。だって、Boostのインストールが完了してないから、shared_ptrが使えないんですもん。ごめんなさい。

使い方

list<int>* xs = cons(1, cons(2, cons(3, nil<int>())));

cout << length(xs) << endl;

ソースコード

#include <iostream>

template <typename T>
struct list{
  T value;

  // fix later
  list* next;

  list(T value, list<T>* next)
    :value(value), next(next)
  {}
};

template <typename T>
inline list<T>* nil(){
  return 0;
}

template <typename T>
list<T>* cons(T value, list<T>* next){
  return new list<T>(value, next);
}

template <typename T>
T head(list<T>* xs){
  return xs->value;
}

template <typename T>
list<T>* tail(list<T>* xs){
  return xs->next;
}

template <typename T>
int length(list<T>* xs){
  if(xs == nil<T>()){
    return 0;
  }else{
    return 1 + length(tail(xs));
  }
}

template <typename T>
list<T>* append(list<T>* xs, list<T>* ys){
  if(xs == nil<T>()){
    return ys;
  }else{
    return cons(head(xs), append(tail(xs),ys));
  }
}

template <typename T, typename F>
void for_each(F f, list<T>* xs){
  if(xs != nil<T>()) {
    f(head(xs));
    for_each(f, tail(xs));
  }
}

void puti(int d){
  printf("%d ",d);
}

int main(int argc, char *argv[])
{
  using namespace std;

  list<int>* xs = cons(1, cons(2, cons(3, nil<int>())));
  list<int>* ys = cons(4, cons(5, cons(6, nil<int>())));

  cout << length(xs) << endl;
  cout << length(append(xs,ys)) << endl;

  for_each(puti, xs);
  puts("");

  for_each(puti, append(xs, ys));
  puts("");
  return 0;
}

参考