ようこそ！

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software Engineer

アルゴリズムとデータ構造の重要性

データ構造とアルゴリズムで
- 日常の課題を解く
- 効率的なコードで実装
本コースは任意の言語で教授可能

アルゴリズムとデータ構造

アルゴリズム：課題を解く手順の集合
1. 設計
2. コード化

データ構造： アルゴリズム実行時にデータを保持・操作
- 発展データ構造：連結リスト、スタック、キューなど

連結リスト

パン作りの手順を含む連結リストの視覚例。

リンクでつながるデータの列

連結リスト ― 構造

連結リストのノードの図。

連結リスト ― 構造

連結リストのノードの図。最初の部分に「DATA」とある。

連結リスト ― 構造

連結リストのノードの図。最初の部分に「DATA」、第2部分に「NEXT」とポインタがある。

連結リスト ― 構造

連結でつながった2つのノードの図。

連結リスト ― 構造

連結でつながった複数ノードの図。

連結リスト ― 構造

最後のノードが null を指す連結リストの図。

連結リスト ― 構造

最初のノードに「HEAD」とある連結リストの図。

連結リスト ― 構造

最後のノードに「TAIL」とある連結リストの図。

連続したメモリに置く必要はない
データは任意の空きアドレスに配置可

単方向連結リスト

単方向連結リストの図。

1 本のリンク：単方向連結リスト

双方向連結リスト

双方向連結リストの図。

双方向に 2 本のリンク：双方向連結リスト

連結リスト ― 実用途

他のデータ構造の実装：
- スタック
- キュー
- グラフ
前後にたどってアクセス
- ウェブブラウザ
- 音楽プレイリスト

連結リスト ― Node クラス

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

連結リスト ― LinkedList クラス

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None

連結リスト ― メソッド

insert_at_beginning()
remove_at_beginning()
insert_at_end()
remove_at_end()
insert_at()
remove_at()
search()
...

連結リスト ― insert_at_beginning

単方向連結リストの図。

連結リスト ― insert_at_beginning

単方向連結リストと新しいノードの図。

 def insert_at_beginning(self, data):
    new_node = Node(data)

    if self.head:

連結リスト ― insert_at_beginning

新ノードが接続された単方向連結リストの図。

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head

連結リスト ― insert_at_beginning

新ノードが接続され、そのノードに「HEAD」とある単方向連結リストの図。

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node

連結リスト ― insert_at_beginning

空の連結リストに新ノードがある図。

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
    else:

      self.tail = new_node      
      self.head = new_node

連結リスト ― insert_at_end

  def insert_at_end(self, data):
    new_node = Node(data)
    if self.head:  

      self.tail.next = new_node

      self.tail = new_node

    else:

      self.head = new_node
      self.tail = new_node

連結リスト ― search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

「current_node」が最初のノードを指す単方向連結リストの図。

連結リスト ― search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

「current_node」が2番目のノードを指す単方向連結リストの図。

連結リスト ― search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

  return False

「current_node」が3番目のノードを指す単方向連結リストの図。

連結リスト ― 例

空の連結リストに新ノードがある図。

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

連結リスト ― 例

連結リストの末尾に新ノードが追加された図。

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll")

連結リスト ― 例

連結リストの先頭に新ノードが追加された図。

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 
sushi_preparation.insert_at_beginning("assemble")

連結リスト ― 例

連結リストの図。

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Passons à la pratique !

Pythonで学ぶデータ構造とアルゴリズム