Array vs. ArrayList

[Schorchy]

Hey,
bin momentan dabei das Buch "Java von Kopf bis Fuß" zu lesen.
nun kam ich an den teil wo sie die ArrayList vorstellen.
Dabei wurden sehr viele vorteile aufgezählt die für die ArrayList sprechen.

welchen Grund also gibs ein "normales" Array zu benutzen?

Danke schon mal im voraus
ich hoff mal ich hab da nichts übersehen das ich jetzt wie ein Idiot mit der Frage wirke

 

[Gast2]

Ein normales Array hat in puncto Geschwindigkeit und Speicherverbrauch weniger overhead als eine ArrayList.

 

[Marco13]

Es gibt aber nur SEHR wenige Fälle, wo das wirklich relevant ist. (Nur um zu verhindern, dass irgendjemand, der meint, sein Programm wäre zu langsam, pauschal alle Lists durch Arrays ersetzt...)

 

[faetzminator]

Auch gerade bei primitiven Datentypen kann ein Array von Vorteil sein, dann muss nicht immer zwischen dem primitiven Typen und der Wrapperklasse konvertiert werden.

 

[bygones]

Auch gerade bei primitiven Datentypen kann ein Array von Vorteil sein, dann muss nicht immer zwischen dem primitiven Typen und der Wrapperklasse konvertiert werden.

seit Autoboxing doch kein wirkliches Problem ?!

 

[faetzminator]

Ich dachte auch eher an die Laufzeit. Ist natürlich nicht in jedem Gebiet ein Thema, bei IO oder math. Berechnungen aber sicherlich...

 

[Marco13]

Vielleicht sollte ich das nochmal deutlicher sagen: Es gibt selten Gründe, einen int[] array statt einer List<Integer> zu verwenden. Aber ich kann mir gerade GAR keinen Fall vorstellen, wann man einen Object[] array statt einer List<Object> verwenden sollte.

Den int[]-Array statt der List<Integer> würde man eben verwenden, wenn es wirklich auf Speicherplatz und Performance ankommt. Genau darum ging's auch neulich in http://www.java-forum.org/mathematik/143300-kosinus-aehnlichkeit-x-y-matrix.html#post954684

Bis das Boxing/Unboxing zum Bottleneck wird, muss man schon mit wirklich vielen Werten (großen Arrays) hantieren, und dann gibt es (abgesehen vom Boxing) meistens noch andere Aspekte, die die Performance beeinflussen. Deswegen habe ich gerade nochmal den Thread http://www.java-forum.org/allgemein...nfluss-caching-performance-grosse-arrays.html ausgegraben, und den Test erweitert, um einen, der nicht auf einem int[] Array, sondern einem Integer-Array arbeitet - und man sieht, dass es zwar langsamer ist (bei mir hier - jaja...), aber das Caching eine viel größere Rolle spielt (bei mir hier - jaja ... )

public class CachingAndBoxingTest
{
    public static void main(String args[])
    {
        for (int n=1000; n<=5000; n+=1000)
        {
            int input[] = new int[n*n];
            for (int i=0; i<input.length; i++)
            {
                input[i] = i;
            }
            Integer inputObjects[] = new Integer[n*n];
            for (int i=0; i<input.length; i++)
            {
                inputObjects[i] = i;
            }
            
 
            long before = 0;
            long after = 0;
            int runs = 3;
            for (int i=0; i<runs; i++)
            {
                before = System.nanoTime();
                long result0 = runRowMajor(input, n);
                after = System.nanoTime();
                System.out.println("size "+n+" run "+i+" row    major       "+result0+" time "+(after-before)/1e6+" ms");

                before = System.nanoTime();
                long resultB = runRowMajorBoxed(inputObjects, n);
                after = System.nanoTime();
                System.out.println("size "+n+" run "+i+" row    major boxed "+resultB+" time "+(after-before)/1e6+" ms");
                
                before = System.nanoTime();
                long result1 = runColumnMajor(input, n);
                after = System.nanoTime();
                System.out.println("size "+n+" run "+i+" column major       "+result1+" time "+(after-before)/1e6+" ms");
            }
        }
    }
 
