Subscribe to JVM Technologies Blog        RSS Feed
***** 1 Votes

An Overview of the Java Collections Framework

Icon Leave Comment
Java Collections Framework Entry

In this entry, we will examine the Java Collections Framework. We will be discussing the basic data structures, and how many of them are implemented in the Java libray. The basic data structures we will examine include lists, stacks, queues, sets, maps, heaps, graphs, and trees.

Lists
Lists are basic and standard data structures in computer science, and theoretically are the supertype data structure for a number of other structures including stacks, queues, and deques. The basic List data structures in the Java Collections Framework include the ArrayList, Vector, and LinkedList classes, all of which implement the List interface. The ArrayList and Vector classes both manage arrays internally to allow for dynamic resizing and inserting elements into the middle of the List. The difference between the two is that Vector is synchronized, allowing Threads to safely modify its elements. This, however, causes Vector's operations to run slower than ArrayLists.

The LinkedList class is an alternative to ArrayList and Vector. Rather than using arrays internally, the LinkedList class manages Nodes that point to each other in a linear manner, thus the name "Linked" List. Because of this Node-based structure, LinkedLists are well-suited for tasks where elements are prepended to it or appended to it. Unlike ArrayList and Vector, LinkedList doesn't allow for O(1) random access to its elements. The LinkedList class also implements the Queue interface, allowing developers to easily utilize a FIFO structure.

The Stack class is another commonly used List data structure for ordering elements in FIFO ordering. While one may initially think that the Stack class is LinkedList based due to LinkedList's design in adding and removing elements from the ends. However, the Stack class is based off of the Vector class. It is actually more efficient to double the size of the array being managed every so often than to deal with the constant creation and removal of linked Nodes. The drawback with the Stack extending Vector is the synchronization, which slows down its operations.

The last major List data structures is a Deque, or a Double-Ended Queue. Deques are used when storing and removing data exclusively at the front and end of the structure. There is no random access in the middle of the structure. For the same reason as with the Stack class, the Deque structure is implemented using an array. However, the ArrayDeque class does not extend Vector.

Sets and Maps
Sets and Maps are important data structures in computer science. Sets store only unique elements, and Maps relate unique keys to corresponding value pairs. In the Java collections framework, the Map interface extends the Set interface, and their concrete implementations correspond very closely.

The most commonly used implementations of the Map and Set interfaces are the HashMap and HashSet classes. The Hash implementation utilizes a one-way hash function to place elements. It doesn't guarantee any form of ordering, but it does allow for O(k) runtime for adding, removing, searching, and size() functionalities. HashMaps are backed using arrays, and HashSets are backed with a HasMap.

The LinkedHashSet and LinkedHashMap classes extend the HashSet and HashMap classes respectively, and are where ordering starts to take place. The LinkedHashSet and LinkedHashMap classes use a doubly-linked list to manage elements, as well as take advantage of the array-based hash management, allowing for the best of both worlds.

The TreeSet and TreeMap classes order elements in sorted order. They implement the NavigableSet and NavigableMap interfaces respectively. TreeSet and TreeMap also guarantee O(log(n)) for the add() (TreeSet only), remove() (TreeSet only), contains(), getKey() (TreeMap only), and put() (TreeMap only) methods. The TreeMap class is based off a Red-Black tree, and the TreeSet class is backed by a TreeMap.

The last important Map in the Java Collections Framework to be examined is a WeakHashMap. The WeakHashMap class allows for weak references of the keys. This means that they are eagerly removed by the garbage collector as soon as they have no strong references. It is a good tool for caching elements, but be wary about checking to make sure if a key exists in the Map before obtaining its value.

Heaps, Graphs, and Trees
The Java Collections Framework dose not formally support Heaps, Graphs, and Trees that the developers can interact with (even though the TreeMap class is implemented with a Red-Black Tree). However, we don't have to look far for a Tree we can interact with on a Node-based level. The javax.swing.JTree serves a purpose for more than just a GUI Display. It is quite simple to take advantage of the TreeNodes it uses to organize a Tree structure. The standard Node class to examine is the DefaultMutableTreeNode, which stores an Object, as well as references to children Nodes, just like one would expect from a Tree structure.

Final Note
While there are many more Collections and data structures in the JDK, these are the predominant ones associated with the Java Collections Framework. Many of the other Collections are part of other frameworks, specifically the concurrency API. These structures will be more closely examined in future entries on those specific APIs.

0 Comments On This Entry

 

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

September 2014

S M T W T F S
 123456
78910111213
14151617181920
2122 23 24252627
282930    

Recent Entries

Recent Comments

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)