hello,
i was wondering which java native datastructure is suitable for the implementation of a 3D scenegraph? probably something tree-like.
any suggestions? 
thanks!
Neither IMO.
Sure you can implement a tree using arrays as nodes, but I’ve only seen that used as a performance enhancement and nothing else.
Best bet is to write your own.
There’s no reason why you couldn’t use a linked list, however when it comes to performance of iterating through the tree you can do better, that’s why Java’s collection framework has the ability to be extended.
http://java.sun.com/docs/books/tutorial/collections/custom-implementations/index.html
[quote]High-performance, special-purpose: Many data structures take advantage of restricted usage to offer better performance than is possible with general-purpose implementations. For instance, consider a List containing long runs of identical element values. Such lists, which occur frequently in text processing, can be run-length encoded — runs can be represented as a single object containing the repeated element and the number of consecutive repetitions. This example is interesting because it trades off two aspects of performance: It requires less space but more time than an ArrayList.
[/quote]
ok thanks.
i am using linkedlist now. is that a fast structure to iterate through?
It’s fast but not the fastest, then again adding/removing from a LinkedList is fastest however iterating isn’t the fastest.
If performance becomes a concern then you should write your own data structure.
thanks,
another question: what is a fast algorithm to sort a linked list? i tried quicksort, but it is terribly slowing down the rendering.
even if the list is sorted already.
Sorting an already-sorted list is a pathological O(n2) case for the simplest implementation of quicksort.
Using a randomised quicksort should avoid this behaviour.
Or you could use the mergesort that’s implemented in java.util.Collections.sort().