プログラミング技法とデータ構造

連結リストとは

あるデータから次のデータと接続させ，何個もデータつなげた一連のデータ構造のことを連結リスト(リンクドリスト)と呼ぶ．連結リストはデータ構造の中でも基本的なものである．

この連結リストは，前回説明した構造体とポインタを利用して構築することができる．

連結リストでは，一般にリストに含まれるひとつのデータ要素のことを，そのまま「要素」(element)，あるいは「ノード」(node)，または「セル」(cell)などと呼ぶ．また，こうした要素に含まれる次の要素への接続情報のことを，そのまま「ポインター」や「リンク」と呼ぶ．

線形リスト

一方向にだけ接続する方式で，C言語では次のように実現される．

typedef struct list{
  int data;
  struct list *next;
} LIST;

リストの要素として構造体を宣言する．これをLIST型としよう．LIST型は，必要なデータ項目(ひとつだけとは限らない)と，次のデータ要素へのポインタを格納するために自分の構造体型(LIST型)へのポインタから構成される．

実際のプログラム中では，この型を用いて次のようにLIST型を初期化する．

LIST *head; //リストの先頭へのポインタ
LIST *tail; //リストの最後へのポインタ
LIST *p;    //リスト中を移動するのに使用するための作業用ポインタ

head = (LIST *)malloc(sizeof(LIST)); //まずはLIST構造体一個を確保してheadに接続
head->next = (LIST *)malloc(sizeof(LIST)); //headの次にもう一個接続，計2個目
head->next->next=0;   //その次は無いので，0値を入れておく．アドレスが0のことをNULLと呼ぶ．
tail = head->next;    //この場合2番めが最後なのでtailにつなぐ

この線形リストは，nextによって次の要素へ接続されているため，nextをたどれば最初から最後の要素まで探索することができる．

p=head; //最初から
p=p->next; //1つたどる
p=p->next; //さらにたどる
...
p=p->next; //いつかは最後にたどりつく．最後かどうかはnextがNULLかどうかで判断できる

通常，線形リストをたどりながら処理するプログラムは次のように書く

　for(p=head; p!=NULL; p=p->next)
  {
     pを使った処理部分
  } 

線形リストの特徴

線形リストの長所は，リストへの追加・削除が簡単なことである．

線形リストの短所は，リストのn番めへのアクセスに，先頭からn回ポインタをたどらないといけない点である．ただし，通常は，リストの先頭と最後はそれを指し示すポインタ変数を用意しておくことが多く，最初と最後だけには一発でアクセス可能である．

線形リストの追加・削除

線形リストへの追加は次のように行える．これで，pが指す要素とp->nextが示す要素の間に，新しい要素newを挿入することができる．

 LIST *p;    //挿入する位置の直前
 LIST *new;  //追加したい要素

 new = malloc(sizeof(LIST)); //新しい要素newを確保
 new->data = 777; //何か新しいデータ
 if(new==NULL)
   exit(EXIT_FAILURE); //失敗終了
 new->next = p->next;  //現在のpの後続をコピー，newに後続をつなぐ
 p->next = new;        //その上でpの後続としてnewを代入
 

逆に，ある要素を削除したい場合には次のようにする．

 LIST *p;    //削除する位置の直前
 LIST *del;  //削除したい要素の保存用

 del = p->next; //削除したい要素はこれ
 p->next = p->next->next; //pの次を，次の次へ
 free(del);  //削除した要素を開放