線形リストを作ってみる その１

programming C++

線形リストは、鎖のようにデータが連なったデータ構造をとります。
--[data]--[data]--[data]--[data]--
線形リストの形には直線型、循環型があり、データを取り出せる方向として一方向、双方向の二種類に分かれます。
一方向の場合は前のノードを参照することができませんので、常に先頭からチェックしなければなりません。
双方向なら前後のノードを知っているため、どのノードからでも簡単にアクセスすることができます。

C++で双方向・循環型の線形リストを実装してみます。各ノードはint型を保持するとしましょう。

ノードクラスの実装

まずはデータを持っているノードクラスを定義します。
ノードクラスが保持する情報は,前後のノードのアドレスとデータそのものになります。
Node.h

#ifndef __Node_H
#define __Node_H

class Node
{

public:
	Node();
	~Node();
	Node*& next();	//次のノードのアドレスを取得する
	Node*& prev();	//前のノードのアドレスを取得する
	int& data();		//ノードが保持するデータを取得する

	void print();//メンバ変数を出力する(テスト用)
private:
	Node* m_next;	//次のノードのアドレス
	Node* m_prev;	//前のノードのアドレス
	int m_data;	//ノードが保持するデータ
};
#endif

Node.cpp

#include "Node.h"

Node::Node(void):
m_next(0),
m_prev(0),
m_data(0)
{
}

Node::~Node(void)
{
}
Node*& Node::next(){
	return m_next;
}
Node*& Node::prev(){
	return m_prev;
}
int& Node::data(){
	return m_data;
}

#include <iostream>
using namespace std;
void Node::print(){
		cout <<"prev["<<m_prev<<"]\t";
		cout <<"["<<this<<",data="<<m_data<<"]\t";
		cout <<"next["<<m_next<<"]"<< endl;
}

Nodeクラスの利用

Nodeクラスを利用してみます。
アドレスの参照を介してデータをやり取りすることができるようにしています。

#include "Node.h"
int main(){
	Node* node1=new Node();
	Node* node2=new Node();

	node1->print();
	node2->print();

	node1->data()=3;
	node2->next()=node1;
	
	node1->print();
	node2->print();

	delete node1;
	delete node2;
	
	return 0;
}


prev[00000000] [008D2330,data=0] next[00000000]
prev[00000000] [008D2368,data=0] next[00000000]
prev[00000000] [008D2330,data=3] next[00000000]
prev[00000000] [008D2368,data=0] next[008D2330]

線形リストクラスの実装

線形リストはいくつでもノードを持つことができます。最低限必要な操作として、要素を挿入することと削除することができるものとします。ノードのポインタを引数として、挿入や削除を行う関数を作成しておくと後で応用が効きます。
ノードの挿入などで処理の場合分けをせずに済むように、ダミーノードとしてrootノードを持たせることにします。各メンバについてですが、ひとまずpublicで扱うものとしましょう。

線形リストクラスの基本形

List.h

#ifndef __List_H
#define __List_H

#include "Node.h"
class List
{
public:
	List(void);
	~List(void);
	void print();							//要素を表示する
//private:
	void insert_next(Node* node,int data);	//指定したnodeの後に追加
	void insert_prev(Node* node,int data);	//指定したnodeの前に追加
	void erase(Node* node);			//指定したノードを削除する
	Node* m_root;
	int m_size;
};
#endif

Listクラスのメンバ関数が決まりましたので、実装部分 List.cppを作成してみたいと思います。

準備

リスト生成時に、rootノードとサイズの初期値を設定します。

#include "List.h"

List::List(void):
m_size(0)
{
	m_root = new Node();
	m_root->next() = m_root;	//rootノードの前後を自分自身にしておく
	m_root->prev() = m_root;
}

要素の追加

前の情報を上書きしないように、ノードのリンクの付け替え手順に注意する必要があります。

void List::insert_next(Node* node,int data){
	if(node==0){
		return;
	}
	Node* new_node=new Node();//新たに追加したnode

	new_node->prev()=node;
	new_node->next()=node->next();
	node->next()->prev()=new_node;
	node->next()=new_node;
	new_node->data()=data;	//追加したnodeの値を設定
	m_size++;
}
void List::insert_prev(Node* node,int data){
	if(node==0){
		return;
	}
	Node* new_node=new Node();//新たに追加したnode

	new_node->prev()=node->prev();
	new_node->next()=node;
	node->prev()->next()=new_node;
	node->prev()=new_node;
	new_node->data()=data;//追加したnodeの値を設定
	m_size++;
}

要素の削除

void List::erase(Node* node){
	if(node==0 || node==m_root){	//rootは削除しない
		return;
	}
	node->prev()->next()=node->next();
	node->next()->prev()=node->prev();
	delete node;
	m_size--;
}

後処理

リストを削除するときに、保持しているノードも全て削除しなければなりません。

List::~List(void)
{
	for(Node* node=m_root->next();node!=m_root;){
		node=node->next();
		delete node->prev();
	}
	//rootノードを初期化する
	m_root->next()=m_root;
	m_root->prev()=m_root;
	m_size=0;
	delete m_root;
}

出力

#include <iostream>
using namespace std;
//要素を表示する
void List::print(){
	cout <<"(root) "<<"\t\t";
	m_root->print();
	int count=0;
	for(Node* node=m_root->next();node!=m_root;node=node->next()){
		cout <<"(node"<<count<<") "<<"\t";
		node->print();
		count++;
	}
	cout << endl;
}

実際にテストをしてみます。

#include "List.h"
int main(){

	List list;
	list.print();
	list.insert_next(list.m_root,1);
	list.print();
	list.insert_next(list.m_root,2);
	list.print();
	list.insert_prev(list.m_root,3);
	list.print();
	list.insert_prev(list.m_root,4);
	list.print();

	list.erase(list.m_root->next());
	list.print();
	
	return 0;
}


(root) prev[006C2330] [006C2330,data=0] next[006C2330]


(root) prev[006C2368] [006C2330,data=0] next[006C2368]
(node0) prev[006C2330] [006C2368,data=1] next[006C2330]


(root) prev[006C2368] [006C2330,data=0] next[006C17B0]
(node0) prev[006C2330] [006C17B0,data=2] next[006C2368]
(node1) prev[006C17B0] [006C2368,data=1] next[006C2330]


(root) prev[006C17E8] [006C2330,data=0] next[006C17B0]
(node0) prev[006C2330] [006C17B0,data=2] next[006C2368]
(node1) prev[006C17B0] [006C2368,data=1] next[006C17E8]
(node2) prev[006C2368] [006C17E8,data=3] next[006C2330]


(root) prev[006C1820] [006C2330,data=0] next[006C17B0]
(node0) prev[006C2330] [006C17B0,data=2] next[006C2368]
(node1) prev[006C17B0] [006C2368,data=1] next[006C17E8]
(node2) prev[006C2368] [006C17E8,data=3] next[006C1820]
(node3) prev[006C17E8] [006C1820,data=4] next[006C2330]


(root) prev[006C1820] [006C2330,data=0] next[006C2368]
(node0) prev[006C2330] [006C2368,data=1] next[006C17E8]
(node1) prev[006C2368] [006C17E8,data=3] next[006C1820]
(node2) prev[006C17E8] [006C1820,data=4] next[006C2330]