Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (487)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (553)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  Java Data structures  (Read 24434 times)
0 Members and 1 Guest are viewing this topic.
Offline Wiki Duke

?





« Posted 2012-07-24 07:08:26 »

General data structure types and interfaces



  • Collection General bag of stuff. Lets you add, remove and iterate when you don't really care what the underlying structure is.
  • List Ordered list of stuff. Use when you want objects kept in order, but you don't care what the underlying structure is.
  • Set. A collection that does not allow duplicates. Use when having the same object twice in your collection is an error.
  • Map. Map of key-value pairs. Use when you want fast lookups from some kind of identifying key to another object.

Lists & queues


  • ArrayList Growable list, implemented with an array that is resized under the hood.
  • LinkedList Doubly linked list. Faster insertion and removal than an ArrayList, but slower to iterate over.
  • PriorityQueue Ordered list where objects are sorted by a priority value.
  • Unrolled linked list




Lookup tables






Ordered collections



Thread-safe collections


Most containers can be wrapped to create thread safe versions using the methods in Collections. Eg. Collections.synchronizedList(new ArrayList<Type>()) More specialised containers can be found in java.util.concurrent.

  • ConcurrentHashMap. Map with non-blocking get(), useful for caches which may be populated from a loader thread.
  • ConcurrentLinkedQueue. Non-blocking queue, useful for multithreaded pipelines where producers and consumers may share a common queue.





General Advice



  • Always declare using the most general type you need.  This isn't so important for locals, but it makes a huge difference for fields, as this allows you to swap the implementation of a datastructure without breaking code, that may otherwise already have dependencies on the explicitly defined implementation. For example:
1  
2  
3  
4  
5  
6  
7  
// Don't do this!
ArrayList<Foo> foos = new ArrayList<Foo>();
HashMap<Foo,Bar> foobar = new HashMap<Foo,Bar>();

// Do this instead
List<Foo> foos = new ArrayList<Foo>();
Map<Foo,Bar> foobar = new HashMap<Foo,Bar>();    



References


  • Interactive applet. Visualization tool that walks through the steps of: BST, AVL, B-tree, AA Tree, Red Black, Skiplist, Max & Min Heap, Treap, Scapegoat and Splay.
This wiki entry has had 21 revisions with contributions from 9 members. (more info)
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #1 - Posted 2012-07-25 14:32:47 »

I think we should define each list. What exactly is an "ordered collection"'? Doesn't that apply to most of the collections?


Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2012-07-25 14:37:51 »

Click on the links in the article for more information persecutioncomplex

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #3 - Posted 2012-07-25 18:35:04 »

Just like that?

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #4 - Posted 2012-07-25 18:44:54 »

I added HashMap because I use it a lot, and it's an awesome collection. Does anyone know what it's based on though? I'm not sure there's an actual array involved, even though that's what it's mimicking.

Offline theagentd
« Reply #5 - Posted 2012-07-25 18:49:54 »

I added HashMap because I use it a lot, and it's an awesome collection. Does anyone know what it's based on though? I'm not sure there's an actual array involved, even though that's what it's mimicking.
I think it's based on an array of linked lists. I wouldn't say it's an awesome collection though. It simply allows you to attach a field to an object without making a field. There's a better way of doing that: with fields... >_>

Myomyomyo.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2012-07-25 19:10:49 »

HashMaps are indeed an array of LinkedLists, with an important detail: every time you access a value, it becomes the head of the linked list.


It simply allows you to attach a field to an object without making a field. There's a better way of doing that: with fields... >_>
Luckily that's not what it's typically used for. Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #7 - Posted 2012-07-25 19:16:25 »

every time you access a value, it becomes the head of the linked list.

Then it'll be slower the more bindings, right? Undecided

I wouldn't say it's an awesome collection though. It simply allows you to attach a field to an object without making a field. There's a better way of doing that: with fields... >_>

Sometimes it's nice to index a list by something other than integers. Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2012-07-25 19:18:24 »

I advice you to read the links you posted yourself. And no, it wouldn't become slower, the array of the hashmap grows to keep the number of elements in the linkedlists low. And indexing a list by anything else than an integer is a horrible abuse of a (hash)map.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #9 - Posted 2012-07-25 19:20:18 »

Hey riven!
What about adding something like a commit message to the wiki thingie.
So you could add some message like "removed strange [/i] in line 2" Wink

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #10 - Posted 2012-07-25 19:23:08 »

For a nice example of what to use a (hash)map for:

   http://pastebin.java-gaming.org/5f59f487d1b

It makes a deep-copy of a (circular!) graph.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline theagentd
« Reply #11 - Posted 2012-07-25 19:29:44 »

