¡Bienvenido!

Estructuras de datos y algoritmos en Python

Miriam Antona

Software Engineer

La importancia de algoritmos y estructuras de datos

• Las estructuras de datos y los algoritmos nos permiten
  • resolver problemas cotidianos
  • con código eficiente
• El curso podría impartirse en cualquier lenguaje

Algoritmos y estructuras de datos

• Algoritmo: conjunto de instrucciones que resuelve un problema

  1. Diseño

     

  2. Código

     

• Estructuras de datos: almacenan y manipulan datos al ejecutar un algoritmo
  • Avanzadas: listas enlazadas, pilas, colas...

Listas enlazadas

• Secuencia de datos conectados por enlaces

Listas enlazadas: estructura

Listas enlazadas: estructura

Listas enlazadas: estructura

Listas enlazadas: estructura

Listas enlazadas: estructura

Listas enlazadas: estructura

Listas enlazadas: estructura

Listas enlazadas: estructura

• Los datos no necesitan estar en bloques contiguos de memoria
• Pueden ubicarse en cualquier dirección de memoria disponible

Listas simplemente enlazadas

• Un enlace: lista simplemente enlazada

Listas doblemente enlazadas

• Dos enlaces en ambos sentidos: lista doblemente enlazada

Listas enlazadas: usos reales

• Implementar otras estructuras:
  • pilas
  • colas
  • grafos
• Acceder moviéndote hacia atrás y adelante
  • navegador web
  • lista de reproducción

Listas enlazadas: clase Node

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

Listas enlazadas: clase LinkedList

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

Listas enlazadas: métodos

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

Listas enlazadas: insert_at_beginning

Listas enlazadas: insert_at_beginning

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

    if self.head:

Listas enlazadas: insert_at_beginning

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

Listas enlazadas: 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

Listas enlazadas: 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

Listas enlazadas: 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

Listas enlazadas: search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Listas enlazadas: 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

Listas enlazadas: 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

Listas enlazadas: ejemplo

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Listas enlazadas: ejemplo

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

Listas enlazadas: ejemplo

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

Listas enlazadas: ejemplo

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python