Dlaczego wstawianie w środku połączonej listy O (1)?

Zgodnie z artykułem Wikipedii dotyczącym list połączonych , wstawianie w środku listy , do której prowadzą linki, jest uważane za O (1). Myślę, że to będzie O (n). Czy nie musiałbyś zlokalizować węzła, który mógłby znajdować się blisko końca listy?

Czy ta analiza nie uwzględnia znalezienia operacji węzła (choć jest to wymagane) i samego samego wstawienia?

EDYCJA :

Listy połączone mają kilka zalet w porównaniu z tablicami. Wstawienie elementu w określonym miejscu listy jest operacją wykonywaną w czasie stałym, natomiast wstawienie do tablicy może wymagać przesunięcia połowy lub więcej elementów.

Powyższe stwierdzenie jest dla mnie trochę mylące. Popraw mnie, jeśli się mylę, ale myślę, że wniosek powinien być taki:

Tablice:

• Znajdowanie punktu wstawienia / usunięcia O (1)
• Wykonywanie wstawiania / usuwania O (n)

Połączone listy:

• Znalezienie punktu wstawienia / usunięcia O (n)
• Wykonywanie wstawiania / usuwania O (1)

Myślę, że jedynym momentem, w którym nie musiałbyś znaleźć pozycji, jest zachowanie jakiegoś wskaźnika (tak jak w niektórych przypadkach w przypadku głowy i ogona). Nie możemy więc jednoznacznie powiedzieć, że połączone listy zawsze pokonują tablice w przypadku opcji wstawiania / usuwania.

Masz rację, artykuł traktuje „Indeksowanie” jako oddzielną operację. Zatem wstawienie samo w sobie jest O (1), ale dotarcie do środkowego węzła to O (n).

Samo wstawienie to O (1). Znalezienie węzła to O (n).

Nie, kiedy zdecydujesz, że chcesz wstawić, zakłada się, że jesteś już w trakcie iteracji listy.

Operacje na listach połączonych są często wykonywane w taki sposób, że tak naprawdę nie są traktowane jako ogólna „lista”, ale jako zbiór węzłów - pomyśl o samym węźle jako o iteratorze dla głównej pętli. Przeglądając listę, zauważasz w ramach logiki biznesowej, że należy dodać nowy węzeł (lub usunąć stary) i robisz to. Możesz dodać 50 węzłów w jednej iteracji, a każdy z tych węzłów to tylko O ​​(1) czas na rozłączenie dwóch sąsiednich węzłów i wstawienie nowego.

Edycja: Człowieku, wpisujesz drugi akapit i nagle, zamiast być pierwszym, jesteś piątym, który mówi to samo, co pierwsze 4!

Dla celów porównania z tablicą, co pokazuje ten wykres, jest to O (1), ponieważ nie musisz przenosić wszystkich elementów po nowym węźle.

Więc tak, zakładają, że masz już wskaźnik do tego węzła lub że uzyskanie wskaźnika jest trywialne. Innymi słowy, problem jest określony: „ dany węzeł w X , jaki kod wstawić po tym węźle?” Możesz zacząć od punktu wstawiania.

Wstawianie do połączonej listy różni się od iteracji po niej. Nie lokalizujesz elementu, resetujesz wskaźniki, aby umieścić tam element. Nie ma znaczenia, czy ma zostać wstawiony w pobliżu przedniego końca, czy blisko końca, wstawianie nadal wymaga ponownego przypisania wskaźników. Będzie to oczywiście zależeć od tego, jak zostało zaimplementowane, ale to jest siła list - można je łatwo wstawiać. Dostęp przez indeks jest tam, gdzie świeci tablica. Jednak w przypadku listy zwykle będzie to O (n), aby znaleźć n-ty element. Tak przynajmniej pamiętam ze szkoły.

Ponieważ nie wymaga zapętlenia.

Wstawianie wygląda tak:

• wstaw element
• link do poprzedniego
• link do następnego
• Gotowe

w każdym przypadku jest to stały czas.

W konsekwencji wstawienie n elementów jeden po drugim daje O (n).

Czy ta analiza nie uwzględnia znalezienia operacji węzła (choć jest to wymagane) i samego samego wstawienia?

Masz to. Wstawianie w danym punkcie zakłada, że ​​masz już wskaźnik do elementu, który chcesz wstawić po:

InsertItem(item * newItem, item * afterItem)

Wstawianie jest O (1), gdy już wiesz, gdzie go wstawisz.

Nie, nie uwzględnia wyszukiwania. Ale jeśli masz już wskaźnik do elementu na środku listy, wstawienie w tym miejscu jest O (1).

Jeśli musisz go szukać, musisz dodać czas wyszukiwania, który powinien wynosić O (n).

Artykuł dotyczy porównania tablic z listami. Znalezienie pozycji wstawiania zarówno dla tablic, jak i list to O (N), więc artykuł to ignoruje.

O (1) zależy od tego, że masz element, do którego wstawisz nowy element. (Przed lub po). Jeśli nie, to jest O (n), ponieważ musisz znaleźć ten przedmiot.

Myślę, że to tylko przypadek tego, co zdecydujesz się liczyć dla notacji O (). W przypadku wstawienia do zliczenia normalnej operacji jest kopiowanie. W przypadku tablicy wstawianie w środku polega na skopiowaniu wszystkiego powyżej lokalizacji do pamięci. W przypadku listy połączonej staje się to ustawieniem dwóch wskaźników. Musisz znaleźć lokalizację bez względu na to, co wstawić.

Jeśli masz odniesienie do węzła do wstawienia po operacji, to O (1) dla połączonej listy.
Dla tablicy jest to nadal O (n), ponieważ musisz przenieść wszystkie kolejne węzły.

Najczęstsze przypadki to prawdopodobnie wstawianie na początku lub na końcu listy (a znalezienie końców listy może zająć dużo czasu).

Porównaj to z wstawianiem elementów na początku lub na końcu tablicy (co wymaga zmiany rozmiaru tablicy, jeśli jest na końcu, lub zmiany rozmiaru i przeniesienia wszystkich elementów, jeśli jest na początku).