ArrayList vs LinkedList vs ?

CodeIt

Aktives Mitglied
Hallo,

es soll ein Menge von Integer-Zahlen, deren genaue Anzahl nicht bekannt ist, in einer Liste nach und nach gespeichert werden (Reihenfolge ist egal). Anschließend soll eine dieser Zahlen zufällig aus dieser Liste mit Math.random gewählt werden. D.h. es wird in Abhängigkeit von der Größe der Liste ein zufälliger Index gewählt, anhand dessen dann auf die Zahl in der Liste zugegriffen werden soll.

Ich frage mich, welche Datenstruktur wäre hier besser geeignet.
LinkedList soll ja schneller sein, wenn man Werte einfügen möchte, wobei hier ja der Wert immer als letztes Element angefügt werden soll. Auf eine ArrayList kann ich bei bekannten Index jedoch schneller zugreifen.

Was würdet ihr empfehlen, oder gibt es eine bessere Datenstruktur?

Vielen Dank
 

CodeIt

Aktives Mitglied
Danke, aber auf der Seite steht:
  1. Adding 50K elements in ArrayList took 10 ms
  2. Adding 50K elements in LinkedList took 7 ms
"LinkedList is slower at adding elements".

Müßte es nicht heißen, das LinkedList ist schneller beim Anfügen von Elementen?
 

Javinner

Top Contributor
Die Poente:
As you will see in the output above:

  • LinkedList is significantly slower at accessing and modifying elements
  • LinkedList is slower at adding elements
  • LinkedList is much faster at removing elements from the beginning of the list
  • ArrayList inserts new elements slower
  • ArrayList is significantly faster at accessing and modifying elements
  • ArrayList is significantly slower at removing elements from the beginning of the list
Disclaimer
The algorithm complexity and the operations performance is not constant in all cases. There are two major factors you have to take into account – the size of the list and where the elements we work with are placed in the list (at the beginning, in the middle or at the end). The only constant rule is: use ArrayList if you want to retrieve elements faster and LinkedList if you want to manipulate data faster.
 

CodeIt

Aktives Mitglied
ok, ich möchte Elemente einfach hinten anfügen. Und nachdem alle Elemente hinten angefügt wurden nur eines dieser Elemente zufällig wählen und eben direkt auf dieses eine Element zugreifen. Das würde also heißen eine ArrayList wäre hier die bessere Lösung, oder?
 

CodeIt

Aktives Mitglied
so z.B.:
Code:
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        long start2 = System.currentTimeMillis();
        for(int i = 0; i < 1000000; i++){
            linkedList.add(i);
        }
        long ende2 = System.currentTimeMillis() - start2;
        System.out.println("LinkedList "+ende2);
      
      
        ArrayList<Integer> arrayList = new ArrayList<Integer>();      
        long start = System.currentTimeMillis();      
        for(int i = 0; i < 1000000; i++){
            arrayList.add(i);
        }
        long ende = System.currentTimeMillis() - start;
        System.out.println("ArrayList "+ ende);
      
      
      
        long start4 = System.currentTimeMillis();
        int index2 = (int) (Math.random()*linkedList.size());
        Integer rando2 = linkedList.get(index2);
        long ende4 = System.currentTimeMillis()-start4;
        System.out.println("Random LinkedList "+ rando2 + "   "+ende4);
      
      
      
        long start3 = System.currentTimeMillis();
        int index = (int) (Math.random()*arrayList.size());
        Integer rando = arrayList.get(index);
        long ende3 = System.currentTimeMillis()-start3;
        System.out.println("Random ArrayList "+ rando + "   "+ende3);
 

Javinner

Top Contributor
Java:
public class CodeIt
{

    public static void main(String[] args)
    {

        List<Integer> firstAL = new ArrayList<>();
        firstAL.add(1);
        System.out.println("AL: " + firstAL.toString());
        firstAL.add(2);
        System.out.println("AL: " + firstAL.toString());
        List<Integer> firstLL = new LinkedList<>();
        firstLL.add(1);
        System.out.println("LL: " + firstLL.toString());
        firstLL.add(2);
        System.out.println("LL: " + firstLL.toString());

        int range = 1_000_000;
        List<Integer> integerAL = new ArrayList<>();
        List<Integer> integerLL = new LinkedList<>();

        System.out.println("fill");
        fill(integerAL, range);
        fill(integerLL, range);
        System.out.println("getIntegerAtIndex");
        int al = getIntegerAtIndex(integerAL, range / 2);
        int ll = getIntegerAtIndex(integerLL, range / 2);
        System.out.println("AL: " + al + ", LL: " + ll);

    }

