Estructuras de datos

Listas enlazadas

Cada elemento de una lista enlazada puede estar en direcciones de memoria aleatorias. Cada elemento de la lista guarda la dirección de memoria del siguiente elemento de la lista. Es como la blockchain.

Si hay espacio disponible en la memoria siempre habrá un hueco para nuevos elementos de una lista enlazada.

Arrays

Con los arrays los elementos se van insertando contiguamente en la memoria.

El problema de esta estructura de datos viene cuando hay que insertar un nuevo elemento en la memoria y el espacio contiguo que le hubiese tocado a ese nuevo elemento ya está ocupado por otro dato/app/cosa.

Ahí es cuando toca recolocar todos los espacios en la memoria para hacer que los nodos del array se localicen secuencialmente.

Operaciones

Acceso a datos

Cuando queremos acceder a un dato aleatorio dentro de un array lo tenemos fácil ya que esta estructura de datos proporciona acceso aleatorio mediante su índice. Es decir, si todos los elementos del array se colocan de forma secuencial en la memoria y sabemos en qué dirección empieza ese array, el acceder a un nodo aleatorio es sencillo haciendo un cálculo del índice.

Sin embargo, con las listas enlazadas esto lo tenemos más difícil. La colocación de los elementos de una lista enlazada en la memoria es de forma aleatoria y lo único con lo que contamos es con punteros a direcciones de memoria por lo que si queremos ir al elemento N de la lista enlazada tendremos que posicionarnos al principio de la estructura de datos e ir recorriendo estos punteros uno a uno hasta que lleguemos al elemento que nos interesa.

Por eso un array es una estructura de datos mejor que una lista enlazada cuando queremos leer sus datos, pero en términos de optimización una lista enlazada es mejor cuando no nos interesa tanto la lectura así como la inserción.

Insertando datos en la mitad de la lista

Al igual que con el acceso a datos, la inserción de un elemento en la mitad de la lista dependerá mucho del tipo de estructura de datos escogida.

Si queremos insertar un nuevo nodo en la mitad de una lista enlazada, a términos de coste computacional es bajo porque tan solo tendremos que apuntar el puntero de la dirección de memoria del elemento N-1 a la nueva dirección del elemento insertado y ya está.

Sin embargo con los arrays es más pesado ya que podemos acceder de una forma rápida al nuevo índice que queremos insertar pero después tendremos que re colocar todos los nodos del resto del array para hacer que todos los elementos estén de forma secuencial.

Si no queda espacio libre (contiguo) en la memoria como para poder hacer esta operación entonces habrá que buscar y re colocar todo el array en un nuevo espacio de memoria disponible en el que quepan todos los elementos secuencialmente.

Borrado de nodos

Para borrar nodos de una de estas estructuras de datos, una lista enlazada es mejor porque al igual que pasa con las inserciones solo hay que referenciar un puntero de dirección de memoria y ya está.

Con los arrays hay que re colocar todos los elementos cuando se borra un nodo.

Notación Big O

Selection Sort

Este es un algoritmo de ordenación que divide la lista en dos partes: una parte ordenada y otra desordenada. Iterativamente busca el elemento más pequeño de la parte desordenada y lo mueve a la parte ordenada.

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

print(selectionSort([5, 3, 6, 2, 10]))
# Output: [2, 3, 5, 6, 10]

El algoritmo a medida que moviendo elementos al nuevo array, va recorriendo cada vez menos elementos a ordenar por lo que su tiempo de ejecución acaba reduciéndose a la mitad.

Selection sort = O(n × 1/2 × n)

Sin embargo, la complejidad temporal de Selection Sort es cuadrática O(n2) en el peor y promedio de los casos, lo que lo hace menos eficiente para listas grandes en comparación con otros algoritmos de ordenamiento como QuickSort o MergeSort. Sin embargo, es fácil de entender y de implementar.

https://www.youtube.com/embed/92BfuxHn2XE?si=65BVOJ3zMHG4a7oA

Recap

• Los arrays colocan sus elementos secuencialmente.
• Los arrays permiten lecturas rápidas.
• Los arrays recolocan la memoria en operaciones de escritura/borrado
• Las listas enlazadas colocan sus elementos de forma aleatoria.
• Las listas enlazadas permiten inserciones y borrados rápidos.
• Las listas enlazadas vuelven a referenciar un puntero.