このセクションの重要性#
単方向リストは非常に基本的なリンク構造であるため、C 言語を使用して単方向リストを記述する方法を学ぶと、ヒープ、スタック、双方向リスト、ハッシュテーブルなどの C での記述は簡単になります。
初心者の場合、コードを自分で入力することを強くお勧めします。
単方向リストのノード#
図のように、単方向リストのノードはデータフィールドとポインタフィールドに分かれており、それらを一体として扱い、ノードと呼びます。後で、ノードを表すために構造体を使用します。
データフィールドは、その名の通り、データを格納する場所です。
ポインタフィールドは、ポインタ変数を格納する場所であり、ポインタは次のノードのアドレスを指します。
単方向リストの表現#
単方向リストは、線形リストのリンク表現と実装です。ノードをリンクして、単方向リストを形成します。
ノードを表す構造体の定義#
C 言語でノードをどのように記述するか？ ここではstructを使用します。
struct node {
/* 次のノード */
struct node *next;
/* 値 */
int data;
};
まず、構造体を定義しました。構造体のタグはnodeです。
次に、2 つの属性を持っています。1 つはint型のdataであり、これは先ほど言及したデータフィールドです。もう 1 つはポインタフィールドです。
struct node *nextをどのように理解すればよいのでしょうか？
ポインタフィールドはポインタ変数を格納する場所であり、この変数の名前はnextです。また、このポインタは次のノードのアドレスを指しているため、言い換えれば、このポインタはノードを表すために定義した構造体を指しています。したがって、このポインタ変数の型はstruct nodeです。アスタリスク*はポインタ変数であることを示しています。したがって、合わせてstruct node *nextとなります。
最後に、便宜上、typedefキーワードを使用してstruct nodeに別名を付けることができます。
typedef struct node {
/* 次のノード */
struct node *next;
/* 値 */
int data;
}list;
これにより、後続のコードでlistはstruct nodeと同等となります。
たとえば、この構造体を使用して新しいノードを作成する場合、list *new_nodeはstruct node *new_nodeと同等です。
単方向リストの作成#
list * create_list()
{
/* 新しいノードを作成します。typedefキーワードを使用したため、node *headとstruct node *headは同等です */
list *head = (list *)malloc(sizeof(list));
if(head==NULL) return NULL;
/* ノードを初期化します */
head->data = 0; // ヘッドノードのデータフィールドは、リストの長さを表すために使用します
head->next = NULL;
return head;
}
この関数は単方向リストを作成し、ヘッドポインタを返します。
ヘッドポインタはヘッドノードのアドレスを指すポインタであり、ノードの次のノードを指すポインタと同じ型です。
まず、malloc関数を使用して、listサイズのメモリを確保し、そのメモリブロックの先頭アドレスを指すポインタを返します。同時に、このポインタをヘッドポインタ変数に割り当てます。
次に、このポインタがNULLであるかどうかをチェックし、NULLであればメモリの割り当てに失敗したことを意味します（通常は起こりません）。
その後、このノードを初期化します。
最後に、関数はヘッドポインタを返し、終了します。
なぜヘッドノードを設定するのですか？
ヘッドノードのデータフィールドは通常意味を持ちませんが、ここでは後続の挿入と削除の操作を容易にするために設定されています。ヘッドノードはリストに必須ではありません。
ヘッドノードの次の最初の要素ノードは、最初の要素ノードと呼ばれます。
単方向リストの挿入#
次の状況を考えてみましょう。新しいノードnをxノードの後に挿入する必要があります。
破線は切断を表します。同様に、次のようにすると一般的なアイデアかもしれません。
x->next = n;
n->next = x->next;
明らかにこれは間違っています。x->next = nを実行した後、n->next = x->nextはn->next = nと同じですので、正しい方法は次のようになります。
n->next = x->next;
x->next = n;
完全な挿入関数：
挿入関数は、挿入されるノードのリストのポインタhead、新しいノードのデータdata、および挿入する位置posの 3 つの引数を受け取ります。
list * list_insert_node(list *head, int data, int pos)
{
int i;
list *curr = head;
/* 挿入位置がリストの長さよりも大きい場合、無効な操作です */
if(pos > curr->data) return NULL;
/* ノードを作成し、初期化します */
list *node = (list *)malloc(sizeof(list));
if(node==NULL) return NULL;
node->data = data;
node->next = NULL;
/* リストを走査し、挿入位置を見つけます */
for(i=0;i<pos;i++){
curr = curr->next;
}
/* 挿入 */
node->next = curr->next;
curr->next = node;
/* リストの長さ+1 */
head->data++;
return head;
}
main 関数でテストできます：
list *l = create_list();
printf("現在のリストの長さ：%d\n", l->data);
list_insert_node(l, 1, 0);
printf("現在のリストの長さ：%d\n", l->data);
gcc でコンパイルして実行します：
gcc -fsanitize=address -fno-omit-frame-pointer -g linked_list.c && ./a.out
正常に出力され、メモリエラーメッセージが表示されません：
現在のリストの長さ：0
現在のリストの長さ：1
単方向リストのトラバース#
非常に簡単で、説明は省略します。
/* リストのデータを出力しますが、ヘッドノードのデータは含まれません */
void print_list(list *head)
{
list *curr = head->next;
while (curr)
{
printf("%d \t", curr->data);
curr = curr->next;
}
printf("\n");
}
単方向リストの削除#
head の後のノードを削除する場合、head->next = head->next->nextとするだけで、削除されるノードを解放することを忘れないでください。
このアイデアに基づいて：
list *list_delete_data(list *head, int pos)
{
int i;
list *curr = head;
/* 削除位置がリストの長さよりも大きい場合、無効な操作です */
if(pos > curr->data) return NULL;
/* 削除するノードの前のノードのポインタをリストで見つけます */
for(i=0;i<pos;i++){
curr = curr->next;
}
// 削除されるノードを一時的に記録します
list *temp = curr->next;
// ノードを削除します
curr->next = curr->next->next;
// 削除されるノードのメモリを解放します
free(temp);
head->data--;
return head;
}
単方向リストのテスト#
これで、基本的なリストが完成しました。main関数でテストできます。
int main()
{
int i;
list *l = create_list();
// 複数回データを挿入します
for(i=0;i<5;i++){
list_insert_node(l, i, 0);
print_list(l);
}
list_delete_data(l, 0);
print_list(l);
return 0;
}
コンパイルして出力します：
# gcc -fsanitize=address -fno-omit-frame-pointer -g linked_list.c && ./a.out
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0
3 2 1 0
完全なコード#
完全なコードについては、コードリストを参照してください。
https://github.com/austin2035/learn-data-structures