Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > de.comp.lang.java > #12950
| From | Wanja Gayk <brixomatic@yahoo.com> |
|---|---|
| Newsgroups | de.comp.lang.java |
| Subject | Re: Rekursion bricht nicht ab |
| Date | 2016-04-23 16:13 +0200 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <MPG.318596afa70f02789896b2@news.aioe.org> (permalink) |
| References | (2 earlier) <dmv3g8Fngq5U2@mid.individual.net> <dmv77lFoggiU1@mid.individual.net> <dmvd9oFq327U1@mid.individual.net> <MPG.31789f5985a68ae9896b0@news.aioe.org> <dn7mkmFu468U1@mid.individual.net> |
In article <dn7mkmFu468U1@mid.individual.net>, Christian H. Kuhn (qno-
news@qno.de) says...
> Die
> ArrayList<>s habe ich aufgrund deines Posts mal mit LinkedList<>s
> ersetzt, weil ich tatsächlich hauptsächlich durchiteriere und nur
> gelegentlichst mal auf eine Index-Position zugreife.
Dazu muss ich vielleicht etwas erklären:
Ein stumpfes list.remove(x) ist bei ArrayList und LinkedList etwa gleich
schnell - die eine verschwendet die Zeit beim Zugriff auf den Index, die
andere beim Kopieren der restlichen Elemente "nach links" um die Lücke
am gelöschten Index zu entfernen.
Bei einer LinkedList wird beim Löschen lediglich das nächste Objekt an
das vorherige geknüpft und das aktuelle Objekt ist damit nicht mehr
referenziert), während das Löschen aus einer ArrqaList bedeutet, dass
alle folgenden Positionen eine Position "nach links" kopiert werden
müssen. Dafpr muss die LinkesList der Kette ablaufen, bis es am
jeweiligen index ist.
Der Vorteil der LinkedList stellt sich also nur in einer recht
speziellen Situation ein, nämlich wenn du während des Iterierens löscht.
Iterator<X> it = arrayList.iterator();
while(it.hasNext()){ O(n)
if(canBeUsed(x)){
use(x);
}
if(mustBeDeleted(x)){
it.remove(); //ist O(n) für ArrayList
}
}
Iterator<X> it = linkedList.iterator();
while(it.hasNext()){ /O(n)
if(canBeUsed(x)){
use(x);
}
if(mustBeDeleted(x)){
it.remove(); //ist O(1) für LinkedList
}
}
Hier hat die ArrayList O(n*n) und die LinkedList O(n).
Gruß,
-Wanja-
--
..Alesi's problem was that the back of the car was jumping up and down
dangerously - and I can assure you from having been teammate to
Jean Alesi and knowing what kind of cars that he can pull up with,
when Jean Alesi says that a car is dangerous - it is. [Jonathan Palmer]
Back to de.comp.lang.java | Previous | Next — Previous in thread | Next in thread | Find similar
Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-08 23:28 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-09 16:13 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:41 +0200
Re: Rekursion bricht nicht ab Peter Büttner <not_for_mail_peb@gmx.net> - 2016-04-10 16:45 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 18:28 +0200
Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-13 19:25 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 21:56 +0200
Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 17:31 +0200
Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:53 +0200
Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:56 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 19:22 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 00:42 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 09:20 +0200
Re: Rekursion bricht nicht ab Christoph Schneegans <Christoph@Schneegans.de> - 2016-04-14 18:47 +0200
Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:07 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 17:38 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 22:36 +0200
Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-28 08:26 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-10 22:15 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:46 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:32 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 20:44 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-14 12:07 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-23 13:35 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 14:57 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 23:05 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-26 01:16 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 16:05 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:48 +0200
Re: Rekursion bricht nicht ab v_borchert@despammed.com (Volker Borchert) - 2016-04-10 06:07 +0000
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:40 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-11 11:21 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:57 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:28 +0200
Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 23:36 +0200
Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 21:42 +0200
csiph-web