連結リストを作る (1)

C/C++ の配列は、そのサイズをコンパイル時に決定する必要があります。
そのため、サイズが動的に変化するデータの格納が少々面倒だったりします。

そこでよく用いられるのが、連結リストと呼ばれるデータ構造です。 殆どの環境ではライブラリとして提供されていますが、勉強もかねて自分で実装してみましょう。

設計

コードを書き始めるまえに、簡単な設計を行いましょう。
この段階では詳細には立ち入らず、データの構造をおおまかに決定すれば十分です。(図 1)

【図1: 連結リストの構造】
リストを構成するノード (node) はそれぞれ、自分の前後に位置するノードのアドレスをメンバ変数 m_lpPrev, m_lpNext に保持します。 (始端ノードの m_lpPrev および、終端ノードの m_lpNextNULLとする)。

リストの本体 (list) は、始端および終端ノードのアドレスを m_lpHead, m_lpTail として保持します (リストが空の場合は、m_lpHead, m_lpTail は共にNULLとする)。

だいたいの構造が決まったら、いよいよ実装を始めます。

ノードの定義

まずは、リストのデータを保持するノード (ListNode クラステンプレート) を定義します。
ListNode.h
////////////////////////////////////////////////////////////////////////////////
//
//  ListNode.h
//
#ifndef __LISTNODE_H__
#define __LISTNODE_H__
#include <assert.h>
#ifndef NULL
#define NULL 0
#endif
//略記用マクロ
#define LPCNODE   const ListNode<T>*
#define LPNODE    ListNode<T>*
#define _TEMPLATE template <typename T>
//プロトタイプ宣言
_TEMPLATE class List;
//リストノード
_TEMPLATE class ListNode {
friend class List<T>;
public:
T   value; //ノード値
//construction
ListNode(LPNODE lpPrev, LPNODE lpNext, const T& value);
//member access (getting)
LPNODE  Prev();
LPCNODE Prev() const;
LPNODE  Next();
LPCNODE Next() const;
protected:
LPNODE  m_lpPrev; //前ノードのアドレス
LPNODE  m_lpNext; //次ノードのアドレス
};
////////////////////////////////////////////////////////////////////////////////
//construction
▼実装部を表示
////////////////////////////////////////////////////////////////////////////////
//member access (getting)
▼実装部を表示
//略記用マクロ解除
#undef LPCNODE
#undef LPNODE
#undef _TEMPLATE
#endif //__LISTNODE_H__
//[EOF]
m_lpPrev, m_lpNext はユーザに勝手に書き換えられては困るので、protected とし、アクセス用のメンバ関数 Prev, Next を作っておきます。

リストの定義

次に、この連結されたノード列を管理するためのクラス List を作成します。
実際にはここで記述されるもの以外の機能も必要ですが、今回は次節のサンプルコードの動作に最低限必要なものだけを実装します。
List.h
////////////////////////////////////////////////////////////////////////////////
//
//  List.h
//
#ifndef __LIST_H__
#define __LIST_H__
#include "ListNode.h"
//略記用マクロ
#define LPCNODE   const ListNode<T>*
#define LPNODE    ListNode<T>*
#define _TEMPLATE template <typename T>
_TEMPLATE class List {
public:
const int& size;
//construction
List();
List(const List<T>&);
//destruction
virtual ~List();
//operator
List<T>& operator = (const List<T>&);
T&       operator [] (int nIndex) ;
const T& operator [] (int nIndex) const;
//operation
LPNODE  Append(const T&);
protected:
LPNODE  m_lpHead; //始端ノードのアドレス
LPNODE  m_lpTail; //終端ノードのアドレス
int     m_nSize;  //要素数
//operation
LPNODE  GetLPNode(int nIndex);
LPCNODE GetLPNode(int nIndex) const;
private:
//destruction
void    Destroy();
};
////////////////////////////////////////////////////////////////////////////////
//construction
▼実装部を表示
////////////////////////////////////////////////////////////////////////////////
//destruction
▼実装部を表示
////////////////////////////////////////////////////////////////////////////////
//operator
▼実装部を表示
////////////////////////////////////////////////////////////////////////////////
//operation
▼実装部を表示
//略記用マクロ解除
#undef LPNODE
#undef _TEMPLATE
#endif //__LIST_H__
//[EOF]

使ってみる

このリストを利用した簡単なプログラムを作成し、動作テストを行います。
#include <stdio.h>
#include "List.h"
int main(){
List<char> list;
//読み込み
for (;;){
int n =getc(stdin);
if (n == EOF) break;
list.Append(static_cast<char>(n));
}
//出力
int i;
for (i=0; i<list.size; ++i){
putc(list[i], stdout);
} //i
return 0;
}
Truth is always bitter to those who fear it.[LF]
[EOF]
Truth is always bitter to those who fear it.
このとおり、任意長の長さのデータをメモリ上に読み込むことができます。

次回は、要素の挿入・削除といった動作のためのメンバ関数の作成を行います。

担当: 成田