For a nice example of what to use a (hash)map for:

   http://pastebin.java-gaming.org/5f59f487d1b

It makes a deep-copy of a (circular!) graph.
I just took a two-second glance at it, but why not just have a field called "old" in Node?

Myomyomyo.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2012-07-25 19:31:37 »

I just took a two-second glance at it, but why not just have a field called "old" in Node?
Why would I litter my classes with unused fields, only for some situation that I might want to make a deep copy?

Besides that doesn't solve anything, because I still have to create all the connections (edges) between the nodes and end up with a properly connected graph.

Would you suggest I'd also add an 'old' field to the Edge class? And how would I connect it all again? Iterating all possible edges everything I need to find a match? I can see the required code explosion and severely degraded performance already. This is exactly what mappings are supposed to do for you!

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #13 - Posted 2012-07-25 19:36:16 »

Hashing is unordered.  Trees are ordered.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #14 - Posted 2012-07-25 19:41:11 »

I advice you to read the links you posted yourself.

I believe I have. The documentation page for the class doesn't offer a lot of insight into it's implementation other than "Hash table implementation of Map", which is just as good as "array-voodoo" to me. Wikipedia doesn't seem to have a much more understandable version of this. I know its speed for basic operations is described, but "constant-time performance" and "LinkedList" don't fit too well with eachother in my head.

Indexing a list by anything else than an integer is a horrible abuse of a (hash)map.

I didn't mean a literal list. I agree that lists work best with integers for positions, but what if my list goes [1, 5, 12, 2, 66, 21, 14078]. You can sort that how you want, but there will always be that big hole of nulls. I would think that pairing up the integers to their respective objects would be easier than having a few thousand nulls in a huge array.

How about this: I like to load all my resources once, and then just refer to them with an Enum. For instance, 10k spaceships don't all need the same little icon in the instance. They all just have the enum-reference, and then I can statically grab the image if it needs to be drawn. The same goes for animations that're all the same.

In this case it's just easier to have an Image-enum representing all available images, than having to look up on a huge list what index in the array each Image is located at.

Offline theagentd
« Reply #15 - Posted 2012-07-25 19:44:41 »

