単方向リストの理解とJavaでの実装
線形単方向リスト(Singly-linked linear list)は、最も基本的なデータ構造のひとつです。また色々なデータ構造に対する考え方の基礎を学ぶことができるので良い題材です。 Java の java.util.LinkedList はその実装を見てみれば分かる通り双方向(Doubly)連結リストなので、これを参考にしながら単方向リストについてざっくりと実装をして、理解を深めました。
データ構造入門:基礎用語と概念の確認
単方向リストについて考える前に、データ構造とアルゴリズム全般の基礎知識を確認しておきましょう。
- データ構造(Data Structure) とは
- データを効率的に使用できるように組織化する方法。配列、ファイル、連結リスト、スタック、キュー、木、グラフなど
- 線形データ構造 要素は順番にアクセスされる。データが連続している必要はない。
- 非線形データ構造 木、グラフなど
- 抽象データ型(ADT, abstract data type) とは
- 基本データ型は基本演算を暗黙的にサポートしているが、同様にユーザ定義型に...