    private static long runRowMajor(int input[], int n)
    {
        long result = 0;
        for (int c=0; c<n; c++)
        {
            for (int r=0; r<n; r++)
            {
                result += input[r+c*n];
            }
        }
        return result;
    }

    private static long runRowMajorBoxed(Integer input[], int n)
    {
        long result = 0;
        for (int c=0; c<n; c++)
        {
            for (int r=0; r<n; r++)
            {
                result += input[r+c*n];
            }
        }
        return result;
    }
    
    private static long runColumnMajor(int input[], int n)
    {
        long result = 0;
        for (int r=0; r<n; r++)
        {
            for (int c=0; c<n; c++)
            {
                result += input[r+c*n];
            }
        }
        return result;
    }
 
    
}

 

[Schorchy]

Also hol ich meistens ne ArrayList und nur wenn es wirklich um geschwindigkeit gehen muss ein normales Array?

 

[Marco13]

Erstmal nur List und nicht ArrayList Und einen Array wenn es um primitive Typen geht UND das ganze kritisch bzgl. Speicherplatz und Performance ist, UND es mit Arrays schneller wird.

 

[hüteüberhüte]

int[]s müssen im Gegensatz zu ArrayList s nicht kopiert und vergrößert werden, der Unterschied spiegelt sich sogar in der asymptotischen Laufzeit wider

 

[Bernd Hohmann]

Ich für mich habe folgende Faustregel:

1) Wenn die Anzahl der Elemente vorgegeben/bekannt ist, dann nehme ich ein Array um klar zu zeigen "es sind immer genau 10 Elemente".
2) Wenn primitive Datentypen gespeichert werden sollen, dann versuche ich ein Array zu nutzen
3) Mehrdimensionale Arrays sowieso als Array

Natürlich lässt sich ein Array "int[256][256]" auch mit Autoboxing und einer ArrayList erledigen - die Gefahr, dass ein Kollege einem den Gnadenschuss wegen "unrettbar doof" erteilt ist allerdings nicht zu verachten.

Bernd

 

[maki]

Ich nutze Arrays nur bei Low Level Operationen oder weil eine Fremd-API auf Arrays besteht.
Autoboxing war bis jetzt kein Problem, wieso auch?.

 

[langhaar!]

Manchmal ist ein Array im Kontext lesbarer.
Für ein Schachbrett z.B. liest sich ein 2-dimensionales Array leichter als geschachtelte Array Listen.

 

[Network]

Eine ArrayList heißt "Array"List weil sich dahinter nichts weiter als ein Array verbirgt. Ist halt mit einigen Zusatzfunktionen ausgestattet.

Bei einem Array handelt es sich nunmal nur um eine Ansammlung von Referenzen, nicht mehr, nicht weniger, das wars.

Das Argument eine ArrayList wäre langsamer als ein Array greift eigentlich nur in dem besonderen Moment, wenn man bspw. ein Objekt der ArrayList mittendrin entfernt und nun alle Objekte in dem Array der ArrayList verschoben werden, damit wieder ein lückenloses Array entsteht.
Nur wer das als großes "Performance" einbußen versteht (Das geht eigentlich sogar extrem schnell durch System-Methoden) dann muss man wohl auf diese Methoden verzichten. Geht nicht besser.

Aber ein einfaches Array greift meistens dann ein, wenn man wirklich nur eine feste Anzahl an Referenzen braucht.
Ein Beispiel aus meinem letzten Projekt wäre, dass gewisse Zahlen hintereinander in einem Alghorithmus abgearbeitet werden mussten (Bspw. IP-Adressen). Und da sich die Anzahl der Zahlen mit der Erstellung eigentlich niemals ändern... ein einfaches Array.
Lässt sich auch schneller und vorallem übersichtlicher als Code schreiben mit { 1, 2, 3, 4, 5, ..., 100 }, anstatt hundertmal untereinander: arrayList.add( ... );

 

[faetzminator]

1) Wenn die Anzahl der Elemente vorgegeben/bekannt ist, dann nehme ich ein Array um klar zu zeigen "es sind immer genau 10 Elemente".

