データ構造に関係するアルゴリズム説明が一通り終わったので、 ここからは動的メモリの管理方法の解説。 まずは最初に、参照カウンタ法とガベージコレクタについて説明する。

参照カウンタ法

データにポインタによって共有が発生すると、 不要になったデータの廃棄が問題になるという例を示す。

/* 共有の発生するリストによる和集合 */
struct List* set_or( struct List* p , struct List* q ) {
struct List* n = q ;
for( ; p != NULL ; p = p->next ) {
if ( ! find( q , p->data ) )
n = cons( p->data , n ) ;
}
return n ;
}
/* リストを全部捨てる関数 */
void list_free( struct List* p ) {
if ( p != NULL ) {
list_free( p->next ) ;
free( p ) ;
}
}
void main() {
struct List* a = 適当なリスト生成 ;
struct List* b = 適当なリスト生成 ;
struct List* c = set_or( a , b ) ;
list_free( c ) ;
list_free( b ) ;  // 実はリストは前処理で捨てられている
list_free( a ) ;
}

こういったプログラムであれば、リストを捨てる処理が気軽に書けなくなってしまう。 根本の原因は、データ間で共有されている部分が発生しているため。 この解決方法の１つが参照カウンタ法。

/* 参照カウンタ法を使うリスト */
struct List {
int refc ; //参照カウンタ。生成時は1で初期化
int data ;
struct List* next ;
} ;
/* コピー(共有?)が発生する時にはこれを使え! */
struct List* share( struct List* p ) {
if ( p != NULL )
p->refc ++ ;
}
/* 共有の発生するリストによる和集合 */
struct List* set_or( struct List* p , struct List* q ) {
struct List* n = share( q ) ; // カウントアップ
for( ; p != NULL ; p = p->next ) {
if ( ! find( q , p->data ) )
n = cons( p->data , n ) ;
}
return n ;
}
/* リストを全部捨てる関数 */
void list_free( struct List* p ) {
if ( p != NULL ) {
p->refc-- ; // カウントダウン
if ( p->refc == 0 ) {
list_free( p->next ) ;
free( p ) ;
}
}
}

このような参照カウンタは、ハードディスクでのファイル管理でも使われている。 ハードディスクでは、障害時に参照カウンタ管理が異常になるとゴミデータが残るようになる。 このため障害復旧時には、全HDD領域の参照カウンタの異常チェックが重要。 しかしながら、復旧処理に時間がかかるようになるので、ジャーナリングという方法がとられる。

一方、参照カウンタ法の問題点として、循環リストのようなデータの場合、カウンタが0にならないけど、 他のデータから孤立したデータが発生してしまう。

ガベージコレクタ

参照カウンタ法は単純だけど、万能ではないため、不要となったデータ領域の回収は、 どうするのが理想的なのか？ ひとつの解決方法はガベージコレクタ。 ガベージコレクタ(Garbage Collector)では、不要となったデータ領域はあえて回収しない。 (free()関数は使わない) しかしこのままではメモリ空間がゴミだらけになってしまう。 そこで、メモリ空間がゴミであふれたら、ゴミ回収(Garbage Collect)を行う。 マーク＆スイープ法では、ゴミであふれたら使用中のメモリ空間をたどりながら、 使用中目印をつける(marking)。　その後、目印のついていない領域は回収(sweep)。

ただし、GCが起動すると、他の処理ができなくなるので、処理の中断が発生する。 対話的なシステムでは、GCは処理の遅延になるので、嫌われていた。 最近のガベージコレクタでは、参照カウンタ法も併用した方式がとられるため、 早い段階で不要な領域の回収が可能となり、処理の遅延が問題になることはなくなってきた。