はじめに
本当はこの記事を書くつもりはなかったが, アドカレの前半がスカスカだったのとちょうど作りたかったものがあったので書いてみることにした. 時間はそこまで取れなかったのでツッコミどころは多数あるかも.
どんなものが作りたいのか
- char型の要素を持った双方向リスト(っぽいもの)
- 前後の要素に簡単に移動したい
- リストの最後尾に新たな要素を追加したい
作るぞ！！！！
早速作っていく. 難しいことはしないので大雑把な解説になります.
その1 要素の構造体を作ろう
まずはこう. char型の要素と前後のlist型へのポインタが入っている. list型の定義の中でlist型を使う再帰的定義になっている.
typedef struct list list;
struct list{
char data;
list *prev;
list *next;
};
その2 前後の要素に移動しよう
まずは手作業でリストを作る.
struct list *l0 = (list *)malloc(sizeof(list));
struct list *l1 = (list *)malloc(sizeof(list));
struct list *l2 = (list *)malloc(sizeof(list));
l0->data = 'A';
l0->prev = NULL;
l0->next = l1;
l1->data = 'B';
l1->prev = l0;
l1->next = l2;
l2->data = 'C';
l2->prev = l1;
l2->next = NULL;
構造体をポインタで宣言するときはmallocなどでメモリ領域を確保してあげよう.
関数は下のように定義して試しに動かしてみよう.
#include <stdlib.h>
#include <stdio.h>
typedef struct list list;
struct list{
char data;
list *prev;
list *next;
};
list *Next(list *l){
return l->next;
}
list *Prev(list *l){
return l->prev;
}
int main(void){
struct list *l0 = (list *)malloc(sizeof(list));
struct list *l1 = (list *)malloc(sizeof(list));
struct list *l2 = (list *)malloc(sizeof(list));
l0->data = 'A';
l0->prev = NULL;
l0->next = l1;
l1->data = 'B';
l1->prev = l0;
l1->next = l2;
l2->data = 'C';
l2->prev = l1;
l2->next = NULL;
struct list *ltest = (list *)malloc(sizeof(list));
ltest = l0;
printf("%c\n", l0->data);
ltest = Next(ltest);
printf("%c\n", ltest->data);
ltest = Next(ltest);
printf("%c\n", ltest->data);
ltest = Prev(ltest);
printf("%c\n", ltest->data);
ltest = Prev(ltest);
printf("%c\n", ltest->data);
return 0;
}
実行結果
A
B
C
B
A
前後の移動が実装できた.
その3 リストを後ろに伸ばそう
これが今回リストを実装しようと思った大きな理由.
最後尾から更に後ろに行こうとしたときに, 行き先がなくてエラーを吐くのではなく要素を増やして対応したい.
というわけでNext()関数をバージョンアップしていく.
list *Next(list *l1){
if(l1->next == NULL){
struct list *l2 = (list *)malloc(sizeof(list));
l1->next = l2;
l2->prev = l1;
l2->next = NULL;
return l2;
}else{
return l1->next;
}
}
行き先がNULLなら新しい要素をくっつけるだけ.
試してみよう.
...
...
int main(void){
struct list *l0 = (list *)malloc(sizeof(list));
struct list *l1 = (list *)malloc(sizeof(list));
struct list *l2 = (list *)malloc(sizeof(list));
l0->data = 'A';
l0->prev = NULL;
l0->next = l1;
l1->data = 'B';
l1->prev = l0;
l1->next = l2;
l2->data = 'C';
l2->prev = l1;
l2->next = NULL;
struct list *ltest = (list *)malloc(sizeof(list));
ltest = l0;
printf("%c\n", l0->data);
ltest = Next(ltest);
printf("%c\n", ltest->data);
ltest = Next(ltest);
printf("%c\n", ltest->data);
ltest = Next(ltest);
ltest->data = 'D';
printf("%c\n", ltest->data);
ltest = Prev(ltest);
printf("%c\n", ltest->data);
ltest = Next(ltest);
printf("%c\n", ltest->data);
return 0;
}
実行結果
A
B
C
D
C
D
ちゃんと繋がっていることがわかる.
その4 メモリを解放しよう
今回の実装ではmalloc関数を使っているため, すべてが終わったらメモリを解放しなければならない.
繋がっているすべての要素を解放する関数を作る.
今まで実行していたときにメモリを解放してなかったのは内緒
先頭のポインタを与えて再帰的に解放する.
void Free(list *l){
if(l->next == NULL){
free(l);
}else{
Free(Next(l));
free(l);
}
}
完成！！！！
list.c
#include <stdlib.h>
typedef struct list list;
struct list{
char data;
list *prev;
list *next;
};
list *Next(list *l1){
if(l1->next == NULL){
struct list *l2 = (list *)malloc(sizeof(list));
l1->next = l2;
l2->prev = l1;
l2->next = NULL;
return l2;
}else{
return l1->next;
}
}
list *Prev(list *l){
return l->prev;
}
void Free(list *l){
if(l->next == NULL){
free(l);
}else{
Free(Next(l));
free(l);
}
}
これでとりあえず使えそうな双方向リスト(っぽいもの)ができた. 私の次回作にご期待ください.
おわりに
今回はとりあえず動けばよかったのでこういう実装だが, 本当は様々な型に対応させたりメモリ効率を考えたりしないといけないと思うので時間があるときはちゃんと考えて作りたい.
きっと今後役立つと思うので, いずれヘッダファイルとか書いて使いやすく整えていきたい.