Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Unidad 3/Estructuras lineales

SecuenciasEditar

Una secuencia es una estructura lineal de cero o más elementos. Al número n de elementos se le llama longitud de la secuencia. Si n = 0, se tiene una secuencia vacía. Es una estructura lineal generalizada:

  • Lineal: si n ≥ 1,   es el primer elemento y   el último,   precede a   y sucede a  . Sus elementos están ordenados por sus posiciones.
  • Generalizada: permite accesos, inserciones y borrados en cualquier posición, a diferencia de otras estructuras lineales (como pilas y colas), que sólo lo permiten en determinadas posiciones.

    Secuencias por índice: VectoresEditar

    Sea S una secuencia con n elementos. Podemos referirnos a cada elemento e de S usando un entero en el rango [0, n - 1] que denominamos índice. El índice de un elemento puede cambiar cuando se actualiza la secuencia.

    OperacionesEditar

    BuscarEn(r)Editar

    Devuelve el elemento en la posición r. Se ejecuta en un tiempo de O(1).

    ModificarEn(r, e)Editar

    Coloca el elemento e en la posición r. Se ejecuta en un tiempo de O(1).

    InsertarEn(r, o)Editar

    Requiere desplazar hacia delante (n – r) elementos. En el caso peor (r = 0) el costo en tiempo es de O(n).

    EliminarEn(r)Editar

    Requiere desplazar hacia atrás (n – r – 1) elementos. En el caso peor (r = 0) el costo en tiempo es de O(n). Para poder realizar inserciones y eliminaciones en ambos extremos con costo en tiempo de O(1), puede utilizarse un arreglo circular.

    Secuencias por posición: ListasEditar

    Una posición proporciona una forma unificada de referirse al “lugar” en el que están almacenados los elementos. Una lista es un contenedor de objetos, la cual almacena cada elemento en una posición y mantiene esas posiciones dispuestas en orden lineal. En cambio, una posición no es un contenedor, puesto que almacena un único elemento y no una colección, y sólo soporta la operación recuperar(), que devuelve el objeto almacenado en esta posición. Una posición siempre se define de manera relativa, es decir, en función de los vecinos. En una lista L, una posición p estará siempre después de alguna posición q y delante de alguna posición s (excepto cuando p es la primera o la última posición de la lista). Una posición p, la cual está asociada con algún objeto o de la lista L, no cambia, incluso aunque el orden lógico de o cambie (por ejemplo, un nodo está asociado a su contenido independientemente de su posición relativa con respecto a otros).

    OperacionesEditar

    RecorridoEditar

    Consiste en visitar cada uno de las posiciones de la lista. Tendrá, naturalmente, una complejidad de O(n).

    InserciónEditar

    Consiste en agregar un nuevo elemento a la lista.

    InsertarAlInicioEditar

    Tendrá complejidad de O(1).

    InsertarDespuésDe(Elemento e)Editar

    Deberá realizarse la búsqueda de e, por lo que tendrá complejidad de O(n). Puede implementarse también InsertarAntesDe(Elemento e).

    InsertarAlFinalEditar

    Dependiendo de la implementación, puede ejecutarse con costo en tiempo de O(1) (aquí solo hace falta añadir un puntero al final).

    BorradoEditar

    Consiste en quitar una posición de la lista.

    EliminarPrimeroEditar

    Tendrá complejidad de O(1).

    EliminarÚltimoEditar

    Dependiendo de la implementación, puede ejecutarse con costo en tiempo de O(1) (para restaurar la información adicional con complejidad constante, una posición no podrá tener solamente una referencia al siguiente, sino también al anterior).

    Eliminar(Elemento e)Editar

    Deberá realizarse la búsqueda de e, por lo que tendrá complejidad de O(n).

    EliminarAnteriorA(Elemento e)Editar

    Deberá realizarse la búsqueda de e, por lo que tendrá complejidad de O(n). Puede implementarse también EliminarPosteriorA(Elemento e).

    BúsquedaEditar

    Consiste en visitar cada una de las posiciones, hasta ubicar una con determinada característica, y devolverla.

    Listas circularesEditar

    Todos los contenedores tienen una referencia al siguiente, de manera que no hay uno primero ni uno último, y la información de estado se limita a un contenedor actual.

    PilasEditar

    En estas estructuras de datos, el acceso está limitado al elemento más recientemente insertado.

    OperacionesEditar

    Todas las operaciones naturales de una pila pueden ser ejecutadas en tiempo de O(1).

    Apilar (push)Editar

    Inserta un elemento en la cima de la pila.

    Desapilar (pop)Editar

    Elimina la posición en la cima de la pila y devuelve el objeto que contiene.

    Cima (top)Editar

    Devuelve el elemento que hay en la cima de la pila sin eliminarlo.

    ColasEditar

    En estas estructuras de datos, el acceso está limitado al elemento más antiguamente insertado.

    OperacionesEditar

    Todas las operaciones naturales de una cola pueden ser ejecutadas en tiempo de O(1).

    Encolar (enqueue)Editar

    Inserta un elemento al final de la cola.

    Desencolar (dequeue)Editar

    Elimina la posición en el frente de la cola y devuelve el objeto que contiene.

    Ver (peek)Editar

    Devuelve el elemento que hay en el frente de la cola sin eliminarlo.

    Colas doblesEditar

    Es una estructura similar a una cola, excepto que está permitido el acceso por ambos extremos. Así como en las listas, para restaurar las referencias con complejidad constante luego de una eliminación al final, una posición no podrá tener solamente una referencia al siguiente, sino también al anterior.

    Nodos cabeceraEditar

    Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista estará diferenciado de los demás. Una lista con nodo cabecera satisface el requerimiento: cada nodo que contiene un elemento tiene un nodo anterior. Esto simplifica las operaciones de eliminación e inserción, pues no hay que tratar los casos especiales para listas vacías. Se simplifica el código y aumenta la velocidad a cambio de un despreciable aumento de espacio.

    IteradoresEditar

    Un iterador es un patrón de diseño de software que abstrae el proceso de recorrer una colección de elementos. Un iterador consta de una secuencia S, una posición actual en S y una forma de avanzar a la siguiente posición, convirtiéndola en su posición actual.

    OperacionesEditar

    TieneSiguienteEditar

    Determina si hay un elemento siguiente.

    SiguienteEditar

    Devuelve el elemento siguiente.

    EliminarActualEditar

    Elimina el elemento actual de la secuencia.