Por que está inserindo no meio de uma lista ligada O (1)?

Question

De acordo com o artigo Wikipedia sobre listas ligadas , inserindo no meio uma lista ligada é considerado O (1). Eu acho que seria O (n). Será que você não precisa para localizar o nó que pode estar perto do fim da lista?

Será que esta análise não conta para a conclusão da operação de nó (embora seja necessário) e apenas a própria inserção?

Editar :

As listas vinculadas têm várias vantagens sobre matrizes. A inserção de um elemento de um determinado ponto de uma lista é uma operação em tempo constante, enquanto que a inserção de uma matriz pode necessitar de mover metade dos elementos, ou mais.

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

Arrays:

• Encontrando-se o ponto de inserção / deleção O (1)
• Realizar a inserção / deleção O (n)

listas vinculadas:

• Encontrando-se o ponto de inserção / deleção O (n)
• Realizar a inserção / deleção O (1)

Eu acho que a única vez que você não teria que encontrar a posição é que se você manteve algum tipo de ponteiro para ele (como com a cabeça ea cauda, ??em alguns casos). Portanto, não podemos categoricamente dizer que as listas ligadas sempre bater matrizes para inserir opções / delete.

Answer 1

Você está correto, o artigo considera "Indexação" como uma operação separada. Assim, a inserção é em si O (1), mas chegar a esse nó central é O (n).

Answer 2

A inserção em si é O (1). constatação nó é O (n).

Answer 3

Não, quando você decidir que você deseja inserir, é assumido que você já está no meio de iteração através da lista.

As operações em listas vinculadas são muitas vezes feito de uma maneira tal que eles não são realmente tratados como uma "lista" genérico, mas como uma coleção de nós - acho que do próprio nó como o iterador para o seu loop principal. Então, como você está cutucando através da lista você notar como parte de sua lógica de negócios que uma nova necessidades nó a ser adicionado (ou um velho excluído) e você fazê-lo. Você pode adicionar 50 nós em uma única iteração e cada um desses nós é apenas O (1) o tempo para desvincular dois nós adjacentes e inserir o seu novo ..

Editar: Cara, você digite um segundo parágrafo e, de repente, em vez de ser a primeira resposta que você é o 5º dizendo a mesma coisa que o primeiro 4

Answer 4

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

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

Answer 5

A inserção em uma lista ligada é diferente do que a iteração através dele. Você não está localizando o item, você está redefinindo ponteiros para colocar o item lá. Não importa se ele vai ser inserido perto do final frente ou perto do fim, a inserção ainda envolve ponteiros a ser redesignados. Vai depender de como ele foi implementado, é claro, mas isso é a força de listas - você pode inserir facilmente. Acedem no índice é onde uma matriz brilha. Para obter uma lista, no entanto, vai ser tipicamente O (n) para encontrar o item enésimo. Pelo menos é o que eu me lembro da escola.

Answer 6

Porque não envolve qualquer looping.

Inserir é semelhante:

• elemento de inserção
• link para anterior
• link para o próximo
• feito

este é tempo constante em qualquer caso.

Por conseguinte, a inserção de elementos n um após o outro é O (n).

Answer 7

Será que esta análise não conta para a conclusão da operação de nó (embora seja necessário) e apenas a própria inserção?

Você tem isso. Inserção em um determinado ponto assume que você já possui um ponteiro para o item que você deseja inserir depois:

InsertItem(item * newItem, item * afterItem)

Answer 8

Inserir é O (1) uma vez que você sabe onde você está indo para colocá-lo.

Answer 9

Não, não conta para a pesquisa. Mas se você já tem a preensão de um ponteiro para um item no meio da lista, inserindo nesse momento é O (1).

Se você tem que procurar por ele, você teria que adicionar o tempo para pesquisa, que deve ser O (n).

Answer 10

O artigo é sobre a comparação de matrizes com listas. Encontrar a posição de inserção para as duas matrizes e listas é S (N), de modo que o artigo ignora.

Answer 11

O (1) está dependendo do fato de que você tem um item onde você irá inserir o novo item. (antes ou depois). Se você não, IT'S O (n) becuase você deve encontrar esse item.

Answer 12

Eu acho que é apenas um caso de 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, inserindo no meio envolve copiar tudo acima do local em memória. Com uma lista ligada, isso se torna definir dois ponteiros. Você precisa encontrar o local não importa o que inserir.

Answer 13

Se você tem a referência do nó para inserir após a operação é O (1) para uma lista ligada.
Para um array ainda é O (n), pois você tem que mover todos os nós consequtive.

Answer 14

Os casos mais comuns são provavelmente a inserção no início ou no fim da lista (e os confins da lista pode não levar tempo para encontrar).

Contraste isso com a inserção de itens no início ou no final de uma matriz (que exige o redimensionamento da matriz se é no final, ou redimensionar e mover todos os elementos se é no início).