5 replies to this topic

[An Alien]

I think the closest thing I've done to data structures would be arrays. I've looked at arraylists before and know that they are more flexibile than arrays, but that's about all I know. I'm looking for someone give me a little intro to data structures and the benefits of using them.

[lethalwire]

Data structures are used to help you organize and store data.
There are certain basics data structures like linked list, array lists, queues, stacks, maps, etc.
As you have had some practice with ArrayLists, you'll see you can easily add/remove/insert/get data from an ArrayList. Arraylists, like primitive arrays are of a fixed sized, unless manually resized.
With a LinkedList, order isn't important and space is relatively unimportant also. LinkedLists are not of a fixed size because they reference other objects in memory.
Queues are a first in, first out(FIFO) data structure. The first one in, is the first one out! Something similar to a hot dog stand: The first person in line gets served first, 2nd person gets served 2nd etc.
A stack is a last in, first out(LIFO) data structure. This is the exact opposite of a queue. Just imagine stacking books into a box. You put in 3 books A first, B second, C third. If you want book A, you'll need to remove books C and B to get to A.
Maps are like reference tables. You can map values to keys. For instance the Key A might hold value 97, Key B holds value 98, c holds 99... etc. So if you want the value of B, you lookup B and retrieve the value of 98.

There are quite a few tutorials online about all of the datas tructures. Even more tutorials can be found about the implementation of these data structures.

[fread]

A more comprehensive guide maybe found in a text. A good text will cover enough for a beginner with a sufficient amount of examples and exercises to challenge yourself at the end of each chapter.

[An Alien]

Thanks Lethal for the examples. I am actually going to look for some more advanced programming books instead of the just basics ones that I've been reading now. Do you know anything about sets? Like Hashset. I know hash ID is a unique ID given to each object from the JVM behind the scenes..I think. But I then what are sets?

[lethalwire]

A set is a list of unique items. A treeset is a sorted list of unique items.

[wim DC]

Quote

Like Hashset. I know hash ID is a unique ID given to each object from the JVM behind the scenes..I think.

That's not quite true, you can override the hashCode method and you can end up with non-unique hashcodes / object.

@Override
    public int hashCode()
    {
        return super.hashCode();    
    }

The HashSet will still use the equals(..) method to check for unique objects. The hash is only used for performance of the set.
Say you have a 1000 objects in a set with unique IDs of 1 to 1000, and you write the hash as such that objects 1-199 returns 1, 200-299 returns 2, 300-399 returns 3, etc..
then, when you're searching in the hashSet for object 456, it knows, oh that's hash 4 so that'll be over there. And it can basically skip 900 objects to look trough.

HashCode rules:
if(x.equals(y) ) ---> x.hashCode == y.hashCode
if( x.hashCode == y.hashCode ) ---> x CAN be equal to y, but doesn't has to.

JavaDoc:

Quote

public int hashCode()
Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

And as far as Sets go:
"Set" just means unique collection (based on the .equals(..) method). What type of Set will only change how it's stored and behaves.
HashSet --> fastest
LinkedHashSet --> also fast, but iterating over the elements will always occur in the same order (unlike the normal HashSet)
TreeSet --> like, Lethalwire said, is a sorted set. Adding the following numbers in this order: 5, 3,4,1,2 will come out as 1,2,3,4,5