No to je pomerne jasny.. Naplneni ArrayListu od zacatku bude mit slozitost O(n^2) - N x vkladam a N x kopiruju pole (celkova velikost zkopirovanych dat = suma od 0 do N-1)
U LinkedListu je to O(n) - N x naalokuju objekt a nastavim pointery. Pokud to plnite na konci, LinkedList vychazi stejne, ArrayList bude mit O(n) (vkladam N x, log(N) x se realokuje pole, ale amortizovana slozitost na jedno vkladani vyjde konstatni..) Takze rozdil v rychlosti bude v tomto pripade konstanta zpusobena tim, ze alokace malych objektu nic nestoji, jak pravi O SUN :) Jarda -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Tuzinsky Vladimir Sent: Wednesday, October 12, 2005 12:54 PM To: 'Java' Subject: RE: Parametr metody List.toArray(Object[]) Po par testoch s ArrayList a LinkedList sa mi zda, ze LinkedList ma vyznam iba v pripade, ze potrebujete pridavat prvky inde ako na koniec pola. Vtedy ArrayList musi kopirovat koniec pola. Napr. List list = new ArrayList(); for (int i = 0; i < 100000; i++) { list.add(0, new Integer(i)); } trva na mojom stroji viac ako 7s, zatial co to iste s LinkedList len nieco cez 100ms. Pri pridavani na koniec pola potrebuje LinkedList asi dva krat tolko casu ako ArrayList... bobes -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Oto Buchta Sent: Wednesday, October 12, 2005 12:28 To: Java Subject: Re: Parametr metody List.toArray(Object[]) On Wednesday 12 of October 2005 12:24, Martin Kuba wrote: > Patrik Beno wrote: > > proste > > list.toArray(new String[list.size()]) > > ma svoj zmysel... > > Naprosty souhlas. Kdyz uz tu probirame Listy, donedavna > jsem s oblibou pouzival konstrukci > > List l = new LinkedList(); > ResultSet rs = jdbcStatement.executeQuery(); > while(rs.next()) { > l.add(rs.getString(1)); > } > String[] s = (String[]) l.toArray(new String[l.size()]); > > abych prevedl predem neznamy pocet vracenych hodnot na pole. > Mel jsem pocit, ze LinkedList je na to vhodny, protoze zbytecne > nealokuje navickrat zadna pole. > > A nedavno mne Heinz Kabutz presvedcil, ze je rozumnejsi pouzivat > i na tohle ArrayList, protoze i kdyz si pri postupnem rustu > musi naalokovat vic poli, porad spotrebuje nakonec min pameti > nez LinkedList, ktery na kazdy prvek potrebuje navic jeden ukazatel. > Toz se chci o tohle zjisteni podelit. Dva. LinkedList je obousmerny spojovy seznam. LinkedList.Entry: private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } } Apropros mate vubec nekdo nejaky use-case, kde LinkedList je lepsi nez ArrayList()? -- Oto 'tapik' Buchta, [EMAIL PROTECTED] Senior Engineer, Systinet Corp, http://www.systinet.com
