Como en el caso de las listas no ordenadas hay dos operaciones fundamentales, insertar y borrar. El borrado de un elemento es idéntico en el caso de una lista ordenada que en una lista no ordenada, en cambio la operación de inserción sí que es diferente.
El procedimiento de añadir un nuevo elemento a una lista ordenada es ligeramente más complejo que en una lista desordenada. Cuando una lista es ordenada hay que mantener el orden siempre, por ello hay que tener especial cuidado al modificar la estructura de datos.
El procedimiento para insertar un elemento consta de dos pasos:
El proceso de búsqueda se suele realizar generalmente mediante una búsqueda secuencial. De esta forma se recorrerá la lista empezando por el inicio hasta encontrar el lugar adecuado para llevar a cabo la inserción.
Vamos a verlo con un ejemplo:
Partimos de la siguiente lista
Si sobre esta lista se inserta el elemento 12, la lista sufirá los siguientes cambios:
1.- Búsqueda secuencial en la lista de la posición adecuada para insertar el elemento 12. La búsqueda se para al llegar al elemento 76, ya que es mayor que el elemento a insertar, y por lo tanto debe estar en una posición posterior al nuevo elemento. Para poder realizar posteriormente la inserción hay que recorrer la lista manteniendo dos referencias, una al nodo actual y otra al nodo anterior.
2.- Inserción del elemento 12 en la posición entre el elemento 3 y el elemento 76. Para realizar esta operación se reestructuran los punteros del nodo que contiene al elemento 3 y del nuevo nodo. El nuevo nodo pasa a contener una referencia al nodo actual (elemento 76), mientras que el nodo anterior (elemento 3), pasa a apuntar al nuevo nodo.
La operación borrar en listas ordenadas es igual que la operación borrar en listas no ordenadas, ya que la eliminación de un elemento nunca violará la condición de orden de esa lista, siempre y cuando la lista estuviese realmente ordenada antes de la eliminación. Por esta razón la explicación de esta operación se encuentra en la página sobre listas.
Como en el caso de listas no ordenadas las operaciones adicionales que pueden incorporar las listas ordenadas es muy variado, pero también como en el caso anterior las dos operaciones principales son las descritas arriba.
Como apunte se puede comentar el diferente tratamiento que se le da a la operación buscar en las listas ordenadas, ya que en estas estructuras se puede aplicar un algoritmo más rápido que la búsqueda secuencial aplicada en las listas no ordenadas. Este tratamiento es la búsqueda binaria, que consiste en dividir la lista en dos partes, comprobando en cual de ellas debería estar el elemento (si existiese). Una vez localizada la mitad en la que se encuentra el objeto buscado se realizaría la misma operación recursivamente sobre esa mitad. Este proceso se propagaría hasta que se encuentre el elemento en el caso de que efectivamente exista, o hasta que el número de elementos de la mitad resultante sea 0 en el caso de que no exista.
