Estructura de Datos.md

Estructura de Datos

Tipo de Dato Abstracto (ADT)

• Es como se va a organizar la informacion
• no son los requerimientos
• sino una imagen mas abstracta de como debería funcionar
• Ejemplo: Una lista, un arbol
• No hablo de arreglos, nodos, objetos...

Estructura de Dato (DS)

• Como implementar un ADT
• Por ejemplo, con un arreglo o una lista de nodos conectados
• Siempre puede haber mas de un DS para implentar un ADT

Ejemplo ADT

Cola (Queue)

• FIFO (First in First Out)
• Lo primero que entra es lo primero que sale
• enqueue(push) y dequeue (shift)
• Representacion en ES
  • Arreglo
  • Linked List
• Big o
  • enqueue: O(1) o O(n)
  • dequeue: O(1)
  • busqueda: O(n)

Pila (Stack)

• LIFO (Last in First Out)
• El ultimo que entra es el primero que sale
• metodos: push y pop
• Represtacion en DS:
  • Arreglo
  • Linked List
• Big o
  • enqueue: O(1)
  • dequeue: O(1)
  • busqueda: O(n)

Arbol (Tree)

• Puede ser ADT como DS (Como se contruye, pero también como se usa)
• Representar un arbol a traves de un arreglo
  • [5, 3, 7, undefined, 4, 6, 8]
• Operaciones:
  • Search (busqueda) O(log n)
  • insert O(log n)
    • Si tengo que balancear el arbol Big O puede ser mayor
  • remove O(log n)
  • travesal O(n)
    • depth first (profundidad primero)
      • in order izquierda-raiz-derecha
        • menor a mayor
      • pre order raiz-izquierda-derecha
        • Rearmar el arbol
      • post order izquierda derecha raiz
    • breadth first (por niveles)

Map/Dictionary/Object

• Key/value pair
• Operaciones son O(1)
  • insert
  • modificar
  • acceder
• Representacion: Hash Table
• Javascript: new Map()

Set

• Tipo de lista
• Donde todos los valores son únicos
• new Set()
• agregar y acceder O(n)
• A menos que implemente un hash table O(1)

Graph

• Conjunto de nodos conectados
• Nodos son llamados vertices
• Las conexiones son aristas
• Directos o Indirectos
  • Directos por default van hacia una dirección (pero pueden ser bidireccionales)
  • Indirectos SIEMPRE son bidireccionales
• Redes Sociales:
  • Facebook: Amigos (Indirecto)
  • Twitter & Instagram: Followers (directo)
  • Linkedn: Grados de separacion entre personas

Ejemplo DS

Arreglo

• Son de tamaño fijo
• Solo un tipo de dato Array de sttrings, o de Numeros o de Booleanos no mixtos
• Distinto al arreglo de Javascript (ADT)

Linked List

• Nodos que apuntan para otros nodos
• simples o dobles
• Simples tienen la propiedad next
• Opcionalmente pueden tener la propiedad previous (Dobles)
• Siempre trackean el head (opcionalmente el tail)

Hash Table

• Tipicamente en un arreglo de buckets
• Cada bucket tiene una linked list (por que se podia repetir el indice y creaba colisiones)
• Pasa un key por una funcion hasheadora, el resultado da un indice, y guardo el valor en ese indice
• Big O: Normalmente son O(1) pero por la colisiones en el peor de los casos es O(n)