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