Multidesk.be » Forums » Java » Set versus List

  • Pagina
  • 1 van 1
0 gasten lezen dit onderwerp.
^ Onderwerp geschreven door een gast op maandag 27 april 2009 om 12:01:50.
wat is juist het verschil tussen een set een list?
een list heeft meer methodes?
en hoe zit het met de complexiteit? bv. contains
^ Reactie #1 geschreven door Martijn op maandag 27 april 2009 om 15:28:15.
Martijn heeft nog geen avatar toegevoegd
Multiviteit: 13785
Beheerder
Het belangrijkste verschil tussen beiden is dat een Set geen duplicaten (en slechts 1 keer null) bevat en dat een List gesorteerd is (dit laatste is bijvoorbeeld van belang wanneer je op een bepaalde index een bepaald element wil invoegen).

Wat bedoel je met het laatste?
Met vriendelijke groeten,
Martijn Wouters
^ Reactie #2 geschreven door NightCreature op maandag 27 april 2009 om 22:39:11.
NightCreature's avatar
Multiviteit: 1196
MSc.
Let op dat als er in een algoritme online over een list wordt gepraat deze meestal niet georderd zijn. Met een list in een algortime wordt vaak een dubbel linked list bedoelt of een single linkt list. Dit zijn iets andere data types dan de java list.
De java list is een implementatie van een ordered queue.
I need thought completion.
Shaders, een beetje vreemd maar wel lekker (voor de ogen dan he)
2.83Ghz Q9550 HD4850 512MiB 4GiB 1333Mhz DDR3 RAM
http://paulintheuk.blogspot.com
FE Programmer @ Codemasters (Front End)
^ Reactie #3 geschreven door een gast op donderdag 30 april 2009 om 10:04:19.
Dus een ArrayList is een gesorteerde lijst?
Wat bedoel je daar precies mee?
Stel je hebt:
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(3);
list.add(5);
list.add(2);

is dat dan: [2,3,5] ?

over de complexiteit:
Wat is de tijdcomplexiteit van een contains op een Set en een contains op een ArrayList?
list.contains(someElement)
-> wat is de complexiteit als list een ArrayList/Set (TreeSet of HashSet, verschilt dat?) is van lengte n?
-> O(n) of O(log n) of .. ?
^ Reactie #4 geschreven door een gast op donderdag 30 april 2009 om 10:05:08.
die O(n) is dus O( n )
^ Reactie #5 geschreven door NightCreature op donderdag 30 april 2009 om 19:47:59.
NightCreature's avatar
Multiviteit: 1196
MSc.
Dat hoeft niet aangezien het een gesorteerde lijst is zal O waarschijnlijk log( n ) zijn. Binary search en waarschijnlijk als de lijst groot wordt zal er quicksort worden gebruikt dan is het n log( n )
Deze tekst werd het laatst bewerkt voor 1 % door NightCreature op donderdag 30 april 2009 om 19:49:01.
I need thought completion.
Shaders, een beetje vreemd maar wel lekker (voor de ogen dan he)
2.83Ghz Q9550 HD4850 512MiB 4GiB 1333Mhz DDR3 RAM
http://paulintheuk.blogspot.com
FE Programmer @ Codemasters (Front End)
^ Reactie #6 geschreven door een gast op vrijdag 1 mei 2009 om 09:32:29.
in het voorbeeld hierboven:
wat krijg je als je list.get(2); doet?

dus een arraylist is beter dan een set als je die veel moet 'raadplegen' ?

^ Reactie #7 geschreven door NightCreature op vrijdag 1 mei 2009 om 10:23:50.
NightCreature's avatar
Multiviteit: 1196
MSc.
Een O( n ) implementatie kan ik me niet voorstellen voor een list omdat je dan een bubble sort aan het doen bent en we allemaal weten dat bubblesort == EVIL.
I need thought completion.
Shaders, een beetje vreemd maar wel lekker (voor de ogen dan he)
2.83Ghz Q9550 HD4850 512MiB 4GiB 1333Mhz DDR3 RAM
http://paulintheuk.blogspot.com
FE Programmer @ Codemasters (Front End)
^ Reactie #8 geschreven door een gast op zondag 3 mei 2009 om 16:31:38.
maar wat is nu de beste datastructuur?

ik heb bv een bestand dat ik wil omvormen naar een list/set of iets dergelijks
het enige wat ik met die list/set moet doen is kijken of er een bepaalde string in voorkomt (dus enkel een contains())

als het bestand niet 2 keer dezelfde string bevat, biedt een set dan geen voordeel boven een list?

en jullie zeggen dat een list gesorteerd is, dus dan zijn de strings uit het bestand gesorteerd?
  • Pagina
  • 1 van 1

Snel-antwoordformulier
Toon uitgebreid antwoordformulier Bericht nalezen Bericht plaatsen