Witam.
Czy majac do dyspozycji tylko wskaznik na poczatek i koniec posortowanej listy dwukierunkowej da sie do niej wstawic element w odpowiednie miejsce(aby dalej byla posortowana) w jakis szybszy sposob niz przegladanie elementu po elemencie?
Witam.
Czy majac do dyspozycji tylko wskaznik na poczatek i koniec posortowanej listy dwukierunkowej da sie do niej wstawic element w odpowiednie miejsce(aby dalej byla posortowana) w jakis szybszy sposob niz przegladanie elementu po elemencie?
Listy nie da się przeglądać inaczej ;] Chyba że pytasz czy da sie to zrobić bez "porównywania" kluczy wszystkich elementów po kolei. W takim wypadku jest to możliwe stosując zwykłe szukanie połówkowe, ale pytanie brzmi jak bardzo kosztowne jest porównanie kluczy a jak zrobienie next(). Bo szukanie połówkowe będzie nas kosztować 2 razy więcej operacji next() ale jednocześnie tylko log2(n)
porównań zamiast n
porównań.
Tak, chodzilo mi o porownywanie po kolei klucza kazdego elementu.
Czyli chyba nie ma co kombinować.
Dzieki za szybka odpowiedz :)