TDA: Tipos de datos abstractos

• Fundamento matemático

Tipos de estructuras de datos

• Listas enlazadas

    * Soporta operaciones como add, addFirst, addLast, remove, removeFirst.
  

• Árboles

• Grafos

• Colas/pilas

• Set/Conjuntos

• Maps/Diccionarios

• Array

    * Colección finita y bien definida de elementos de x tipo.
    * Cada elemento esta contiguo uno al otro en memoria 
    * int[] = new int[x]
  
    * Pros: Rápida lectura y escritura
  
    * Contras: -Inserción/Eliminación si no hay especies 
               -No puede crecer/decrecer en demanda
  

• Matrices

    * Es un array multidimensional
    * Tiene filas y columnas
  

Listas enlazadas

    * Estructura de datos dinámica
    * Crece o decrece por demanda
    * No está contigua en memoria 
    * Lista secuencial de los elementos 
    * Cada elemento es un nodo 
    * Un nodo es un objeto compuesto por dos elementos:

             * EL valor que guarda un dato
             * Referencia al siguiente elemento de la lista
             * La lista tiene una referencia al primer elemento 
             * La referencia al primer elemento debe protegerse 
             * El último nodo apunta a null

class Nodo { 
    private int dato;
    private Nodo siguiente;

    public Nodo(int dato){
         this.dato = data;
         this.siguiente = null;
    }


public class list {
     private nodo first; 

     public list(){
         this.first = null; 
     }

    public void addLast(int e){
         if(this.first==nulll){
               this.first = new Nodo(e);
         }else{
           Nodo current = this.first;
           while(current.next != null){
                current = current.next;
          }
         current = current.next;
    }
     
}

Listas circulares

• Es una lista en la que cada nodo tiene un sucesor y un predecesor.

     * El sucesor del último es el primero.
     * El predecesor del primero es el último.
  

• Iniciando en cualquier nodo, se puede recorrer la lista completa.

• El "first" apunta al último elemento.

• Son útiles cuando se necesita acceder rápidamente a el inicio/final de la lista.

• El recorrido se detiene cuando el current es igual al first.

Pilas

• Conjunto de elementos colocados unos sobre el otro.

• únuicamente se puede acceder el último elemento insertado.

• Siempre se inserta al final (el final se llama tope)

• Naturaleza LIF (Last input, fisrt input)

• Tiene 3 operaciones:

        * Push: Inserta un elemento en el tope.
        * Pop: Elimina el elemento en el tope.
        * Peek: Ver el elemento en el tope.
  

• Se puede implementar con las listas y los Arrays.

Colas

• Estructura lineal que sigue el FIFO ( first in, first out)

• Se extrae el datos menos recientemente agregado.

• Las operaciones son las siguientes:

     * Enqueue.
     * Dequeue.
     * Front: Retorna el primer elemento de la  cola.
     * Rear: Retorna el último elemento de la cola