@Riven
Oh! The nodes and the edges may be shared! Yeah, I guess that is a perfect example of using a HashTable! Will use that example in the future (unless you've patented it xD)!

Myomyomyo.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #16 - Posted 2012-07-25 19:52:13 »

This usage of mapping is way too complex to patent! My 'nullify references to aid the garbage collector' patent is pending though, although these days it's rather counter productive to nullify anything, as all data must be retained for 18 months.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline sproingie

JGO Kernel


Medals: 202



« Reply #17 - Posted 2012-07-25 20:13:47 »

The linked lists for HashMap only come into play when there's a collision.  Most of the time, the number of collisions is very low, so you're never chasing down the chain.

I'm actually kind of amazed that HashMap doesn't use open addressing.  Buckets?  Really?  That's like Baby's First Data Structure.


Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #18 - Posted 2012-07-26 08:26:42 »

HashMaps are indeed an array of LinkedLists, with an important detail: every time you access a value, it becomes the head of the linked list.

I think only a LinkedHashMap does this, no?

Offline UprightPath
« Reply #19 - Posted 2012-07-26 08:39:49 »

No. The LinkedHashMap allows you to have an ordered Iterator (FIFO) method.

Normally, the iterator for a HashMap will be based on bucket order (I think). Meaning that whatever the internal data-structure holding the values stores them. Heh.

Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #20 - Posted 2012-07-26 08:59:56 »

No. The LinkedHashMap allows you to have an ordered Iterator (FIFO) method.

Well yes, LinkedHashMap has a special constructor which allows the 'move-the-last-accessed-entry-to-the-front' behaviour which Riven described, which you use for implementing a simple LRU.
Look at LinkedHashMap.Entry.recordAccess() where this is implemented.
I don't think this sort of behaviour exists in a normal HashMap.

Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #21 - Posted 2012-07-26 09:20:03 »

sproingi, that advice is right, exept for ArrayLists imo.
You often need ArrayList.trimToSize(), which trims the array to it's size. For example if you have a method putting (not-knowing how much) elements into an ArrayList, and then never or not often changes it again, you could use .trimToSize() to reduce memory usage.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline sproingie

JGO Kernel


Medals: 202



« Reply #22 - Posted 2012-07-26 14:57:35 »

I think my advice is right 99% of the time for ArrayLists too, but obviously if you need the functionality of a specific type, you use the specific type.  If you're never going to change the size of an ArrayList, then you should set the size in the constructor and it will only allocate that many elements.

In fact the advice gets even more general for methods.  If you have a method that takes an ArrayList<Foo> and does nothing but loop over it, it should take an Iterable<Foo> instead.  I don't get that abstract with publicly-readable fields for obvious reasons though.

Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #23 - Posted 2012-07-26 18:17:26 »

I think my advice is right 99% of the time for ArrayLists too, but obviously if you need the functionality of a specific type, you use the specific type.  If you're never going to change the size of an ArrayList, then you should set the size in the constructor and it will only allocate that many elements.

In fact the advice gets even more general for methods.  If you have a method that takes an ArrayList<Foo> and does nothing but loop over it, it should take an Iterable<Foo> instead.  I don't get that abstract with publicly-readable fields for obvious reasons though.

Consider the following scenario:

You have a directory and you want to search all the files inside them recursively, and add then to an ArrayList.
You can't set the size in the constructor, since you don't know the size.
You can only trim it to size after you have found all the Files.

The thing you could do is return a simple List<File> of Files in the end after you got all the Files... Little src code to make it clear:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
public static List<File> getFilesFromDir(File directory) {
    // Check for "directory" being a directory:
   if (!directory.isDirectory()) {
        throw new IllegalArgumentException(directory.isDirectory() == false);
    }
    // Create new ArrayList, keep it as ArrayList, to call .trimToSize(); later:
   ArrayList<File> files = new ArrayList<File>();
    // Add the files recursively:
   getFilesRecursive(directory, files);
    files.trimToSize();
    return files;
}

private static void getFilesRecursive(File dir, ArrayList<File> list) {
    // For each File in the directory "dir":
   for (File file : dir.listFiles()) {
        // If it's a Directory, call this method with the File "file" as directory:
       if (file.isDirectory()) {
            getFilesRecursive(file, list);
        } else { // Else add it to found files, since it is a file, not directory:
           list.add(file);
        }
    }
}

(fast-typed, not syntax-tested)

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline sproingie

JGO Kernel


Medals: 202



« Reply #24 - Posted 2012-07-26 20:43:17 »

Sure, using the ArrayList implementation internally in the local and returning the abstract List is 100% legit.  It's hard to boil that down to one-liner advice of course, but those declarations are also perfectly good field declarations too.
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #25 - Posted 2012-07-26 20:51:03 »

you could do something like this : Cheesy
1  
2  
3  
4  
5  
6  
7  
8  
public List<Foo> get() {
    // Create ArrayList, and internally keep it as ArrayList
   ArrayList<Foo> list = new ArrayList<Foo>();
    // Do stuff with the ArrayList
   //...
   // return it as List<Foo>!
   return list;
}

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Icecore

Senior Member


Medals: 5



« Reply #26 - Posted 2012-07-31 20:07:51 »

What about Vector http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Vector.html
Data structures for using in multi thread.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #27 - Posted 2012-07-31 20:09:29 »

I'd like to remind everybody that this is a wiki page.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #28 - Posted 2012-07-31 20:28:48 »

Can someone please explain the differenct between a Vector and a ArrayList in java? I've never used a Vector.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Icecore

Senior Member


Medals: 5



« Reply #29 - Posted 2012-07-31 21:12:04 »

Can someone please explain the differenct between a Vector and a ArrayList in java? I've never used a Vector.
Vector is synchronized
they work slower then ArrayList, but you can use them in 2 and more Thread at once.
(you can’t use ArrayList more then one Thread in one time, that’s call errors)

Simple example

ArrayList X
X have 5 elements
Thread 1 – remove last element
Thread 2 – add element to end
Can be situation when you receive:
Element 5 = null (because Thread 1 remove it ^^)
Before (1,2,3,4,5)
After (1,2,3,4,null,6)
or (1,2,3,4,null)

P.s Sorry don’t want modify first post , fear can write something not right on English Wink
Pages: [1] 2
  ignore  |  Print  
 
 

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CopyableCougar4 (23 views)
2014-08-22 19:31:30

atombrot (34 views)
2014-08-19 09:29:53

Tekkerue (30 views)
2014-08-16 06:45:27

Tekkerue (28 views)
2014-08-16 06:22:17

Tekkerue (18 views)
2014-08-16 06:20:21

Tekkerue (27 views)
2014-08-16 06:12:11

Rayexar (65 views)
2014-08-11 02:49:23

BurntPizza (41 views)
2014-08-09 21:09:32

BurntPizza (32 views)
2014-08-08 02:01:56

Norakomi (42 views)
2014-08-06 19:49:38
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!