データ構造/連結リスト - nkym_memo @ ウィキ

連結リスト(linked list)

• 連結リスト リストに含まれる各要素をポインタによってつなぎ合わせたもの。

• 前から後ろに向かってのみ順番をたどることができる（計算量O(n)）
• 配列に対する利点：要素の挿入や削除が容易（計算量O(n)）
• リストの連結/分断が容易

• 指定した要素の直前に挿入は不可能
• 削除は指定セルの直後のみ（指定セルおよびその直前のセルは削除不可能）
• 後述のinsert のように、２つのポインタを用いるて、現在注目中のセルと、直前のセルを常に指すのが定石

例)
struct CELL{
	int value;
	struct CELL *next;
}
 メンバnext：次の要素を指すポインタ。最後の場合はメンバnextにNULLポインタをセット

シーケンシャルアクセス

struct CELL *p,*header;

if((p = malloc(sizeof(struct CELL))) == NULL){
	fprintf(stderr,"Cannot allocate memory");
}
if((header = malloc(sizeof(struct CELL))) == NULL){
	fprintf(stderr,"Cannot allocate memory");
}

for(p = header->next;p != NULL;p = p->next){
	printf("%d\n",p->value);
}

要素の挿入

ポインタxで指されているセルの次に、ポインタpで指されている新しいセルを挿入

1. ポインタxで指しているセルのアドレスをpに渡す
2. ポインタxで指しているセルのアドレスをpのセルにする

p->next = x->next;
x->next = p;

要素の削除

ポインタxで指されているセルの次のセルを削除

1. ポインタpで削除するセルを指定
2. ポインタxの指す先をポインタpの指すセルにする

   p = x->next;
   x->next = p->next;

境界条件の扱い

先頭、末尾の要素、連結リストが空の時の処理が境界条件

指定セルの直前への挿入

• *current_Cell：現在着目しているセルを指すポインタ
• *prev_currrent_Cell：Current_Cellの直前のセルを指すポインタ

struct CELL{
	int value;
	struct CELL *next;
}header;

insert(int a){
	struct CELL *current_Cell,*prev_Cell,*new_Cell;

	current_Cell = header.next;
	prev_Cell = &header;

	while(current_Cell != NULL && a > current_Cell->value){
		prev_Cell = current_Cell;
		current_Cell = prev_Cell->next;
	}

	if((new_Cell = malloc(sizeof(struct CELL)) == NULL){
		fprintf(stderr,"Cannot allocate memory");
	}
	new_Cell->next = current_Cell;
	new_Cell->value = a;
	prev_Cell->next = new_Cell;
}

---

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)