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

Secuencias

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, $a_{1}$ es el primer elemento y $a_{n}$ el último, $a_{i}$ precede a $a_{i+1}$ y sucede a $a_{i-1}$. 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

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

BuscarEn(r)

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

ModificarEn(r, e)

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

InsertarEn(r, o)

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

EliminarEn(r)

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

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

Recorrido

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

Inserción

Consiste en agregar un nuevo elemento a la lista.

InsertarAlInicio

Tendrá complejidad de O(1).

InsertarDespuésDe(Elemento e)

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

InsertarAlFinal

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

Consiste en quitar una posición de la lista.

EliminarPrimero

Tendrá complejidad de O(1).

EliminarÚltimo

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)

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

EliminarAnteriorA(Elemento e)

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

Búsqueda

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

Listas circulares

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

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

Operaciones

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

Apilar (push)

Inserta un elemento en la cima de la pila.

Desapilar (pop)

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

Cima (top)

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

Colas

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

Operaciones

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

Encolar (enqueue)

Inserta un elemento al final de la cola.

Desencolar (dequeue)

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

Ver (peek)

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

Colas dobles

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

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

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

TieneSiguiente

Determina si hay un elemento siguiente.

Siguiente

Devuelve el elemento siguiente.

EliminarActual

Elimina el elemento actual de la secuencia.