COS-121

Aula 11

• Simplesmente encadeada
  Numa lista linear simplesmente encadeada cada elemento possui, além do espaço para armazenamento da informação, um espaço para armazenar uma referência da localização na memória onde o próximo elemento da lista (ou o anterior) se encontra.
  

  A representação simbólica para a lista linear simplesmente encadeada é apresentada a seguir:

  

• Duplamente encadeada
  Numa lista linear duplamente encadeada cada elemento possui, além do espaço para armazenamento da informação, um espaço para armazenar a referencia da localização de memória onde se encontra o próximo elemento da lista e outro espaço para armazenar a referencia da localização de memória onde se encontra o elemento anterior.

  A representação simbólica para a lista linear duplamente encadeada é apresentada a seguir:

  

  Na figura acima note que, na lista duplamente encadeada, o campo próximo de um nó faz referência ao próximo nó da lista, e o campo anterior faz referência ao nó anterior ao nó em questão.

Uma primeira vantagem da utilização de lista duplamente encadeada sobre a lista simplesmente encadeada é a maior facilidade para navegação, que na lista duplamente encadeada pode ser feita nos dois sentidos, ou seja, do início para o fim e do fim para o início. Isso facilita a realização de operações tais como inclusão e remoção de nós, pois diminui a quantidade de variáveis auxiliares necessárias.

A principal vantagem da utilização de listas encadeadas sobre listas sequenciais é o ganho em desempenho em termos de velocidade nas inclusões e remoções de elementos. Em uma lista contígua é necessário mover todos os elementos da lista para uma nova lista para realizar essas operações. Com estruturas encadeadas, como não existe a obrigatoriedade dos elementos estarem em posições contíguas da memória, basta realizar alterações nas referências dos nós, sendo um novo nó rapidamente inserido ou removido. Esta estrutura é mais adequada para listas com centenas ou milhares de nós, onde uma inserção ou remoção em uma lista contígua representará uma perda notável no desempenho do processamento.

Rotinas de Manipulação Lista Simplesmente Encadeada

As rotinas inserção e remoção de elementos numa lista são realizadas manipulando-se a referência ao próximo nó da lista. Observe a ilustração a seguir:

Inserção:

Remoção:

Veja o algoritmo a seguir:

#include 

struct Nodo {

	int info;
	struct Nodo *prox;

};

struct ListaSimplesEnc {

	struct Nodo *prim;

};

void criarLista (struct ListaSimplesEnc *pList) {

	pList -> prim = NULL;

}

void mostrarLista (struct ListaSimplesEnc *pList){

	struct Nodo *p;

	for (p = pList -> prim; p != NULL; p = p->prox) {

		printf("%d\t", p->info);

	}

	printf("\n");

}

void inserirIni (struct ListaSimplesEnc *pList, int v){
	struct Nodo *novo;
	novo = (struct Nodo*) malloc (sizeof (struct Nodo));
	novo -> info = v;
	novo -> prox = pList -> prim;
	pList -> prim = novo;
}

void removerIni (struct ListaSimplesEnc *pList){

	struct Nodo *pAux = pList -> prim;
	pList -> prim = pList -> prim -> prox;
	free(pAux);

}

void inserirOrd (struct ListaSimplesEnc *pList, int v){
	struct Nodo *novo;
	novo = (struct Nodo*) malloc (sizeof (struct Nodo));
	novo -> info = v;
	
	struct Nodo *pAtu, *pAnt;

	pAnt = NULL;
	pAtu = pList -> prim;

	while ( pAtu != NULL && pAtu->info < v){

		pAnt = pAtu;
		pAtu = pAtu -> prox;

	}

	novo -> prox = pAtu -> prox;
	pAnt -> prox = novo;
}

int estaVazia(struct ListaSimplesEnc *pList) {

	return (pList->prim == NULL);

}

void main () {
	struct ListaSimplesEnc minhaLista;
	int valor, op;

	criarLista(&minhaLista);

	while( 1 ){

		printf( "1 - Inserir elemento no inicio\n" );
		printf( "2 - Inserir elemento em ordem (so se a lista estiver ordenada)\n" );
		printf( "3 - Remover elemento no inicio\n" );
		printf( "4 - Remover elemento\n" );
		printf( "5 - Mostrar lista\n" );
		printf( "6 - Sair\n" );
		printf( "Opcao? " );
		scanf( "%d", &op );

		switch( op ){

			case 1: // inserir elemento no inicio
		
				printf( "Valor? " );
				scanf( "%d", &valor );
				inserirIni(&minhaLista, valor);
				break;
			case 2: // inserir elemento ordenado
				printf( "Valor? " );
				scanf( "%d", &valor );
				inserirOrd(&minhaLista, valor);
				break;
			case 3: // remover o primeiro
				break;
			case 4: // remover determinado elemento
				break;
			case 5: //  mostrar lista
				if (estaVazia(&minhaLista)) {
					printf("Lista vazia");
				}
				else {
					mostrarLista(&minhaLista);
				}
				break;
			case 6: // abandonar o programa
				exit(0);
		}

	}
}

Rotinas de Manipulação Lista Duplamente Encadeada

As rotinas inserção e remoção de elementos numa lista são realizadas manipulando-se a referência ao próximo nó da lista. Observe a ilustração a seguir:

Inserção:

Remoção:

Veja o algoritmo a seguir:

#include 

// elemento da lista - nó ou nodo
struct Nodo {

	int info;
	struct Nodo *ant;
	struct Nodo *prox;

}no;


void main () {

	struct Nodo *inicio = NULL, *tmp, *p;
	int v;

	while( 1 ){

		printf( "\nValor? " );
		scanf( "%d", &v );

		if ( v == 0 ) break;

		// cria um novo nodo para ser inserido na lista
		tmp = (struct Nodo* ) malloc ( sizeof( struct Nodo ) );
		tmp -> info = v; 
		tmp -> prox = NULL;

		if (inicio == NULL) { // lista vazia

			inicio = tmp;
			tmp->ant = tmp->prox = NULL;

		}
		else {

			// p irá percorrer a lista			
			p = inicio;
			
			while ( p->prox != NULL && p->info != v) {

				p = p->prox;

			}

			if ( p->info != v ){
	
				p->prox = tmp;
				tmp->ant = p;

			}
		}

	}

	
	// mostrando a lista
	p = inicio;
	while ( p != NULL ) {

		printf( "%d\t", p->info);
		p = p->prox;

	}
	printf( "\n");

}