1.単方向リスト(Singly Linked List)とは
別名「線形リスト（Linear List）」又は「連結リスト」とよばれ、データ構造の基本アルゴリズムの一つです。
例えば、下の図のようなイメージです。
| Head データ1のアドレス |
-> |
データ1 データ2のアドレス |
-> |
データ2 データ3のアドレス |
-> |
データ3 NULL |
Headとは、リストの先頭のデータのアドレスを示します。ここが「NULL」の場合、データは存在しないと言う事が一般的です。
そして「データ x」が「次のデータ xへのアドレス」を格納して単方向リストを形成します。
また「データ x」の「次のデータ xのアドレス」を格納している変数が「NULL」の場合リスト構造の最後を示します。
2.先頭にデータを追加
1.新規データの「次のデータのアドレス」にHeadが示す「次のデータのアドレス」を代入
2.新規データのアドレスを「Head」に代入
| Head データ1のアドレス |
-> |
データ1 データ2のアドレス |
-> |
データ2 NULL |
実行後
| Head 新規データアドレス |
-> |
新規データ データ1のアドレス |
-> |
データ1 データ2のアドレス |
-> |
データ2 NULL |
void HeadInsert(LIST **Head, LIST *Node)
{
/* データを追加 */
Node->next = *Head;
*Head = Node;
}
3.最後にデータを追加
1.リストにデータが無ければ、先頭にデータを追加し終了
2.リストの最後のデータを検索
3.最後のデータに新規データのアドレスを代入
4.新規データに「NULL」を代入
| Head データ1のアドレス |
-> |
データ1 データ2のアドレス |
-> |
データ2 NULL |
実行後
| Head データ1のアドレス |
-> |
データ1 データ2のアドレス |
-> |
データ2 新規データアドレス |
-> |
新規データ NULL |
void TailInsert(LIST **Head, LIST *Node)
{
LIST *p;
if(*Head == (LIST *)NULL){
/* リストにデータが無い場合、先頭に追加 */
HeadInsert(Head, Node);
}else{
/* リストの最後を検索 */
for(p=*Head; p->next!=(LIST *)NULL; p=p->next);
/* データを追加 */
p->next = Node;
Node->next = NULL;
}
}
4.データの挿入
1.挿入位置を検索
2.新規データの「次のデータのアドレス」に
挿入位置のデータに代入されている「次のデータのアドレス」を代入
3.挿入位置のデータの「次のデータのアドレス」に新規データのアドレスを代入
| Head データ1のアドレス |
-> |
データ1 データ2のアドレス |
-> |
データ2 NULL |
実行後
| Head データ1のアドレス |
-> |
データ1 新規データアドレス |
-> |
新規データ データ2のアドレス |
-> |
データ2 NULL |
void ListInsert(LIST **Head, LIST *Node, int Position)
{
LIST *p;
Position--; /* 挿入位置の一つ前にする*/
if(*Head == (LIST *)NULL || Position<=0){ /* 挿入位置が先頭なら */
HeadInsert(Head, Node);
}else{ /* 挿入位置は先頭でない */
if(GetNodeTotal(Head)<Position){ /* 挿入位置がリストの最後より後ろなら */
TailInsert(Head, Node);
}else{
p=GetNode(Head, Position); /* 挿入位置のNodeを取得 */
Node->next = p->next; /* データを挿入 */
p->next = Node;
}
}
}
5.データの削除
1.削除データの位置を検索
2.削除データのアドレスが格納されているデータに
削除データに代入されている「次のデータのアドレス」代入
| Head データ1のアドレス |
-> |
データ1 削除データアドレス |
-> |
削除データ データ2のアドレス |
-> |
データ2 NULL |
実行後
| Head データ1のアドレス |
-> |
データ1 データ2のアドレス |
-> |
データ2 NULL |
void DeleteNode(LIST **Head, int Position)
{
LIST *p, *Node;
Position--; /* 削除位置の一つ前にする */
if(*Head != (LIST *)NULL){ /* LISTが存在しないなら終了 */
if(Position==0){ /* 削除位置が先頭なら解放 */
p=*Head;
*Head = p->next;
NodeFree(p);
}else if(GetNodeTotal(Head)>Position && Position>0){ /* 削除位置がList内なら */
p=GetNode(Head, Position); /* 削除位置のNodeを取得 */
Node = p->next; /* Nodeを解放する */
p->next = Node->next;
NodeFree(Node);
}
}
}