Grafos E Listas

Lista ligada

Origem: Wikipédia, a enciclopédia livre.

Question book.svg

Este artigo não cita fontes fiáveis e independentes. (desde março de 2011). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.

—Encontre fontes: Google (notícias, livros e acadêmico)

Uma lista ligada ou lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por células que apontam para o próximo elemento da lista. Para "ter" uma lista ligada/encadeada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula. O esquema a seguir representa uma lista ligada/encadeada com 5 elementos:

Célula 1 ----> Célula 2 ---> Célula 3 ---> Célula 4 ---> Célula 5 ---> (Nulo)

Para inserir dados ou remover dados é necessário ter um ponteiro que aponte para o 1º elemento e outro que aponte para o fim, porque se queremos inserir ou apagar dados que estão nessas posições, a operação é rapidamente executada. Caso seja necessário editar um nó que esteja no meio da lista haverá uma busca pela posição desejada.

Diagrama conceitual de uma lista ligada.

Índice [esconder]

1 Vantagens

2 Desvantagens

3 Níveis de complexidade

4 Exemplo em C

4.1 Estrutura

4.2 Manutenção

4.2.1 Cria Lista

4.2.2 No início

4.2.3 No fim

4.3 Remoção

4.3.1 No início

4.3.2 No fim

5 Exemplo em C++

6 Exemplo em Java

7 Ver também

Vantagens[editar | editar código-fonte]

A inserção ou remoção de um elemento na lista não implica a mudança de lugar de outros elementos;

Não é necessário definir, no momento da criação da lista, o número máximo de elementos que esta poderá ter. Ou seja, é possível alocar memória "dinamicamente", apenas para o número de nós necessários.

Desvantagens[editar | editar código-fonte]

A manipulação torna-se mais "perigosa" uma vez que, se o encadeamento (ligação) entre elementos da lista for mal feito, toda a lista pode ser perdida;

Para aceder ao elemento na posição n da lista, deve-se percorrer os n - 1 anteriores.

Níveis de complexidade[editar | editar código-fonte]

Numa lista com n itens, temos as seguintes complexidades de tempo no pior caso:

Inserção

Cabeça O(1)

Cauda O(n)

Meio O(n)

Eliminação

Cabeça O(1)

Cauda O(n)

Meio O(n)

Exemplo em C[editar | editar código-fonte]

Exemplo de código feito em linguagem de programação C:

Estrutura[editar | editar código-fonte]

typedef struct No_st{

int numero;

struct No *prox;

}No;

O tipo de dados seria definido apenas pela chamada ao método struct, mas a inclusão do typedef simplifica a sua utilização. A partir deste momento, a variável do tipo No está disponível, sendo o seu acesso feito como a uma qualquer estrutura de dados.

Exemplo de inicialização e preenchimento no main:

int main(void){

No exemplo; /*A variável exemplo é do tipo no*/

No *pexemplo; /*A variável pexemplo do tipo apontador para no*/

exemplo.numero = 1;

pexemplo = &exemplo;

printf("%d\n", exemplo.numero);

printf("%d\n", pexemplo->numero);

return (1);

}

Neste exemplo, ambas as chamadas à função printf() iriam imprimir o número 1.

Manutenção[editar | editar código-fonte]

Cria Lista[editar | editar código-fonte]

Para começar uma lista não basta começar a inserir novas células, é preciso uma base, ou raiz, que será sempre a mesma para uma lista. Esta raiz pode ser simplesmente um apontador para uma lista ou um apontador para uma primeira célula vazia. Normalmente, para listas, é usada a célula vazia, já para as pilhas e filas é usado o apontador para os respectivos. A função seguinte é usada no main após ser declarada a variável raiz que será do tipo apontador para lista( que nestes exemplos tem o nome No).Esta cria uma célula vazia e mete a raiz a apontar para esta:

No * cria_lista(){ // Função do tipo apontador para lista, i.e., o tipo de função tem de ser igual ao tipo que retorna

No * novo,*aux;

novo = (No *) malloc( sizeof( No )); /*Aloca memória do tamanho de uma célula*/

if(novo == NULL) exit(0); /* Se não alocar memória significa que não há memoria disponível, logo deve sair*/

novo->prox = NULL;