ソフトウェアエンジニアを目指す人のブログ

ソフトウェアエンジニアになるために勉強したことを書いていきます

Basic Data Structure (Cousera Data Structures week 1)

久しぶりのブログ更新になります。やはり仕事が忙しいなかなか勉強の時間がとれませんね。。

さて今回からcouseraのdata structures コースをやって行きたいと思います。

www.coursera.org

やはりソフトウェアエンジニアを目指すならデータ構造の知識は必須ですよね。ということで、今後から備忘録も兼ねてdata structureコースの各週の内容のサマリを書いていきたいと思います。

Week 1 Basic Data Structures

Arrays

  • Array(配列)は等しいサイズの要素で構成されているメモリ上の連続した空間である
    • 各要素は連続した整数でインデックスされている
  • 各要素へのアクセスは定数オーダーの時間で行える
  • 配列の最後への要素の追加、削除は定数オーダー時間
  • 任意の場所の追加、削除は線形オーダー時間 (O(n))

Singly-Linked List

f:id:rikeiin:20180402000221p:plain

SIngly-Linked List(単方向リスト)は各要素は値となるkeyと次の要素のアドレスを示すポインタをもっている。 単方向リストに対する操作は以下のようなものがあげられる。

f:id:rikeiin:20180402000734p:plain

各操作のオーダーは以下のようになる。

f:id:rikeiin:20180402001120p:plain

ポイントはリストの頭に対する操作はO(n)の時間でできるがリストに末尾に対する操作はO(n)であること(リストの先頭から辿っていく必要があるから)。 ただし、末尾のアドレスをもつtailがあればpushbackとtopbackはO(1)でできる。

Doubly-Linked List

f:id:rikeiin:20180402001627p:plain

Doubly-Linked List(双方向リスト)の各要素は値を保持しているkeyと前後の要素のポイントを持っている。

双方向リストに対する各操作のオーダーは以下のようになる。 f:id:rikeiin:20180402002047p:plain

ポイントは単方向リストと違い、前の要素へのポイントをもっているため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はキューを用いて実装できる。 f:id:rikeiin:20180402181818p:plain

木構造まとめ

  • 木構造はキーと子を持つ
  • 木の探索方法はDFS(pre-order, in-order, post-order)とBFSがある
  • 木の探索は一般的に再帰的なアルゴリズムで実装される。