リスト構造 - frostar@wiki

リスト構造はデータと次のデータへのアドレスを1つの塊(ノード)として持っていて、それを連ねたデータ構造である。

• 利点
  • データの挿入、削除がしやすい
  • データをどんどん追加できる
• 欠点
  • 目的のデータへのアクセスが面倒

まずはノードを作ってみる。
Data型という型のデータを格納するリストについて考える。

class Node{
	Data data;
	Node* next;
}

次のデータへのポインタは自分の型のポインタになる。
ちなみに、とりあえず各データへアクセスするためのメソッドについては置いておく。

リストの本体は次のようになる

class List{
	Node* rootP;//先頭ノードのポインタ

	void addData(Data& d);//データ追加
	void insertData(int n,Data& d);//データ挿入
	Data getData(int n);//データ取得
	void remove(int n);//データ削除
}

各メソッド

void addData(Data& d){
	Node* node = new Node(d);
	if(rootP == NULL){
		rootP = data;
	}else{
		Node* p;
		for(p=rootP;p->getNext()!=NULL;p=p->getNext());
		p->setNext(node);
	}
}

getNext、setNextはそれぞれNode型のnextにアドレスを格納するためのメソッド。
まず、nodeというNode型のデータをnewで作る。
rootPがNULLの時(データがない時)はrootPにnodeを格納。
それ以外なら、先頭から順次ノードを見て、nextがNULL(次のデータがない→最後のデータ)のデータの次にnodeを追加する。

void insertData(int n,T& d){
	Node* node = new Node(d);
	if(n==0){
		node->setNext(rootP);
		rootP=node;
	}else{
		Node* p = rootP;
		for(int i=1;i<n;i++){
			if(p==NULL)break;
			p=p->getNext();
		}
		node->setNext(p->getNext());
		p->setNext(data);
	}
}

n番目にデータを挿入する。
基本的にはaddとあまり変わらない。
nが0ならnodeの次のデータとして、現在の先頭ノードを入れ、rootPにnodeのアドレスを入れることで、nodeを先頭ノードとしている。
それ以外なら、データをn回たどって、その次のノードにnodeを挿入する。
挿入場所の1つ前のノードのnextに挿入ノードのアドレスを入れ、挿入ノードのnextに1つ前のノードの次のノードを格納することで実現できる。

Data getData(int n){
	Node* p = rootP;
	for(int i=0;i<n;i++){
		if(p==NULL)break;
		p=p->getNext();
	}
	if(p==NULL)return NULL;
	return p->getData();
}

データの取得も、n回たどって、そのデータを返してるだけである。

void remove(int n){
	if(0<=n && rootP!=NULL){
		Node *p = rootP;
		Node *bp = NULL;
		for(int i=0;i<n;i++){
			bp=p;
			p=p->getNext();
		}
		if(p==NULL)break;
		if(bp==NULL)rootP=p->getNext();
		else bp->setNext(p->getNext());
		delete p;
	}
}

削除するときは、削除対象ノードの前のノードのnextを削除対象ノードの次のノードにして、データを削除することで実現できる。

今回は単方向リストを作成したが、ひとつ後ろのノードのアドレスを持つ双方向リストも存在する。
双方向リストでは、データの検索性が上がるが、処理が増えるし、それほど大きくないデータなら単方向リストで十分だと思う。
また、最大数や検索ポインタなどの処理を追加してもいいだろう。
あくまで今回のは最低限レベルである。
実際、何のデータをリストに格納するかはわからないので、C++だとtemplateを使うといい。