はじめに

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

Miriam Antona

Software Engineer

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

• データ構造とアルゴリズムでできること
  • 日常の問題を解決する
  • 効率的なコーディング
• 本コースはお好きなプログラミング言語で応用可能

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

• アルゴリズム：問題を解くための一連の手順

  1. 設計

     

  2. コード化

     

• データ構造： アルゴリズムを実行する際にデータを保持・操作する仕組み
  • 高度なデータ構造：連結リスト、スタック、キューなど

連結リスト

• リンクでつながったデータの並び

連結リスト - 構造

連結リスト - 構造

連結リスト - 構造

連結リスト - 構造

連結リスト - 構造

連結リスト - 構造

連結リスト - 構造

連結リスト - 構造

• データはメモリ上で連続した場所に置く必要がない
• データは利用可能なメモリアドレスがあればどこでも配置できる

単方向連結リスト

• リンクが1つ：単方向連結リスト

双方向連結リスト

• 両方向にリンクがある：双方向連結リスト

連結リスト - 実際の用途

• 他のデータ構造の構築：
  • スタック
  • キュー
  • グラフ
• 前後に移動しながら情報にアクセスする操作
  • ウェブブラウザー
  • 音楽プレイリスト

連結リスト - 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

 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

連結リスト - 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

連結リスト - 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

連結リスト - 例

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

練習しましょう！

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