連結リストを作る (1) (Codelogy)

連結リストを作る (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.

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

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

担当: 成田

日時: 2008年09月01日 15:00 | パーマリンク