Hola equipo de BlackHat esta vez traigo algo básico, que todo buen programador medianamente decente debe conocer. Es la implementación del tipo de dato abstracto (TDA) lista con una lista simplemente enlazada y además con el cálculo de el orden de cada uno de los algoritmos con la notación asintótica para el caso peor, de la que ya CHenry habló anteriormente.
Primero vamos a describir la implementación del TDA Nodo Simple, este tiene que tener un valor o una referencia a este y una referencia al nodo que lo sucede.
Clase Node
Nombre de Atributo | Descripción |
value | Referencia al valor del nodo. |
next | Referencia al siguiente nodo. |
Nombre de Método | Descripción | Orden del Algoritmo |
__init__ | Constructor de la clase. Se le pasan como parámetros opcionales la referencia a su valor y la referencia al siguiente nodo. | O(1) |
__str__ | Convierte a cadena de caracteres el valor referenciado por el nodo. | O(1) |
Ahora echemos un vistazo a la descripción de la implementación del TDA Lista.
Clase SimpleLinkedList
Nombre de Atributo | Descripción |
__count | Contador que indica la cantidad de elementos en la lista. |
__headNode | Referencia al nodo cabeza de la lista |
__lastNode | Referencia al nodo final de la lista |
__iterCursor | Referencia al nodo en el que se está iterando en ese instante en la lista |
Nombre de Método | Descripción | Orden del Algoritmo |
__init__ | Constructor de la clase. | O(1) |
__getitem__ | Indexador para conocer el valor de un elemento. Recibe como parámetro un entero el cual es la posición del elemento del que se desea conocer el valor. Devuelve una copia del valor de ese elemento | O(n) |
__setitem__ | Indexador para establecer el valor de un elemento. Recibe como parámetro un entero y una referencia a un valor. El entero es la posición donde se desea establecer el valor. | O(n) |
__delitem__ | Elimina un elemento de la lista. Recibe como parámetro la posición que se va a eliminar. | O(n) |
__add__ | Sobrecarga del operador +. Toma como parámetro otra lista simplemente enlazada y devuelve una nueva lista la cual es el resultado de la concatenación de las dos lista | O(n) |
__str__ | Se ejecuta cuando el objeto es convertido a cadena de caracteres, este método genera una cadena de caracteres con cada uno de los valores de los nodos de la lista convertidos a cadena. | O(n) |
__iter__ | Permite a la clase ser iterada por ciclos como el for. Para que la clase pueda ser iterada simultaneamete por varios ciclos a la vez este método devuelve una copia del objeto. |
O(1) |
next | Devuelve el elemento de la lista sobre el cual se está iterando y avanza al siguiente. En caso de llegar al fin de la lista este método levanta una excepción para detener las iteraciones | O(1) |
__AdvanceTo | Devuelve un nodo de la lista, el cual se corresponde con el índice que se le pasó al método | O(n) |
Join | Empata dos listas, la actual y la que se le pasa como parámetro. Creando una sola lista y los nombres de las listas ahora referencian a la misma lista. | O(1) |
Add | Agrega un nuevo elemento a la lista. | O(1) |
Clear | Limpia la lista y la deja vacía. | O(1) |
LocateFirst | Devuelva la posición de la primera ocurrencia en la lista del valor que se le pasa como parámetro. | O(n) |
Locate | Devuelve una lista con las posiciones donde ocurre el valor que se le pasa como parámetro en la lista. | O(n) |
Insert | Inserta en la lista un nuevo elemento con el valor y la posición que se le pasan como parámetros | O(n) |
Reverse | Invierte el orden de los elementos de la lista, la pone "patas arriba". | O(n) |
QSort | Ordena la lista de menor a mayor usando el algoritmo de ordenamiento QuickSort | O(n log(n)) |
Ahora pasamos a ver la implementación en Python:
Nota: La implementación se encuentra en la sección de Códigos
No hay comentarios:
Publicar un comentario