Ist für mich persönlich kein Grund, ein Array zu verwenden.

2) Wenn primitive Datentypen gespeichert werden sollen, dann versuche ich ein Array zu nutzen

Kommt immer drauf an, obs "Business Logic" ist oder sich um tieferliegende Dinge handelt. Beispiele hab ich bereits genannt.

Network: [c]List<String> list = Arrays.asList("foo", "bar", "baz");[/c]

 

[bygones]

int[]s müssen im Gegensatz zu ArrayList s nicht kopiert und vergrößert werden, der Unterschied spiegelt sich sogar in der asymptotischen Laufzeit wider

muessen ? Listen muessen auch nicht kopiert werden, solange du nicht mehr reinstecken willst als momentan geht. Dann hast du bei Arrays genau das selbe Problem. Somit kein Argument

Wenn die Anzahl der Elemente vorgegeben/bekannt ist, dann nehme ich ein Array um klar zu zeigen "es sind immer genau 10 Elemente"

wo bitte in einer API ist bei einem Array dann dieser Satz den ausgedrueckt ? egal ob mit einer Liste oder einen Array, vergroessern oder verkleinern kann man immer.

Wenn primitive Datentypen gespeichert werden sollen, dann versuche ich ein Array zu nutzen

wenn jedoch in anderen bereichen einfach eine Liste/Collection Typ gebraucht wird ist ein array erstmal unnuetz.

Wie Marco13 schon richtig sagte, eine Auswahl der beiden aufgrund von scheinbarer Performanz zu machen ist in 99,99999% der Faelle unsinn.

 

[Ark]

Bei unveränderlichen (unveränderbaren?) Datentypen nutze ich sehr gerne Arrays (der primitiven Typen, wenn möglich) statt List-Implementierungen, weil da der Overhead bzw. die typische Flexibilität einer List genau gar keinen Vorteil bringt. Bei primitiven Datentypen kommt es sehr auf den Einzelfall an, aber tendenziell nehme ich da auch Arrays des jeweiligen primitiven Typs (und keine Wrapper). Und für alles andere gibt es Colt: Colt - Welcome

Ark

 

[SlaterB]

Bei unveränderlichen (unveränderbaren?) Datentypen nutze ich sehr gerne Arrays (der primitiven Typen, wenn möglich) statt List-Implementierungen, weil da der Overhead bzw. die typische Flexibilität einer List genau gar keinen Vorteil bringt.

immerhin kann eine Liste tatsächlich unveränderlich sein/ gemacht werden, gar eine neue Klasse ohne set()
(edit: String als Beispiel, höheres char[] ),
in einem Array kann jeder tauschen/ überschreiben wie er lustig ist

 

[Ark]

immerhin kann eine Liste tatsächlich unveränderlich sein/ gemacht werden, gar eine neue Klasse ohne set(),
in einem Array kann jeder tauschen/ überschreiben wie er lustig ist

Klar, Schreibzugriffe auf dieses Array müssen dann verhindert werden. Dazu gibt es dann z.B. entweder entsprechende Getter (für die einzelnen Elemente) oder entsprechende Methoden, die das Array kopieren (

System.arraycopy()

) und dieses wiederum nötigenfalls in eine List packen. Iterator ginge natürlich auch – kommt halt darauf an.

[EDIT]Ganz grob kann man sagen: Ich benutze häufig (Array)List als eine Art ArrayBuilder, wenn man so will.[/EDIT]

Ark

 

[SlaterB]

[..] Methoden, die das Array kopieren [..] und dieses wiederum nötigenfalls in eine List packen.

es geht ja nun hauptsächlich um die direkte Verwendung,
dass intern einmalig versteckt sämtliche Daten letztlich in Arrays stehen, steht außer Frage, etwa eben ArrayList

dazu gibt es ja nur die Verlinkung als Alternative, für Indexzugriff ziemlich grausig,
auch String, HashMap & Co. brauchen Array

 

[ssoul26]

@TO Verstehe den Author und du hast es raus.

-> ArrayList