    static List fill(List list, int count)
    {
        long start = System.currentTimeMillis();
        Random random = new Random();
        while (count > 0) {
            int nummber = random.nextInt(1000) + 1;
            list.add(nummber);
            count--;
        }
        long finisch = System.currentTimeMillis() - start;
        System.out.println(finisch);
        return list;
    }

    static int getIntegerAtIndex(List list, int index)
    {
        long start = System.currentTimeMillis();
        int i = (int) list.get(index);
        long finisch = System.currentTimeMillis() - start;
        System.out.println(finisch);
        return i;
    }

}
/** Konsolenausgabe */
AL: [1]
AL: [1, 2]
LL: [1]
LL: [1, 2]
/** Also fuegen beide Listen mit der Methode add() die neuen Werte am Ende der Liste ein */
fill
30 //ArrayList deutlich schneller
109
getIntegerAtIndex
1 //ArrayList deutlich schneller
4
AL: 47, LL: 706 //Zufallswerte, nicht weiter beachten
 

Javinner

Top Contributor
Java:
static void changeIntegerAtIndex(List list, int index)
{
        long start = System.currentTimeMillis();
        int i = 1_000_000;
        list.set(index, i);
        long finisch = System.currentTimeMillis() - start;
        System.out.println(finisch);
}
/** Konsolenausgabe */
changeIntegerAtIndex
0 //ArrayList wieder im Vorteil
3
 

CodeIt

Aktives Mitglied
Vielen Dank. Vielleicht noch eine Frage, weil jetzt zusätzlich noch die contains()-Methode teste.
Ich hätte erwartet das hier die LinkedList schneller wäre als die ArrayList, dem ist aber nicht so, da
sind die beiden annähernd gleichschnell. Kann das sein?
 

Javinner

Top Contributor
CodeIt hat gesagt.:
Was ist den schon beständiger als Wetter, mein Lieber
Ob die eine oder andere Liste schneller ist, hängt von den Anforderungen ab.
Immer dann, wenn so eine Frage im Raum steht, mache ich ein kleinen Test, welcher die jeweilige Anforderung testet.
Danach sieht man es dann, was besser ist. Ich nahm die Mühe auf mich, um dir zu zeigen, wie schnell so ein Test geschrieben ist, so teste doch einfach ;)
 

mrBrown

Super-Moderator
Mitarbeiter
Danach sieht man es dann, was besser ist. Ich nahm die Mühe auf mich, um dir zu zeigen, wie schnell so ein Test geschrieben ist, so teste doch einfach ;)
Für sowas bietet sich btw JMH an ;)

