電脳ミツバチのコンピュータ広報室

銀座の屋上菜園を耕しています。コンピュータ畑も耕します。

リスト

スポンサーリンク

Lispでその名を轟かせたデータ構造リストだが、簡単に図で表すと

          • >①----->②---->③----->④

このように項目(node)の最後と次の項目の最初をつなげたものである。
つながっていると言う点では配列と同じと思うかもしれないが配列よりも優れている点として、

  1. 実行中に大きくなったり小さくなったり出来ることである。配列も可変長配列のアルゴリズムを使えば出来なくはないが、リストの場合、最大の大きさがわかっている必要すらない。これによりいくつかのデータ構造が記憶領域を共有するのに、あまり相互の大きさに注意を払わなくてよい。
  2. 項目の並べ替えが楽である。配列がいちいち全ての項目を一つづつずらさねばならないのに対して
                  ________________
         ↓              |
ー----①-----    ②----→③    ④
            |____________________↑

こんな具合に調整できる。
デメリット(リストに向いていない動作)として入れ替えが自由に行えることにより、特定の項目を参照する(search)能力が相対的に落ちる。


リストのやり方として最初と最後の点を考える。つまりダミーを置いてやるのだ
仮に最初をheadとし、終わりをzと置く(セジウィック先生流)と、これにより先頭や末尾の接点も中の要素同様に入れ替えなどの操作が可能になる。

                           __________
                ________|________  |
 head       ↓      |       |  |     z
 □--------     ①----→②    ③  ------□
            |____________________↑

①→②→③から③→①→②へと変換

リストによる挿入はもっと簡単である。

                          
                  _⑥_
 head               |  |        z
 □-------→①----→②   ③------□

①→②→③から①→②→⑥→③へと変換        

削除は書くまでも無く⑥を消す動作である。②と③を繋げればよい。
実装してみるとこうなる。

#include<stdio.h>
#include<stdlib.h>

struct node
{int key;struct node *next;};    /*最後が次の構造体をさす*/
struct node *head,*z,*t;

listinitialize()
{
	head=(struct node *)malloc(sizeof *head);
	z=(struct node *)malloc(sizeof *z);
	head->next=z;
	z->next=z;
}

deletenext(struct node *t)
{t->next=t->next->next;}

struct node *insertafter(int v,struct node *t)
{
	struct node *x;
	x=(struct node *)malloc(sizeof *x);
	x->key=v;
	x->next=t->next;
	t->next=x;
	return x;
}
main(){}

ヘッダファイルなんかに入れてやると使えるかもしれない。
ただ、リストは実装が簡単なので毎回直接書くことが多い。
特に今は何もやっていない。
説明するとリストはnode(節点)いくつかからなり、各々の接点は整数一つとリストの次のnodeを指すリンクからなる。最初にheadとzを定義して後々増やしていく又は消していくプログラム。

  • >等の意味が分からなければ構造体の項なんかを参照すればよい。

例えばhead->next->keyはリストの最初の番号をさし、head->next->next->keyはリスト二番目をさす。

この実装において与えられた項目の直前の項目を見つける操作を直接出来るようにしたものを両方向リスト(doubly linked list)という。
ただ、これを実装させると各々の項目に2つのリンクを保持しなければならないので基本操作におけるリンクの回数が2倍になる。
又この実装においてzがheadを指してぐるぐる回すことも出来る。
この時のリストのことを循環リスト(circular list)と呼ぶ。
代表的なアルゴリズムにJosephus problemがある。

配列での実装

配列はコンピュータの記憶装置で直接実現できるので配列でデータ構造を実現する方法を調べればより低レベルでの実現できる。
ここで並列的配列を用いると便利なことが多い。
これは一つの配列の添え字の部分にさらに配列を入れるというもの。
例えばkey[next[head]]が一番目の項目をあらわし、key[next[next[head]]]が次の項目をあらわすと言う具合である。
この利点はkeyにはデータのみ入れておき、データ構造の部分はnextの中で作れること。

#include<stdio.h>
#define max	3
	
int key[max+2],next[max+2];
int x,head,z;
listinitialize()
{
	head=0;z=1;x=2;
	next[head]=z;next[z]=z;
}
deletenext(int t)
{
	next[t]=next[next[t]];
}
int insertafter(int v,int t)
{
	key[x]=v;
	next[x]=next[t];
	next[t]=x;
	return x++;
}

main(){}

こんな感じになる。