連結リストを作る (1)

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

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

設計

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

【図1: 連結リストの構造】

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

リストの本体 (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 //コンストラクタ _TEMPLATE ListNode<T>::ListNode(LPNODE lpPrev, LPNODE lpNext, const T& value) : m_lpPrev(lpPrev), m_lpNext(lpNext), value(value) { }▼実装部を表示 //////////////////////////////////////////////////////////////////////////////// //member access (getting) //前ノードアドレス _TEMPLATE LPNODE ListNode<T>::Prev() { return m_lpPrev; } //前ノードアドレス (const) _TEMPLATE LPCNODE ListNode<T>::Prev() const { return m_lpPrev; } //次ノードアドレス _TEMPLATE LPNODE ListNode<T>::Next() { return m_lpNext; } //次ノードアドレス (const) _TEMPLATE LPCNODE ListNode<T>::Next() const { return m_lpNext; }▼実装部を表示 //略記用マクロ解除 #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 //コンストラクタ _TEMPLATE List<T>::List() : m_lpHead(NULL), m_lpTail(NULL), m_nSize(0), size(m_nSize) { } //コンストラクタ _TEMPLATE List<T>::List(const List<T>& l) : size(m_nSize) { if (l.m_nSize){ LPCNODE p =l.m_lpHead; int nSize =l.m_nSize; LPNODE lpHead =new ListNode<T>(NULL, NULL, p->value); LPNODE lpTail =lpHead; while (p =p->m_lpNext){ lpTail =lpTail->m_lpNext =new ListNode<T>(lpTail, NULL, p->value); } m_lpHead =lpHead; m_lpTail =lpTail; m_nSize =nSize; } else { m_lpHead =NULL; m_lpTail =NULL; m_nSize =0; } }▼実装部を表示 //////////////////////////////////////////////////////////////////////////////// //destruction //デストラクタ _TEMPLATE List<T>::~List(){ Destroy(); } //オブジェクトの破棄 [for internal use] _TEMPLATE void List<T>::Destroy(){ LPNODE p =m_lpHead; while (p){ LPNODE q =p->m_lpNext; delete p; p =q; } return; }▼実装部を表示 //////////////////////////////////////////////////////////////////////////////// //operator //代入 _TEMPLATE List<T>& List<T>::operator = (const List<T>& l){ if (l.m_nSize){ LPCNODE p =l.m_lpHead; int nSize =l.m_nSize; LPNODE lpHead =new ListNode<T>(NULL, NULL, p->value); LPNODE lpTail =lpHead; while (p =p->m_lpNext){ lpTail =lpTail->m_lpNext =new ListNode<T>(lpTail, NULL, p->value); } Destroy(); m_lpHead =lpHead; m_lpTail =lpTail; m_nSize =nSize; } else { Destroy(); m_lpHead =NULL; m_lpTail =NULL; m_nSize =0; } return *this; } //要素参照 _TEMPLATE inline T& List<T>::operator [] (int nIndex){ assert(0 <= nIndex && nIndex < m_nSize); return GetLPNode(nIndex)->value; } ////要素参照 (const) _TEMPLATE inline const T& List<T>::operator [] (int nIndex) const { assert(0 <= nIndex && nIndex < m_nSize); return GetLPNode(nIndex)->value; }▼実装部を表示 //////////////////////////////////////////////////////////////////////////////// //operation //要素の追加 _TEMPLATE LPNODE List<T>::Append(const T& value){ LPNODE lpNode; if (m_lpTail){ lpNode =new Node(m_lpTail, NULL, value); m_lpTail =m_lpTail->m_lpNext =lpNode; ++m_nSize; } else { lpNode =new Node(NULL, NULL, value); m_lpHead =lpNode; m_lpTail =lpNode; m_nSize =1; } return lpNode; } //ノードアドレスの取得 [for internal use] _TEMPLATE LPNODE List<T>::GetLPNode(int nIndex){ assert(0 <= nIndex && nIndex < m_nSize); LPNODE p =m_lpHead; int i; for (i=0; i<nIndex; ++i) p =p->m_lpNext; return p; } //ノードアドレスの取得 (const) [for internal use] _TEMPLATE LPCNODE List<T>::GetLPNode(int nIndex) const { assert(0 <= nIndex && nIndex < m_nSize); LPCNODE p =m_lpHead; int i; for (i=0; i<nIndex; ++i) p =p->m_lpNext; return p; }▼実装部を表示 //略記用マクロ解除 #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.

このとおり、任意長の長さのデータをメモリ上に読み込むことができます。

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

担当: 成田