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

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

これに加え、配列の欠点としてあげられるのが、途中データの削除・挿入となる。 配列の指定位置にデータを追加しようと思うと、 入れるべき場所に"空き"を作るために、以降のデータを１つ後ろにずらす必要がある。 削除でも同様に、１つ前にずらす処理が必要となる。 これにかかる処理時間は、最悪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を返すことは考える必要があるけど…) 一方、欠点としては、データを参照する場合には、 先頭から１つづつアクセスする必要があり、 中央データを参照して２分探索といったテクニックは使えない。

• 05/21 いいねぇ〜 "素人でも使いやすい回路図エディタBSch3V" http://tinyurl.com/6wdovm #fnct
• 05/21 いいねぇ〜… RT @jun1s: 先日も、市内の某ＩＴ会社の役員達と飲んでいたわけだが、曰く、「いい人材の雇用はとかく難しい。面接やテストだけではなかなか測れない。奥が深い。しかし、高専卒は別。彼らは安心して採用できる。5年間彼らを見てきた先生達から意見を… #fnct

この記事は、 の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。