ホーム » スタッフ » 斉藤徹 » リスト構造

2012年5月
« 4月   6月 »
 12345
6789101112
13141516171819
20212223242526
2728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

リスト構造

配列の利点・欠点を踏まえ、リスト構造の説明を行う。

配列は、N番目のデータ抽出が簡単であり、2分探索法では中央の値を 簡単に取り出せることから、O(log N)の処理が可能となる。 この一方で、C言語では配列サイズは固定であり、 最初の段階で適切なサイズが解らない場合は、メモリの使用効率を 低下させる。

これに加え、配列の欠点としてあげられるのが、途中データの削除・挿入となる。 配列の指定位置にデータを追加しようと思うと、 入れるべき場所に"空き"を作るために、以降のデータを1つ後ろにずらす必要がある。 削除でも同様に、1つ前にずらす処理が必要となる。 これにかかる処理時間は、最悪N件、最低で0件となることから、平均N/2回の ループを要し、O(N)の処理が必要となる。

これらの欠点の対応方法として、配列であれば、次のデータの入っている 場所を使えば良い。

((リストを配列で))
top: 3
data,next
0:  41  1    int data[..] ;
1:  60  -1   int next[..] ;
2:  10  4    for( p = top ; p >= 0 ; p = next[ p ] )
3:   6  2        printf( "%d" , data[ p ] ) ;
4:  22  5
5:  34  0

この方法は、アパートの回覧板で、部屋の住人は「次の部屋の人の番号を知っていれば十分」という状況と同じである。 この方式であれば、たとえデータを追加したい場合でも、 例えば30を追加するのであれば、data[4]の後ろに追加したいのであり、 data[6] = 30 を保存し、next[4] = 6、next[6] = 5 とすれば、途中にデータを混ぜることができる。

この方法によって、データを途中に追加する場合でも、O(1)で挿入が可能となる。 (ただし挿入すべき場所を探すにはO(N)の時間を要する)

リスト構造

一方でこのままでは、data[],next[]の最初の配列サイズ以上のデータを保存することは できない。そこで必要に応じてメモリを確保する方法をとる。

// 基本となるリスト構造の宣言
struct List {
int data ;
struct List* next ;
} ;
// 手作業で地道にリストを生成
struct List* top ;
top = (struct List*)malloc( sizeof(struct List) ) ;
top->data = 1 ;
top->next = (struct List*)malloc( sizeof(struct List) ) ;
top->next->data = 2 ;
top->next->next = (struct List*)malloc( sizeof(struct List) ) ;
top->next->next->data = 3 ;
top->next->next->next = NULL ;
// リストデータを表示
struct List* p ;
for( p = top ; p != NULL ; p = p->next )
printf( "%d" , p->data ) ;

このような方法であれば、必要に応じてメモリを確保するため、 配列サイズが途中で不足するといった事態を考える必要がない。 (mallocがNULLを返すことは考える必要があるけど…) 一方、欠点としては、データを参照する場合には、 先頭から1つづつアクセスする必要があり、 中央データを参照して2分探索といったテクニックは使えない。