4.Data Structure

データ構造とは

データ構造(データこうぞう、英: data structure)は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。
ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム(アルゴリズム)の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。

基本的なデータ構造

クラス(class)は、クラスベースのオブジェクト指向においてオブジェクトの設計図にあたるもの。抽象データ型の一つ。任意のデータ型を自由に組み合わせて作るデータ構造。

  • 配列 (線形)  ーー 2-1 配列
  • クラス  ーー 2-3 クラス
  • スタック ーー  4-1 スタック
  • キュー  ーー  4-2 キュー

コレクション

コレクションリストセット)や マップ は、オブジェクトの集合を扱うための仕組みです。

カテゴリ クラス 説明
List系 ArrayList 配列を扱います。
LinkedList 配列を扱います。挿入・削除が高速です。
Vector 配列を扱います。
パフォーマンスが悪いため現在ではあまり推奨されない古いクラスです。
Set系 HashSet 値の重複を許さない順不同の要素集合を扱います。
TreeSet 値の重複を許さないソートされたの要素集合を扱います。
Map系 HashMap キーと値の組からなる要素の集合を扱います。
TreeMap キーと値の組からなる要素の集合を扱います。
キーでソートされています。
【コレクションクラスの比較】
ArrayList LinkedList HashMap TreeMap HashSet TreeSet
インタフェイス List List Map Map Set Set
要素の重複 × × × ×
null値の要素 × ×
自動ソート × × × ×

List構造 コレクションクラス

List構造は、要素を順番付けして管理するデータ構造です。
ArrayList」「LinkedList」の2種類があります。

List構造

要素がインデックス(番号)順に並んでいるので、番号を指定して要素の取得、挿入、更新、削除ができます。また、Iteratorや拡張for構文を使って先頭から順番に要素を取得することも出来ます。
ArrayListは要素の取得が早いが挿入や削除が遅い、LinkedListは要素の挿入や削除は早いが取得が遅いという特徴があります。
List構造は、要素の重複は可能です。

Map構造 コレクションクラス

Map構造は、キーと値をセットにしたものを1つの要素として管理するデータ構造です。
HashMap」「TreeMap」の2種類があります。

Map構造

要素がキーと値で管理されているので、キーを指定して値の取得や更新、削除を行います。
HashMapは格納順は管理されませんが、TreeMapはキーによって自動的にソートして管理されます。
また、HashMapはキーと値にnullを使用することが可能ですが、TreeMapはnullは使用することができません。
Map構造は、キーによって値を管理するためキーの重複は不可です。
(同じキーがセット(put)された場合は上書きされます。)

Set構造 コレクションクラス

Set構造は、要素を順番付けしないで管理するデータ構造です。
HashSet」「TreeSet」の2種類があります。

Set構造

Listのような順番付けや、Mapのようなキー管理もないため、要素の取得にはIteratorや拡張for構文で取得します。
このようなことからHashSetは要素の取得順は保証されませんが、TreeSetは自動ソートされて管理されるのでソートされた順番で要素が取得されます。
また、HashSetは要素にnullを使用する事が可能ですが、TreeSetはnullを使用する事ができません。
Set構造は、要素の重複は不可です。(同じキーがセット(add)された場合は上書きされます。)

参考:

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

Algorithms and Data Structures

ツールバーへスキップ