danieltm64

Olá, Philipe.
 
Apenas para recordar, uma lista simplesmente encadeada é uma lista encadeada em que cada nodo contém, além do dado a ser armazenado, um apontador para o nodo seguinte, enquanto uma lista duplamente encadeada é uma lista encadeada em que cada nodo contém, além do dado a ser armazenado, dois apontadores: um para o nodo anterior e outro para o nodo seguinte.
 
Uma multi-lista é uma lista encadeada em que cada nodo contém múltiplos apontadores. Uma lista duplamente encadeada é um caso particular de multi-lista, mas o termo ‘multi-lista’ é comumente usado para referir-se a listas encadeadas com 3 apontadores ou mais.
 
O propósito de multi-listas é ordenar um único conjunto de dados de várias maneiras eficientemente. Por exemplo, suponhamos que cada elemento da lista representa um funcionário, e cada funcionário tem nome, salário e sexo. Cada nodo da lista contém um funcionário e 3 apontadores. Assim você pode ter um único conjunto de funcionários e, de maneira muito eficiente, você pode percorrer essa lista de funcionários em diversas ordens, como: percorrer por nome em ordem alfabética, percorrer por salário em ordem crescente, e percorrer por sexo. Exemplo:
 
Começo:
* Apontador (Nome): Nodo 1
* Apontador (Salário): Nodo 2
* Apontador (Sexo Masculino): Nodo 3
* Apontador (Sexo Feminino): Nodo 2
 
Nodo 1
* Nome: Antônio
* Salário: 3000
* Sexo: Masculino
* Apontador (Nome): Nodo 3
* Apontador (Salário): NULL
* Apontador (Sexo): NULL
 
Nodo 2
* Nome: Paula
* Salário: 1000
* Sexo: Feminino
* Apontador (Nome): NULL
* Apontador (Salário): Nodo 3
* Apontador (Sexo): NULL
 
Nodo 3
* Nome: Bernardo
* Salário: 2000
* Sexo: Masculino
* Apontador (Nome): Nodo 2
* Apontador (Salário): Nodo 1
* Apontador (Sexo): Nodo 1
 
Como você pode ver, cada nodo possui 3 apontadores, e se você sempre seguir o apontador associado ao nome do funcionário, você percorrerá a lista em ordem alfabética dos nomes dos funcionários, e se você sempre seguir o apontador associado ao salário do funcionário, você percorrerá a lista em ordem crescente de salário, e assim por diante. Assim, o dado só existe uma vez e eficientemente você consegue ordenar os dados de acordo com diversos critérios.
 
Para verificar isso, note que o apontador associado ao nome no começo aponta para o nodo 1, cujo funcionário tem nome começando com A, e esse nodo aponta para o nodo 3, cujo funcionário tem nome começando com B, e esse nodo aponta para o nodo 2, cujo funcionário tem nome começando com P. Assim os funcionários estão ordenados por nome em ordem alfabética. O mesmo vale para o salário, pois o começo aponta para o nodo 2, cujo funcionário tem o menor salário, e esse nodo aponta para o nodo 3, cujo funcionário tem um salário maior, e esse nodo aponta para o nodo 1, cujo funcionário tem o maior salário. Com relação ao sexo masculino, o começo aponta para o nodo 3, cujo funcionário é homem, e esse nodo aponta para o nodo 1, cujo funcionário também é homem. Já com o sexo feminino, o começo aponta para o nodo 2, cujo funcionário é mulher.
 
Com base nesse exemplo, um elemento da multi-lista poderia ser definido da seguinte forma em C:
struct nodo { char *nome; int salario; bool sexo; struct nodo *proximoNome; struct nodo *proximoSalario; struct nodo *proximoSexo; } Ou, se você quiser permitir percorrer a lista de trás pra frente, um elemento da multi-lista poderia ser definido assim:
struct nodo { char *nome; int salario; bool sexo; struct nodo *anteriorNome; struct nodo *proximoNome; struct nodo *anteriorSalario; struct nodo *proximoSalario; struct nodo *anteriorSexo; struct nodo *proximoSexo; }