【C言語】リスト構造の使い方を学んでデータの挿入や削除が簡単になる

C言語を学ぶ過程でリスト構造の理解を避けて通ることはできません。

リストはデータ構造の一つです。

今までは配列を使った処理を中心に学んできたのですが、今回はリストの使い方を新しく覚えたのでその備忘録です。

リストとは?

f:id:taiyoutan:20211017174610j:plain

リストとは代表的なデータ構造のうちの一つです。

データ構造とはデータの集まりをコンピュータプログラムで扱いやすいように、一定の形式で格納したもの。

リストの特徴について一言で説明すると、データの入れ替えがしやすいように各データが次の順番のデータの情報を持っているという特徴があります。

配列もデータ構造のうちの一つで、アルゴリズムに適したデータ構造が存在するわけです。

リストの特徴

f:id:taiyoutan:20211109102916j:plain

リスト最大の特徴といえば各ノードが順番の情報を持っていることです。

■ ノードとは? ■

ノードとは、データ部とポインタ部から構成されている情報のかたまりである

データ部:リストで管理したいデータが格納されている
ポインタ部:次のノード(の場所)を示すデータが格納されている

データ部にデータを格納し、それぞれのポインタ部に次のノード(の場所)を指し示す情報が格納されています。

そのため、データ間の順番や繋がりが分かるようになっているのです。

学校の連絡網をイメージしてみると少し親近感が湧くかなと思います。

ちなみに配列も複数のデータを一つずつ要素に格納するといった点ではリストと同じ括りですが、アルゴリズムの点で違いが生まれます。

配列とリストの違い

f:id:taiyoutan:20211109103754p:plain

配列とリストがどのように異なるのか、具体的に説明していきます。

配列のデータ構造

ある配列に5つのデータが入っていると仮定します。

このデータを並べる際、途中に空白をつくっていけないものとして、3番目のデータ(下図C)を削除したとします。

削除するだけだと3番目が空白になってしまうので、3番目以降のデータを左にずらさなくてはなりません。

■ 配列のデータ構造 ■

元の配列                   A → B → C → D → E
Cを削除                  A → B →  C  → D → E
DとEを左にずらす A → B → D → E

削除と同時に「DとEを左にずらす」という作業が必要になるので、配列の要素数が多いほど整理するのに時間がかかってしまいます。

リストのデータ構造

リスト構造はノードのポインタ部が次の順番の情報を持っているので、削除における処理が少なくて済みます。

まず3番目のデータを削除します。

Bは次のCを指す情報をDを指す情報に書き換えることによって、DとEをずらす作業が必要ないのです。

■ リストのデータ構造 ■

元のデータ         A → B(toC)→ C → D → E
Cを削除              A → B(toC)→  C  → D → E
Bの情報を変更   A → B(toD)→  C  → D → E

リストを使うことによって削除におけるデータの挿入や削除が簡単になります。

もしこのようなデータが大量に存在する場合、配列のように変更があるたびにデータをずらす処理をしていたら大変ですよね。

リストを使うとデータ数に関わらず1回の処理で済みます。

リストを学んで思ったこと

リストはとても便利ですが、ややプログラムが複雑です。

みなさんも冗長な処理にならないように気を付けてください。

コメントを残す

メールアドレスが公開されることはありません。