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

105

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.

Rob Sobers
źródło

Odpowiedzi:

113

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).

CookieOfFortune
źródło
3
Co robi większą różnicę przy wstawianiu więcej niż 1 obiektu w tej samej pozycji ...
Ma QUIT - Anony-Mousse
@ Anony-Mousse czy możesz to trochę wyjaśnić? tzn. musimy znaleźć pozycję wstawienia tylko raz podczas wstawiania kilku obiektów?
MyTitle
2
To O (n) w rozmiarze istniejącej listy, a nie liczbie wstawień, które planujesz tam zrobić.
ZAKOŃCZYŁO - Anony-Mousse
28

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

Evansbee
źródło
25

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!

Bill K.
źródło
1
Ha tak, to jest do bani ... Dałem +1 Twojej, ponieważ warto stwierdzić, że złożoność wstawiania połączonych list jest rozważana w kontekście znajdowania się już w pożądanym wskaźniku.
Daniel Macias
6

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.

Joel Coehoorn
źródło
5

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.

itsmatt
źródło
3

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).

Tomalak
źródło
3

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)
e.James
źródło
2

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

Lance Richardson
źródło
2

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).

PRZETRZĄSAĆ
źródło
0

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.


źródło
1
Czy znalezienie punktu wstawienia tablicy nie byłoby O (1)? Ponieważ tablice są przechowywane w ciągłej pamięci, wszystko, co należy zrobić, to dodać przesunięcie.
Rob Sobers
@ vg1890 - Najpierw musisz znaleźć przesunięcie.
0

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.

Glenn
źródło
0

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ć.

workmad3
źródło
0

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.

Sani Singh Huttunen
źródło
0

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).

ChrisW
źródło
Możliwe jest, aby wstawianie elementów na koniec tablicy było O (1), jeśli utrzymujesz bufor pustych elementów na końcu, chociaż czasami wstawki nadal będą miały wartość O (1). Większość kolekcji to robi. Możliwe jest również ustawienie inertowania elementów na początku tablicy na O (1), zmieniając operator indeksu na zwracający numer elementu (n + x)% len, gdzie x to liczba razy wstawiono elementy na początek listy. Deques są czasami implementowane w ten sposób (ale czasami są również implementowane z podwójnie połączonymi listami.
Brian