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

De Wikilibros, la colección de libros de texto de contenido libre.

Secuencias[editar]

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: Vectores[editar]

    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.

    Operaciones[editar]

    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: Listas[editar]

    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).

    Operaciones[editar]

    Recorrido[editar]

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

    Inserción[editar]

    Consiste en agregar un nuevo elemento a la lista.

    InsertarAlInicio[editar]

    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).

    InsertarAlFinal[editar]

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

    Borrado[editar]

    Consiste en quitar una posición de la lista.

    EliminarPrimero[editar]

    Tendrá complejidad de O(1).

    EliminarÚltimo[editar]

    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úsqueda[editar]

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

    Listas circulares[editar]

    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.

    Pilas[editar]

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

    Operaciones[editar]

    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.

    Colas[editar]

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

    Operaciones[editar]

    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 dobles[editar]

    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 cabecera[editar]

    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.

    Iteradores[editar]

    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.

    Operaciones[editar]

    TieneSiguiente[editar]

    Determina si hay un elemento siguiente.

    Siguiente[editar]

    Devuelve el elemento siguiente.

    EliminarActual[editar]

    Elimina el elemento actual de la secuencia.