Basic Data Structure (Cousera Data Structures week 1)
久しぶりのブログ更新になります。やはり仕事が忙しいなかなか勉強の時間がとれませんね。。
さて今回からcouseraのdata structures コースをやって行きたいと思います。
やはりソフトウェアエンジニアを目指すならデータ構造の知識は必須ですよね。ということで、今後から備忘録も兼ねてdata structureコースの各週の内容のサマリを書いていきたいと思います。
Week 1 Basic Data Structures
Arrays
- Array(配列)は等しいサイズの要素で構成されているメモリ上の連続した空間である
- 各要素は連続した整数でインデックスされている
- 各要素へのアクセスは定数オーダーの時間で行える
- 配列の最後への要素の追加、削除は定数オーダー時間
- 任意の場所の追加、削除は線形オーダー時間 (O(n))
Singly-Linked List
SIngly-Linked List(単方向リスト)は各要素は値となるkeyと次の要素のアドレスを示すポインタをもっている。 単方向リストに対する操作は以下のようなものがあげられる。
各操作のオーダーは以下のようになる。
ポイントはリストの頭に対する操作はO(n)の時間でできるがリストに末尾に対する操作はO(n)であること(リストの先頭から辿っていく必要があるから)。 ただし、末尾のアドレスをもつtailがあればpushbackとtopbackはO(1)でできる。
Doubly-Linked List
Doubly-Linked List(双方向リスト)の各要素は値を保持しているkeyと前後の要素のポイントを持っている。
双方向リストに対する各操作のオーダーは以下のようになる。
ポイントは単方向リストと違い、前の要素へのポイントをもっているためpopback()とAddBefore(Node, key)のオーダーがO(1)になっていること。
リストまとめ
- リストの先頭要素の挿入と削除はO(1)
- 末尾のアドレスを保持していて双方向リストである場合、末尾の要素の挿入と削除はO(1)
- 要素の検索はO(n)
- リストの要素はメモリ上で連続的である必要はない
- 双方向リストである場合、ある要素の前後の挿入、削除はO(1)
Stack
Stackは以下の操作を行うデータ構造である
- Push(key)：スタックに新しいキーを追加する
- Key Top()：直近のキーを返す
- Key Pop()：直近のキーをスタックから削除して返す
- Boolean Empty()；スタックに要素が存在するか
スタックはいわゆるLIFO(Last In Fast Out)のデータ構造であり、スタックは配列やリストで実装できる。スタックに対する操作はO(1)である。
Queue
Queueは以下の操作を行うデータ構造である。
- Enqueue(Key)：キューにキーを追加する
- Key Dequeue()：最後に追加されたキーを削除して返す
- Boolean Empty()：キューに要素が存在するか
Queueはtailを持ったリスト、もしくは配列で実装できる。 Queueに対する操作はO(1)である。
Tree
木構造は空、もしくはキーと子のリストを持つ要素で構成されるデータ構造である。 特に二分木の場合、ノードはkeyとleft, rightを持つ。
木構造の探索方法は主に以下の2つ。
- Depth-first
- 他のサブツリーを探索する前に一つのサブツリーを完全に探索する
- Breadth-first
- 次の階層に行く前にある一階層のノードをすべて探索する。
Depth-firstにはさらに3つの探索方法がある。
- InOrderTraversal(tree)
- InOrderTraversal(tree.left)
- print(tree.key)
- In OrderTraversal(tree.right)
- PreOrderTraversal(tree)
- print(tree.key)
- PreOrderTraversal(tree.left)
- PreOrderTraversal(tree.right)
- PostOrderTraversal(tree)
- PostOrderTraversal(tree.left)
- PostOrderTraversal(tree.right)
- print(tree.key)
Breadth-firstはキューを用いて実装できる。
