Lista Ordenada.

Continuando com minha promessa, vamos falar sobre listas ordenadas, mais uma vez adotando o pascal,

bom já definimos o que é uma lista simplesmente encadeada, porém um array possui um índice ou seja uma posição, então com o intuído de tornar uma lista familiar a estrutura de um array, o registro passa a adotar um campo chamado índice ou posição ou chave onde esse vai determinar a posição do registro tornado mais intuitiva a busca ou posição de uma informação dentro de uma estrutura de dados.

Lista Ordenada

Definição: É uma lista que mantém os seus elementos sempre ordenados por algum critério.
Deve ser usada quando é necessário acessar os elementos da lista de forma ordenada. Quando a ordem não for importante, deve-se considerar o uso de outro tipo de lista pois as operações de inserção e remoção são mais caras (exigem mais processamento) nas listas ordenadas.
A forma mais comum de se implementar uma lista ordenada é usando uma lista encadeada, onde o primeiro nó é menor que o segundo e assim por diante. Graficamente teríamos:

Para
Para ver uma implementação de uma lista Ordenada, abra a unit LstOrd e para um programa que demonstra como usá-la, veja DLstOrd.
O procedimento inicializar faz com que a cabeça da lista aponte para nil, indicando que não há elementos na lista.
O procedimento apagar e as funções vazia e tamanho são iguais à da lista encadeada, recebendo apenas um parâmetro com tipo diferente.
A função inserir coloca o item passado na posição correta da lista, ou seja, mantendo a ordem da mesma. A lista não deve conter uma chave igual à do item passado. Se a chave do item passado for menor do que a do primeiro da lista, será inserido no início e tornar-se-á a cabeça da lista (situação 1). Caso contrário, será inserido no meio (situação 3) ou no final (situação 2) da lista, dependendo do valor de sua chave e dos elementos contidos na lista (situação 2).
Situação 1: Inserindo um valor no início da lista:

Situação 2: Inserindo um valor no final da lista:

Situação 3: Inserindo um valor no meio da lista:

A função remover encontra um item na lista com a chave passada, libera a memória alocada pelo item e ajusta apontadores. No caso da remoção, encontramos 2 situações: remoção do elemento da cabeça ou que não está na cabeça.
Situação 1: Removendo um item da cabeça da lista: