Say mam ArrayList z n elementów w tej tablicy, a ja dodać element na początku:Jaka jest złożoność czasu dodawania elementu na początku tablicy ArrayList?
myArrayList.add(0,'some value');
Jaki będzie złożoność czas tej operacji?
Nie określa tego Java Doc.
także
po prostu rozpocząć naukę języka Java, a ja zobaczyłem zdanie
An ArrayList in Java is a List that is backed by an array.
Co oznacza 'wspierany' tu chodzi? Dziękuję Ci!
Dodawanie elementu do początku tablicy to O (n) - wymagałoby przesunięcia wszystkich istniejących elementów o jedną pozycję.
Wszystkie elementy na liście tablic są przechowywane w ciągłej tablicy. Jeśli dodasz więcej elementów niż obecny rozmiar tablicy - zostanie ona automatycznie wyhodowana, aby pomieścić nowy element.
Dodatkiem do końca jest O (1) zamortyzowany na wielu wstawkach.
Wiem, że O (n) jest normalnym przypadkiem, ale właściwie pytałem, czy Java ma w tym przypadku jakąś magię (jak wspomniano o Louisezie Wassermanie)? Przepraszam, że nie jest wystarczająco jasne! – lakeskysea
Co masz na myśli mówiąc "ten przypadek"? –
@LouisWasserman przepraszam, mam na myśli "tę operację". ta operacja zwykle zajmuje O (n), ale zastanawiałem się, czy implementacja Java ma jakiś "inteligentny" sposób dodawania elementu na początku ArrayList. Czy możesz nieco rozwinąć swoją odpowiedź, dlaczego trwa to liniowo? – lakeskysea
ArrayList.add(0, element) zajmuje czas liniowy, ale stała jest bardzo niska, ponieważ może korzystać z płonącego szybkiego System.arraycopy.
Oznacza to, że 'ArrayList' jest implementacją, a' List' jest interfejsem. –
ArrayList jest technicznie po prostu tablicą w pewnym sensie. Używa metody System.arraycopy do obsługi dodawania i usuwania elementów. W takim przypadku utworzy dwie tablice: jedną z 0-0 (pustą) i drugą z (0-n). Następnie tworzy nową tablicę o długości + 1 i łączy je wszystkie razem, umieszczając nowy element w odpowiednim indeksie. –