Por que inserir no meio de uma lista encadeada O (1)?

De acordo com o artigo da Wikipedia sobre listas vinculadas , inserir no meio de uma lista vinculada é considerado O (1). Eu acho que seria O (n). Você não precisaria localizar o nó que poderia estar próximo ao final da lista?

Essa análise não leva em consideração a descoberta da operação do nó (embora seja necessária) e apenas a própria inserção?

EDITAR :

As listas vinculadas têm várias vantagens sobre as matrizes. A inserção de um elemento em um ponto específico de uma lista é uma operação de tempo constante, enquanto a inserção em uma matriz pode exigir a movimentação de metade dos elementos ou mais.

A declaração acima é um pouco enganosa para mim. Corrija-me se estiver errado, mas acho que a conclusão deveria ser:

Matrizes:

• Encontrando o ponto de inserção / exclusão O (1)
• Realizando a inserção / exclusão O (n)

Listas vinculadas:

• Encontrando o ponto de inserção / exclusão O (n)
• Realizando a inserção / exclusão O (1)

Eu acho que a única vez que você não teria que encontrar a posição é se você mantivesse algum tipo de indicador para ela (como com a cabeça e a cauda em alguns casos). Portanto, não podemos dizer claramente que as listas vinculadas sempre superam os arrays para opções de inserção / exclusão.

Você está correto, o artigo considera "Indexação" como uma operação separada. Portanto, a própria inserção é O (1), mas chegar a esse nó do meio é O (n).

A própria inserção é O (1). A localização do nó é O (n).

Não, quando você decide que deseja inserir, presume-se que você já esteja no meio da iteração pela lista.

Operações em Listas Vinculadas são freqüentemente feitas de tal maneira que não são realmente tratadas como uma "lista" genérica, mas como uma coleção de nós - pense no próprio nó como o iterador para seu loop principal. Portanto, conforme você folheia a lista, percebe como parte de sua lógica de negócios que um novo nó precisa ser adicionado (ou um antigo excluído) e você o faz. Você pode adicionar 50 nós em uma única iteração e cada um desses nós é apenas O (1) tempo para desvincular dois nós adjacentes e inserir seu novo.

Edit: Cara, você digita um segundo parágrafo e, de repente, em vez de ser o primeiro a responder, você é o quinto dizendo a mesma coisa que os primeiros 4!

Para fins de comparação com um array, que é o que o gráfico mostra, é O (1) porque você não precisa mover todos os itens após o novo nó.

Então, sim, eles estão assumindo que você já tem o ponteiro para aquele nó, ou que obter o ponteiro é trivial. Em outras palavras, o problema é afirmado: " dado nó em X , qual é o código a inserir após este nó?" Você começa no ponto de inserção.

A inserção em uma lista vinculada é diferente de iterar por ela. Você não está localizando o item, está redefinindo ponteiros para colocar o item lá. Não importa se ele será inserido próximo ao front-end ou próximo ao final, a inserção ainda envolve ponteiros sendo reatribuídos. Dependerá de como foi implementado, é claro, mas essa é a força das listas - você pode inserir facilmente. O acesso via índice é onde um array se destaca. Para uma lista, entretanto, normalmente será O (n) para encontrar o enésimo item. Pelo menos é o que me lembro da escola.

Porque não envolve nenhum loop.

Inserir é como:

• inserir elemento
• link para anterior
• link para o próximo
• feito

este é um tempo constante em qualquer caso.

Conseqüentemente, inserir n elementos um após o outro é O (n).

Essa análise não leva em consideração a descoberta da operação do nó (embora seja necessária) e apenas a própria inserção?

Você entendeu. A inserção em um determinado ponto pressupõe que você já segure um ponteiro para o item que deseja inserir após:

InsertItem(item * newItem, item * afterItem)

Inserir é O (1) assim que você souber onde irá colocá-lo.

Não, não leva em conta a pesquisa. Mas se você já tiver segurado um ponteiro para um item no meio da lista, inserir nesse ponto é O (1).

Se você tiver que pesquisá-lo, terá que adicionar o tempo da pesquisa, que deve ser O (n).

O artigo é sobre como comparar arrays com listas. Encontrar a posição de inserção para arrays e listas é O (N), portanto, o artigo a ignora.

O (1) depende do fato de você ter um item onde irá inserir o novo item. (antes ou depois). Se não o fizer, é O (n) porque você deve encontrar esse item.

Acho que é apenas o caso do que você escolhe para contar para a notação O (). No caso de inserir a operação normal para contar é operações de cópia. Com uma matriz, inserir no meio envolve copiar tudo acima do local na memória. Com uma lista encadeada, isso se torna a configuração de dois ponteiros. Você precisa encontrar o local independentemente do que inserir.

Se você tiver a referência do nó a inserir após a operação, é O (1) para uma lista vinculada.
Para uma matriz, ainda é O (n), pois você deve mover todos os nós consequentes.

Os casos mais comuns provavelmente estão inserindo no início ou no final da lista (e o final da lista pode demorar para ser encontrado).

Compare isso com a inserção de itens no início ou no final de um array (que requer redimensionar o array se estiver no final, ou redimensionar e mover todos os elementos se estiver no início).