/**
 * Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)<p>
 *
 * The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
 * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
 * that is, adding n elements requires O(n) time.  All of the other operations
 * run in linear time (roughly speaking).  The constant factor is low compared
 * to that for the <tt>LinkedList</tt> implementation.<p>
 *
 * Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
 * the size of the array used to store the elements in the list.  It is always
 * at least as large as the list size.  As elements are added to an ArrayList,
 * its capacity grows automatically.  The details of the growth policy are not
 * specified beyond the fact that adding an element has constant amortized
 * time cost.<p>
 *
 * An application can increase the capacity of an <tt>ArrayList</tt> instance
 * before adding a large number of elements using the <tt>ensureCapacity</tt>
 * operation.  This may reduce the amount of incremental reallocation.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
 * and at least one of the threads modifies the list structurally, it
 * <i>must</i> be synchronized externally.  (A structural modification is
 * any operation that adds or deletes one or more elements, or explicitly
 * resizes the backing array; merely setting the value of an element is not
 * a structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the list.
 *
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
 *
 * <p>The iterators returned by this class's <tt>iterator</tt> and
 * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
 * structurally modified at any time after the iterator is created, in any way
 * except through the iterator's own <tt>remove</tt> or <tt>add</tt> methods,
 * the iterator will throw a {@link ConcurrentModificationException}.  Thus, in
 * the face of concurrent modification, the iterator fails quickly and cleanly,
 * rather than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.<p>
 *
 * Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness: <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i><p>
 *
 * This class is a member of the
 * <a href="http://www.java-forum.org/java-basics-anfaenger-themen/technotes/guides/collections/index.html">
 * Java Collections Framework</a>.

 

[hüteüberhüte]

muessen ? Listen muessen auch nicht kopiert werden, solange du nicht mehr reinstecken willst als momentan geht. Dann hast du bei Arrays genau das selbe Problem. Somit kein Argument

Fehlen bei dir neuerdings die Umlaut-Tasten?

Natürlich müssen ALs vergrößert werden, wenn ihr Limit erreicht ist.

Nimm ein Array, in das n Elemente rein sollen: Laufzeit n=O(n). Nimm eine AL: Laufzeit schlechtestenfalls (n^2)/2=O(n^2). Nimm die Hälfte davon, dann erhältst du immer noch (n^2)/4...

Außerdem müssen wieder massig Objekte erzeugt werden.

Nur jemand im totalen OOP-Wahn würde die Nachteile verschweigen. Wie es hier wiedereinmal der Fall ist...

 

[maki]

ArrayList (Java Platform SE 7 )

Der "Nachteil" ist erstmal rein theoretisch, nur jemand im "Sinnlos-Optimier-Wahn-obwohl-gar-kein-Anlass-besteht" würde das verschweigen.

 

[hüteüberhüte]

Ich kenne die Api. Danke! Zum Glück muss ich mit niemanden arbeiten, der langsamen, unsauberen AL-Code schreibt, weil er Arrays primitiver Typen vorher nie kennengelernt hat

 

[maki]

Ich kenne die Api. Danke!

Dann wundere ich mich warum du dann so argumentierst:

Nimm ein Array, in das n Elemente rein sollen: Laufzeit n=O(n). Nimm eine AL: Laufzeit schlechtestenfalls (n^2)/2=O(n^2). Nimm die Hälfte davon, dann erhältst du immer noch (n^2)/4...

Denn wenn man die API kennen würde, wüsste man, dass das dieses Argument schlicht falsch ist.

 

[Bernd Hohmann]

Natürlich müssen ALs vergrößert werden, wenn ihr Limit erreicht ist.

bygones sagte "Listen muessen auch nicht kopiert werden, solange du nicht mehr reinstecken willst als momentan geht."

Wenn die ArrayList also auf die gewünschte Grösse initialisiert wurde (wie ein Array auch) muss auch nichts vergrössert werden.

Bernd

 

[hüteüberhüte]

Es ging um zwei Situationen. Einmal kenne ich die Länge vorher und einmal kenne ich sie nicht. Dann wird es schwierig werden, ein Limit anzugeben... Aber ist auch egal. Wie konnte ich es nur wagen, dir hochgelobten, gottgleichen Moderator zu widersprechen...

 

[SlaterB]

was kommen hier wieder für Aussagen zusammen, allein das Befüllen einer Liste ist von Komplexität n^2?
uiui, dann muss sich Collections.sort() ja gar nicht um n log(n) bemühen..

> Außerdem müssen wieder massig Objekte erzeugt werden.

mehr als eins, die ArrayList? das Array so oder so, ok, paar Arrays evtl. beim Umkopieren,
wieviele ist ja schon für n^2 die Frage, so viele sinds nicht, keine Handvoll bevor der Speicher voll ist, da eben die Größe immer verdoppelt wird


hüteüberhüte, wie lange willst du das uns allen noch antun, dass nur du allein schlau bist und alle anderen 'naja' ist ja klar
(obwohl die Wahrscheinlichkeitstheorie warnt), aber musst du dann weiter hier die Welt vor den anderen retten?

edit:
eigentlich nicht richtig zu meckern, aber so bezeichnend:
ich habe das Thema schon gestern nach hütes Post 17:49 abonniert, als ich noch nichts selber geschrieben habe,
die nur eine Zeile stand erstmal so da, dass die kommentiert und dann ausgeführt werden würde schien klar,
hat erstaunlich lang gedauert, aber so kommt es nun

 

[hüteüberhüte]

edit:
eigentlich nicht richtig zu meckern, aber so bezeichnend:
ich habe das Thema schon gestern nach hütes Post 17:49 abonniert, als ich noch nichts selber geschrieben habe,
die nur eine Zeile stand erstmal so da, dass die kommentiert und dann ausgeführt werden würde schien klar,
hat erstaunlich lang gedauert, aber so kommt es nun

Ich hatte das Thema auch abonniert, aber eine Reaktion ließ so lang auf sich warten, das ich ins Bett musste Aber egal, scheint ja offenbar alles ausführlich erklärt worden sein

 

[bygones]

Fehlen bei dir neuerdings die Umlaut-Tasten?

Lebe in daenemark und die haben nunmal keine dt umlaute...

Dafuer dass du die API meinst zu kennen, redest du recht viel Unwahrheiten...

Aber wenn es dich gluecklich macht ;-)

 

[maki]

Es ging um zwei Situationen. Einmal kenne ich die Länge vorher und einmal kenne ich sie nicht. Dann wird es schwierig werden, ein Limit anzugeben... Aber ist auch egal.

Wie jetzt?

Die hast doch selber gesagt:

Nimm ein Array, in das n Elemente rein sollen: Laufzeit n=O(n). Nimm eine AL: Laufzeit schlechtestenfalls (n^2)/2=O(n^2). Nimm die Hälfte davon, dann erhältst du immer noch (n^2)/4...

Also doch feste Größe..

Wie machst du das eigentlich , wenn du die Größe eben vorher nicht kennst?
Einfach ein Array beliebiger Größe allokieren, und wenn das zu klein wird, neues Array anlegen und umkopieren.. ?

Wie konnte ich es nur wagen, dir hochgelobten, gottgleichen Moderator zu widersprechen...

*gähn*

 

[Schorchy]

Also um das mal nochmal zusammen zu fassen:

Array´s nehme ich am besten wenn wenn ich die größe vorher kenne und diese auch nicht verändert werden muss.
=> da sie in dem fall übersichtlicher sind als eine List

List´s nehme ich wenn ich die größe nicht kenne und/oder diese sich verändert
=> da sie in dem fall einfacher zu handeln sind

ungefähr richtig ?

 

[Bernd Hohmann]

Array´s nehme ich am besten wenn wenn ich die größe vorher kenne und diese auch nicht verändert werden muss. => da sie in dem fall übersichtlicher sind als eine List

List´s nehme ich wenn ich die größe nicht kenne und/oder diese sich verändert => da sie in dem fall einfacher zu handeln sind.

Ja, so kann man das stehen lassen. Bei primitiven Datentypen und mehrdimensionalen Arrays sollte man versuchen mit Arrays zu arbeiten.

Ein normales Array zu vergrössern ist ja auch kein Hexenwerk: neues Array mit der gewünschten Grösse anlegen, mit System.arraycopy(...) das alte Array an den Anfang des neuen kopieren und das alte Array wegschmeissen (oder das neue dem alten zuweisen). 3 Zeilen, gut ist.

Bernd

 

[ARadauer]

welchen Grund also gibs ein "normales" Array zu benutzen?

a varargs
b weil es eine fremde api benötigt

 

[Marco13]

Natürlich lässt sich ein Array "int[256][256]" auch mit Autoboxing und einer ArrayList erledigen - die Gefahr, dass ein Kollege einem den Gnadenschuss wegen "unrettbar doof" erteilt ist allerdings nicht zu verachten.

Da meine Aussagen in dieser Richtung interpretiert werden könnten: Sowas würde man natürlich eher nicht als List<List<Integer>> modellieren. Es gäbe da zwei Fälle zu unterscheiden:
1. Es wird nicht nach draußen gegeben. Dann: Sch... drauf, da kann man machen was man will, und wenn man 256*256 ints braucht, macht man sich einen int[256][256], klar (ich bin davon ausgegangen, dass es darum gar nicht ging - das mag rückblickend und bei der pauschalen Eingangsfrage ungerechtfertigt sein )
2. Es wird nach draußen gegeben. Dann würde man eben NICHT den Array nach draußen geben. Wenn überhaupt, dann eine unmodifiable List aus (ggf. auch wieder unmodifiablen) List<Integer>, aber vermutlich nicht mal das. Für so einen Fall will man das, was man dort modelliert, vermutlich eher über gezielte Methoden [c]getSizeX/getSizeY/get(x,y)[/c] nach außen verfügbar machen. Zumindest würde ich einem Kollegen, der

public class SomeClass
{
    private int array[][] = ...
    public int[][] getArray() { ... }
}

macht einige sehr kritische Fragen stellen (modulo der angedeuteten Spezialfälle)

Nimm ein Array, in das n Elemente rein sollen: Laufzeit n=O(n). Nimm eine AL: Laufzeit schlechtestenfalls (n^2)/2=O(n^2).

was kommen hier wieder für Aussagen zusammen, allein das Befüllen einer Liste ist von Komplexität n^2?

Sooo unplausibel ist das gar nicht, aber in diesem Fall (bei ArrayList) eben doch falsch. Wenn das Befüllen einer ArrayList wie so ablaufen würde, wäre es O(n^2)

void einfügen()
{
    if (kein Platz mehr im Array)
    {
        vergrößere den Array um eine konstante Größe x
    }
    füge Element in Array ein
}

Allerdings ist es in ArrayList so, und damit O(n)

void einfügen()
{
    if (kein Platz mehr im Array)
    {
        vergrößere den Array um einen konstanten Faktor x
    }
    füge Element in Array ein
}

 

[SlaterB]

Allerdings ist es in ArrayList so, und damit O(n)

O(n log n)
paar mal Umkopieren schon, aber was zählen schon 50 Durchgänge bis zur Milliarde bei Faktor 1.5

 

[Marco13]

Ohne mich jetzt auf die Ebene eines mathematischen Beweises herablassen zu wollen: Es würde mich wundern, wenn es auf vector<T, Alloc> schon seit 1X Jahren falsch stünde...

 

[SlaterB]

möglicherweise wird hier den technischen Rahmenbedingungen Rechnung getragen,
keine 50x Umkopieren bevor nicht eh der Speicher voll wäre, mehr kann es gar nicht sein,
zudem dürfte ein Umkopieren kaum so lange dauern wie das normale Einfügen von Millionen Elementen
bzw. z.B. ein Merge-Vorgang beim Sortieren,

der konstante Faktor senkt das 50x noch weiter ab, so dass man letztlich nahe bei n bleibt, z.B. 2x n oder nur 1.1x n,
darauf kann man dann eben verzichten

allerdings würde das die Aussage 'the latter case it is quadratic' auch etwas abgeschwächen,
aber n* (1 + n/1000) darf wohl auch als n^2 gelten