Complexidade do tempo de lista vinculada
Lista individual
O diagrama a seguir mostra uma lista individual de três elementos:
Cada elemento tem duas partes. A primeira parte tem os dados. A segunda parte tem um ponteiro que aponta para o próximo elemento. O segundo e o terceiro elementos são semelhantes ao primeiro. O último elemento tem um ponteiro nulo. Com a lista individual, o Traversing só pode ir em uma direção: a direção da frente.
Os elementos de uma lista vinculada não são abordados por referências (subscritos entre colchetes), tudo sendo igual. Eles são acessados por iteradores (ponteiros). No caso da lista de vinculação individual, o iterador deve começar do início e passar do elemento a elemento, a fim de alcançar o elemento pretendido.
Lista duplamente vinculada
O diagrama a seguir mostra uma lista duplamente vinculada de três elementos:
Aqui, cada elemento tem três partes. A primeira parte tem um ponteiro que aponta para o elemento anterior. A segunda parte tem os dados. A terceira parte tem um ponteiro que aponta para o próximo elemento. A primeira parte do primeiro elemento tem um ponteiro que aponta para nulo. A terceira parte do último elemento tem um ponteiro que aponta para nulo. Com a lista duplamente vinculada, a travessia pode seguir em qualquer direção: a direção para a frente ou a direção inversa.
Os elementos de uma lista vinculada não são abordados por referências (subscritos entre colchetes). Eles são acessados por iteradores (ponteiros). No caso de uma lista duplamente vinculada, o iterador pode se mover em qualquer direção, mas precisa começar em cada extremidade. O movimento não pode começar oficialmente de dentro da lista.
O objetivo deste artigo é determinar o que é conhecido como complexidade do tempo para a lista vinculada.
Complexidade do tempo em geral
A complexidade do tempo é o tempo de execução relativo de algum código. A complexidade do tempo também pode ser vista como o número de operações principais do código.
Tempo constante
Diz -se que uma operação principal, como inserção ou exclusão, tem uma complexidade de tempo de tempo constante, porque a ação pode ser vista como ocorrendo uma vez. Está escrito como:
O (1)
onde 1 significa tempo ou ação constante que ocorre uma vez. Isso usa a notação Big-O que começa com o em maiúsculas seguidas de parênteses. Dentro dos parênteses está o número de operações principais para a tarefa.
Tempo linear
Lendo uma matriz desde o início- um elemento depois do outro procurando um elemento específico- é referido como uma pesquisa linear.
O elemento procurado pode ser encontrado em algum lugar no meio e a busca pararia. Esta ainda é uma pesquisa linear. A complexidade do tempo para a pesquisa linear é escrita como:
Sobre)
onde n é o número máximo possível de operações.
Lista vinculada Operações principais
Procurando
Para uma lista vinculada individual, para passar de um elemento para o outro, o código deve usar o ponteiro do elemento atual, que aponta para o próximo elemento. Este não é o caso das matrizes. Para uma lista duplamente vinculada, para passar de um elemento para o outro, o código deve usar o ponteiro do elemento atual que aponta para o próximo elemento. Este não é o caso das matrizes. Para uma lista duplamente vinculada, para passar de um elemento para o anterior, o código deve usar o ponteiro do elemento atual que aponta para o elemento anterior. Este não é o caso das matrizes.
Eliminação
Quando um elemento atual é excluído, o ponteiro do elemento anterior que estava apontando para ele, deve ser feito para apontar para o próximo elemento. Então, o ponteiro do próximo elemento que estava apontando para ele deve ser feito para apontar para o elemento anterior.
Inserção
Quando o elemento atual é inserido, o ponteiro do elemento anterior que estava apontando para o próximo elemento deve ser feito para apontar para o elemento atual. O ponteiro do próximo elemento que estava apontando para o elemento anterior deve ser feito para apontar para o elemento atual.
O ponteiro frontal do elemento atual deve ser feito para apontar para o novo próximo elemento. O ponteiro traseiro do elemento atual deve ser feito para apontar para o novo elemento anterior.
Complexidade do tempo para lista vinculada
Ao falar sobre a complexidade do tempo para uma lista vinculada, é a complexidade do tempo para pesquisa, inserção e exclusão que são falados sobre. Não é a complexidade do tempo para construir a lista vinculada que é discutida. A complexidade do tempo para a construção de uma lista vinculada é um problema diferente.
Procurando
Para que uma lista de vinculação singular seja pesquisada por um elemento específico (dados), o código de pesquisa deve digitalizar o elemento da lista por elemento- desde o início. Para que uma lista duplamente vinculada seja pesquisada por um elemento específico, o código de pesquisa deve digitalizar o elemento da lista por elemento- desde o início. Ou escanear a lista, elemento por elemento, do final. A complexidade do tempo de pesquisa de uma lista vinculada (isoladamente ou duplamente) é:
Sobre)
onde n é o número de elementos na lista. Não importa se o elemento foi encontrado, em algum lugar dentro da lista.
Inserção
A inserção é considerada uma operação principal. Para inserir um elemento em uma lista vinculada, a pesquisa deve ocorrer, para chegar à posição, para inserção. A complexidade do tempo para pesquisa é O (n). A complexidade do tempo para a ação da inserção é O (1). Portanto, a complexidade do tempo para inserção em uma lista vinculada é O (n + 1). Por simplicidade, a complexidade do tempo para inserção de um elemento, em uma lista vinculada, é escrita como:
Sobre)
Eliminação
A exclusão é considerada como uma operação principal. Para excluir um elemento em uma lista vinculada, a pesquisa deve ocorrer, para chegar ao cargo de exclusão. A complexidade do tempo para pesquisa é O (n). A complexidade do tempo para a ação da exclusão é O (1). Portanto, a complexidade do tempo para exclusão em uma lista vinculada é O (n + 1). Por simplicidade, a complexidade do tempo para exclusão de um elemento, fora de uma lista vinculada, é escrita como:
Sobre)
Construindo uma lista vinculada em C
Para construir uma lista duplamente vinculada em C, use o objeto STRUT. O primeiro membro de dados deve ter um ponteiro que aponte para a estrutura anterior. O terceiro membro de dados deve ter um ponteiro que aponte para a próxima estrutura. O membro do dados do meio deve ter os dados. O primeiro membro de dados da primeira estrutura deve apontar para nulo. O terceiro membro de dados da última estrutura também deve apontar para nulo.
No caso de lista de vinculação individual, omite o primeiro membro de dados.
Conclusão
A complexidade do tempo para pesquisar uma lista vinculada é:
Sobre)
Por simplicidade, a complexidade do tempo para inserir um elemento em uma lista vinculada é:
Sobre)
e não O (1).
Por simplicidade, a complexidade do tempo para exclusão de um elemento, fora de uma lista vinculada, é:
Sobre)
e não O (1).