コンピュータサイエンスの基礎・上級①：データ構造入門

本記事はコンピュータサインス学習サービスRecursionの学習記録です。

次の回▶
記事まとめ

効率的なデータの格納と操作

• データ構造とは、コンピュータ上でデータを効率的に格納・利用するための手法。
  • データ構造には、データの格納やアクセス、操作方法に関するルールや手順が存在する。
  • 配列、リスト、スタック、キュー、ツリー、グラフなどが代表例。
• データ構造の選択は、データの性質や操作要件に依存する。
  • 例えば、順番にデータを処理する必要がある場合はリストやキュー、ランダムアクセスを効率的に行いたい場合には配列やツリーが適している。
• データ構造入門では、時間計算に狩る触れながら配列や連結リストといった基本的なデータ構造について学ぶ。

本記事では連結リストのうち片方向リストについて学習する。
配列と比較したときの各操作にかかる時間計算量は以下の通り。

データ構造	インデックス操作	挿入操作	削除操作	時間	備考
配列	O(1)	O(n)	O(n)	高速	配列は連続メモリにデータが格納されているため、インデックス操作はO(1)で高速。挿入・削除には要素のシフトが必要。
片方向リスト	O(n)	O(1)	O(1) or O(n)	遅い～高速	インデックス操作は先頭から順に辿る必要があるためO(n)。挿入は既知の位置ならO(1)で可能。削除は最初ならO(1)、特定位置ならO(n)。

連結リスト(Linked List)

連結リストは、配列とは異なり、データが連続したメモリブロックに格納されないデータ構造である。
データは、ポインタを使用して接続されるノードによって構成される。
各ノードは次のノードへの参照をもち、これを辿ることでリスト全体を走査できる。

片方向リスト(Singly Linked List)

片方向リストは、連結リストの基本形で、各ノードが次のノードを指すポインタを持っている。
よって、先頭ノードから次のノードへの参照を使ってリスト全体を順番に辿ることができる。
ノードの追加や作事にあたっては、このポインタを適切に更新する。

ポインタは、ほかの変数のメモリアドレスを指す変数で、連結リストや動的データ構造において重要な役割を果たす。
例えば、片方向リストでは次のノードへの参照がポインタとして格納され、ノード間の接続を維持する。

// ポインタと聞くとC++の文脈でよく使われる印象です。

片方向リストの操作

インデックス操作

連結リストにおいて指定されたインデックスの要素のアクセスするには、前の要素を順にたどる必要がある(要素がメモリ上に非連続的に配置されるため)。
このため、インデックス操作にはO(n)の時間がかかる。
一方、配列ではインデックス演算はO(1)の時間で実行でき、連続したメモリ領域にデータが格納されえるため、指定したインデックスに直接アクセスできる。

挿入操作

連結リストでは、特定のノードの後ろに新しいノードを追加する挿入操作がO(1)で実行できる。
例えば、既知のノードAの後ろにノードBを挿入する場合、次の手順を踏む。
1. Aの次のノードへの参照を一時的に保存
2. Aの次にBを挿入
3. Bの次に元のAの次のノードを設定
この方法で新しいノードを効率的にリストに追加できる。

削除操作

連結リストにおいて先頭のノードを削除する場合、その次のノードを新たな先頭として設定することでO(1)で削除できる。
ただし、特定のノードを削除するには、そのノードの位置を探索する必要があるため線形時間O(n)がかかる。

メモ

片方向リストは、配列と比べて挿入・削除操作の時間計算量が少ない=O(1)で済む点が優れていると理解した。
しかし、ノードの位置が未知の場合はO(n)の計算量になるとのことで、メリットがよくわからなくなった。
以下に調べてみたことをメモしてみる。

片方向リストが配列より優先される状況

場面	理由	例
挿入・削除が頻繁	片方向リストは挿入・削除が既知の位置ならO(1)で効率的。 一方、配列はシフトが必要でO(n)の時間がかかるため。	タスク管理システムやリクエストキューなど、 動的なデータ処理が求められるアプリケーション。
メモリが断片化している場合	配列は連続したメモリが必要だが、片方向リストはメモリのどこにでもノードを配置できるため、メモリ効率が良い。	組み込みシステムや動的メモリ管理が必要な環境。
データサイズが不定	配列はサイズが固定だが、片方向リストは動的にサイズ変更が可能で、柔軟に対応できる。	ログ管理システムやリアルタイムデータのストリーム処理など。
順次アクセスがメインで、 ランダムアクセス不要	ランダムアクセスは遅いが、順次処理がメインなら片方向リストは挿入・削除が効率的に行える。	ファイルストリーミングやトラバース処理など、順次データ処理が必要な場面。

以上。
使いこなすには時間がかかりそうだが、検討やコードリーディングする際の解像度が少し上がった気がする。