Vielleicht noch eine Frage, weil jetzt zusätzlich noch die contains()-Methode teste.
Ich hätte erwartet das hier die LinkedList schneller wäre als die ArrayList, dem ist aber nicht so, da
sind die beiden annähernd gleichschnell. Kann das sein?
Ja, Komplexität von contains ist für beide O(n), die Implementierung von ArrayList hat da aber leichte Vorteile.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
O Hashmap, ArrayList, LinkedList Java Basics - Anfänger-Themen 7
C LinkedList vs. ArrayList Java Basics - Anfänger-Themen 15
O LinkedList zu ArrayList Java Basics - Anfänger-Themen 4
J Per I/O Streams in LinkedList oder ArrayList schreiben/lesen Java Basics - Anfänger-Themen 6
I LinkedLIst / ArrayList Konstruktor Java Basics - Anfänger-Themen 4
S Speichermangel ArrayList/LinkedList Java Basics - Anfänger-Themen 3
B Unterschied ArrayList und LinkedList Java Basics - Anfänger-Themen 5
S Implementierung gegen Interfaces / List, ArrayList, LinkedList Java Basics - Anfänger-Themen 11
J LinkedList, Collection, ArrayList, List. was denn bitte? Java Basics - Anfänger-Themen 6
krgewb ArrayList allgemein halten Java Basics - Anfänger-Themen 6
M Ausgabe einer ArrayList ensteht nur als Hashcode, nicht als Objekt Java Basics - Anfänger-Themen 16
S Java: Wie sortiere ich eine ArrayList benutzerdefinierter Objekte nach einem bestimmten Attribut? Java Basics - Anfänger-Themen 2
J ArrayList in 2D-Array konvertieren. Java Basics - Anfänger-Themen 48
E Arrays in einer ArrayList miteinander vergleichen Java Basics - Anfänger-Themen 12
String in ArrayList umwandeln Java Basics - Anfänger-Themen 1
F Arraylist<String>Ein Wort pro Zeile Java Basics - Anfänger-Themen 6
J ArrayList vergleichen im spiel Mastermind Java Basics - Anfänger-Themen 2
Mugetsu35 ArrayList Update ohne Index Java Basics - Anfänger-Themen 6
W Objekte einer ArrayList in txt-datei schreiben mit Paths? Java Basics - Anfänger-Themen 2
Z Java ArrayList speichert falsche Daten ab bzw. gibt falsche Daten aus? Java Basics - Anfänger-Themen 42
W if-Abfrage bei ArrayList-Methodenaufrufen - Wie löse ich das? Java Basics - Anfänger-Themen 6
W ArrayList und toString Java Basics - Anfänger-Themen 17
volcanos Addition -> List<Integer> mit Arrays.asList() versus List<Integer>ArrayList<>() Java Basics - Anfänger-Themen 14
ArrayList mit unbekannter Menge an Arrays die Arrays vergleichen Java Basics - Anfänger-Themen 9
M 2d ArrayList durchgehen Java Basics - Anfänger-Themen 2
Blkckroll45 Arraylist Java Basics - Anfänger-Themen 6
H Interface Wieso "List<String> list = new ArrayList<>[…]" Java Basics - Anfänger-Themen 4
berserkerdq2 Geht collections.sort bei allen? Linkedhashset, ArrayList, HashSet etc. Java Basics - Anfänger-Themen 4
R Methoden Werte einer ArrayList als Parameter übergeben. Java Basics - Anfänger-Themen 4
L Dauerhaftes Speichern einer Eingabe bei einer ArrayList Java Basics - Anfänger-Themen 26
D Arraylist mit Komplexen Datentyp Java Basics - Anfänger-Themen 3
H Kompliziertes Sortieren einer ArrayList mit Objekten(Sortieren nach X und Y) Java Basics - Anfänger-Themen 11
T Permanentes speichern von Objekten in einer ArrayList Java Basics - Anfänger-Themen 6
volcanos List & ArrayList nach Familiennamen abfragen Java Basics - Anfänger-Themen 57
M static ArrayList in non-static Java Basics - Anfänger-Themen 12
berserkerdq2 Ich gebe eine ArrayList als List zurück per MEthode, wie kann ich nun aber die ArrayList speichern? Java Basics - Anfänger-Themen 46
M ArrayList<TreeNode<T>> fortlaufende Nummerierung der Elemente Java Basics - Anfänger-Themen 5
B Bungeecord | ProxiedPlayer wird nicht in ArrayList hinzugefügt Java Basics - Anfänger-Themen 1
S ArrayList Username und passwort mit JTextField eingaben abgleichen Java Basics - Anfänger-Themen 10
F Werte in einer Arraylist Zählen Java Basics - Anfänger-Themen 2
F Erste Schritte Zahlenreihe von Arraylist in 3erBlöcke sortiert in neue Arraylist Java Basics - Anfänger-Themen 2
M ArrayList mit einer Schleife befüllen Java Basics - Anfänger-Themen 2
F Methode ArrayList mit Eingabewert Java Basics - Anfänger-Themen 2
J ArrayList add methode selbst programmieren Java Basics - Anfänger-Themen 10
K Erste Schritte Wie schnell ist LinkedHashMap im Vergleich zur ArrayList, wenn alle Entries durchlaufen werden? Java Basics - Anfänger-Themen 47
thobren jtable arraylist Java Basics - Anfänger-Themen 12
N Exception beim Verwenden von Arraylist? Java Basics - Anfänger-Themen 10
P Schiebefix - ArrayList überschreibt Daten Java Basics - Anfänger-Themen 3
Zeppi OOP ArrayList Java Basics - Anfänger-Themen 2
P ArrayList Java Basics - Anfänger-Themen 4
L ArrayList auf 4 Elemente begrenzen Java Basics - Anfänger-Themen 56
C ArrayList sortieren nach bestimmten Buchstaben in den Wörtern Java Basics - Anfänger-Themen 13
S Arraylist<Object> mit verschiedenen Objects ausgeben Java Basics - Anfänger-Themen 3
J ArrayList auf bereits vorhanden eintrag prüfen Java Basics - Anfänger-Themen 5
M For Schleife/ArrayList Java Basics - Anfänger-Themen 12
L ArrayList<String> --> double[] array Java Basics - Anfänger-Themen 18
L Längstes Element einer ArrayList ausgeben Java Basics - Anfänger-Themen 9
S Aus verschachtelter ArrayList auf einen Wert zugreifen Java Basics - Anfänger-Themen 4
L Methoden ArrayList Werte hinzufügen und löschen Java Basics - Anfänger-Themen 32
M ArrayList in GUI ausgeben Java Basics - Anfänger-Themen 1
J Nur bestimmter Typ aus der ArrayList ausgeben. Java Basics - Anfänger-Themen 9
Bademeister007 Hallo Leute ich hab eine Frage zur ArrayList Java Basics - Anfänger-Themen 8
Bademeister007 Operatoren Alle Zahlen einer ArrayList die durch 5 teilbar ist Java Basics - Anfänger-Themen 2
S Objekt aus Arraylist in andere Arraylist kopieren? Java Basics - Anfänger-Themen 2
C Sortieren einer ArrayList Java Basics - Anfänger-Themen 2
krgewb ArrayList von ArrayList Java Basics - Anfänger-Themen 2
R ArrayList Problem Java Basics - Anfänger-Themen 6
jonny_2k12 Wie kann ich eine ArrayList aus einer Klasse in eine andere übergeben? Java Basics - Anfänger-Themen 21
O Namen (mit Umlauten und ß) in einer ArrayList suchen Java Basics - Anfänger-Themen 5
N Typebound Objekte einer Arraylist hinzufügen Java Basics - Anfänger-Themen 7
R Methoden ArrayList clonen wirft exception Java Basics - Anfänger-Themen 3
S ArrayList in andere Klasse übernhemen Java Basics - Anfänger-Themen 5
M Letztes Element einer ArrayList Java Basics - Anfänger-Themen 12
B Objektverwaltung mit ArrayList in einer seperaten Klasse Java Basics - Anfänger-Themen 24
I Sortiert eine HashMap nicht gleich wie eine ArrayList? Java Basics - Anfänger-Themen 1
I ArrayList erstellen innerhalb einer Zeile? Java Basics - Anfänger-Themen 3
L Iterieren durch eine ArrayList. Integer Array wird übergeben Java Basics - Anfänger-Themen 17
V Collections ArrayList mit Comparator sortieren Java Basics - Anfänger-Themen 16
D Collections Arrays in ArrayList abspeichern Java Basics - Anfänger-Themen 6
F java.util.ArrayList Java Basics - Anfänger-Themen 3
M ArrayList - Objekt kopieren und ändern Java Basics - Anfänger-Themen 11
M Zugriff auf eine ArrayList in einer anderen Klasse Java Basics - Anfänger-Themen 4
P Arraylist zu einem Array bringen mit Verschachtelung Java Basics - Anfänger-Themen 11
N Methode mit einer Arraylist Java Basics - Anfänger-Themen 106
I ArrayList - Methode zum Speichern eines Eintrags in einer Datei Java Basics - Anfänger-Themen 17
H ArrayList Java Basics - Anfänger-Themen 7
D public ArrayList(Collection<? extends E> c); Java Basics - Anfänger-Themen 2
M JTextField in ArrayList speichern Java Basics - Anfänger-Themen 4
C ArrayList mit return zurückgeben Java Basics - Anfänger-Themen 13
K Zahlenfolge ArrayList Java Basics - Anfänger-Themen 3
C Erste Schritte Frage zur ArrayList Java Basics - Anfänger-Themen 15
I Klassen Eine ArrayList<Long>, die sich automatisch sortiert Java Basics - Anfänger-Themen 20
F Array in ArrayList ablegen Java Basics - Anfänger-Themen 3
V ArrayList Java Basics - Anfänger-Themen 1
Z Runden Arraylist Java Basics - Anfänger-Themen 9
X Frage zur einer ArrayList in einer ArrayList Java Basics - Anfänger-Themen 5
F Arraylist als Pfadausgabe Java Basics - Anfänger-Themen 10
L Daten aus ArrayList in Datenbank durchsuchen Java Basics - Anfänger-Themen 5
L Objekt aus Textdatei in ArrayList speichern Java Basics - Anfänger-Themen 4
M Problem mit ArrayList Java Basics - Anfänger-Themen 32

Ähnliche Java Themen

Neue Themen


Oben