HOME

TheInfoList



OR:

The
Java Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's most ...
collections framework is a set of classes and interfaces that implement commonly reusable collection
data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s. Although referred to as a framework, it works in a manner of a
library A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
. The collections framework provides both interfaces that define various collections and classes that implement them.


Differences from Arrays

Collections and arrays are similar in that they both hold references to objects and they can be managed as a group. However, unlike arrays, collections do not need to be assigned a certain capacity when instantiated. Collections can also grow and shrink in size automatically when objects are added or removed. Collections cannot hold basic data type elements (primitive types) such as int, long, or double; instead, they hold Wrapper Classes such as Integer, Long, or Double.


History

Collection implementations in pre- JDK 1.2 versions of the Java platform included few data structure classes, but did not contain a collections framework. The standard methods for grouping Java objects were via the array, the Vector, and the Hashtable classes, which unfortunately were not easy to extend, and did not implement a standard member interface. To address the need for reusable collection
data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s, several independent frameworks were developed, the most used being
Doug Lea Douglas S. Lea is a professor of computer science and current head of the computer science department at State University of New York at Oswego, where he specializes in concurrent programming and the design of concurrent data structures. He was ...
's ''Collections package'', and ObjectSpace ''Generic Collection Library'' (JGL), whose main goal was consistency with the
C++ C, or c, is the third letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''cee'' (pronounced ), plural ''cees''. History "C" ...
Standard Template Library The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called '' algorithms'', '' ...
(STL). The collections framework was designed and developed primarily by
Joshua Bloch Joshua J. Bloch (born August 28, 1961) is an American software engineer and a technology author, formerly employed at Sun Microsystems and Google. He led the design and implementation of numerous Java platform features, including the Java Col ...
, and was introduced in JDK 1.2. It reused many ideas and classes from Doug Lea's ''Collections package'', which was deprecated as a result.
Sun Microsystems Sun Microsystems, Inc. (Sun for short) was an American technology company that sold computers, computer components, software, and information technology services and created the Java programming language, the Solaris operating system, ZFS, th ...
chose not to use the ideas of JGL, because they wanted a compact framework, and consistency with C++ was not one of their goals. Doug Lea later developed a
concurrency Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to: Law * Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea'' * Concurring opinion (also called a "concurrence"), a ...
package, comprising new Collection-related classes. An updated version of these concurrency utilities was included in JDK 5.0 as of JSR 166.


Architecture

Almost all collections in Java are derived from the java.util.Collection interface. Collection defines the basic parts of all collections. The interface states the add() and remove() methods for adding to and removing from a collection respectively. Also required is the toArray() method, which converts the collection into a simple array of all the elements in the collection. Finally, the contains() method checks if a specified element is in the collection. The Collection interface is a subinterface of java.lang.Iterable, so any Collection may be the target of a for-each statement. (The Iterable interface provides the iterator() method used by for-each statements.) All collections have an iterator that goes through all of the elements in the collection. Additionally, Collection is a generic. Any collection can be written to store any class. For example, can hold strings, and the elements from the collection can be used as strings without any casting required. Note that the angled brackets can hold a type argument that specifies which type the collection holds.


Three Types of Collection

There are three generic types of collection: ordered lists, dictionaries/maps, and sets. Ordered lists allows the programmer to insert items in a certain order and retrieve those items in the same order. An example is a waiting list. The base interfaces for ordered lists are called List and Queue. Dictionaries/Maps store references to objects with a lookup key to access the object's values. One example of a key is an identification card. The base interface for dictionaries/maps is called Map. Sets are unordered collections that can be iterated and contain each element at most once. The base interface for sets is called Set.


List interface

Lists are implemented in the collections framework via the java.util.List interface. It defines a list as essentially a more flexible version of an array. Elements have a specific order, and duplicate elements are allowed. Elements can be placed in a specific position. They can also be searched for within the list. Two examples for concrete classes that implement List are: *java.util.ArrayList, which implements the list as an array. Whenever functions specific to a list are required, the class moves the elements around within the array in order to do it. *java.util.LinkedList. This class stores the elements in nodes that each have a pointer to the previous and next nodes in the list. The list can be traversed by following the pointers, and elements can be added or removed simply by changing the pointers around to place the node in its proper place.


Stack class

Stacks are created using java.util.Stack. The stack offers methods to put a new object on the stack (method push()) and to get objects from the stack (method pop()). A stack returns the object according to last-in-first-out (LIFO), e.g. the object which was placed latest on the stack is returned first. java.util.Stack is a standard implementation of a stack provided by Java. The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class java.util.Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top. When a stack is first created, it contains no items.


Queue interfaces

The java.util.Queue interface defines the queue data structure, which stores elements in the order in which they are inserted. New additions go to the end of the line, and elements are removed from the front. It creates a first-in first-out system. This interface is implemented by java.util.LinkedList, java.util.ArrayDeque, and java.util.PriorityQueue. LinkedList, of course, also implements the List interface and can also be used as one. But it also has the Queue methods. ArrayDeque implements the queue as an array. Both LinkedList and ArrayDeque also implement the java.util.Deque interface, giving it more flexibility. java.util.Queue can be used more flexibly with its subinterface, java.util.concurrent.BlockingQueue. The BlockingQueue interface works like a regular queue, but additions to and removals from the queue are blocking. If remove is called on an empty queue, it can be set to wait either a specified time or indefinitely for an item to appear in the queue. Similarly, adding an item is subject to an optional capacity restriction on the queue, and the method can wait for space to become available in the queue before returning. java.util.PriorityQueue implements java.util.Queue, but also alters it. Instead of elements being ordered in the order in which they are inserted, they are ordered by priority. The method used to determine priority is either the compareTo() method in the elements or a method given in the constructor. The class creates this by using a heap to keep the items sorted.


Double-ended queue (deque) interfaces

The java.util.Queue interface is expanded by the java.util.Deque subinterface. Deque creates a double-ended queue. While a regular queue only allows insertions at the rear and removals at the front, the deque allows insertions or removals to take place both at the front and the back. A deque is like a queue that can be used forwards or backwards, or both at once. Additionally, both a forwards and a backwards iterator can be generated. The Deque interface is implemented by java.util.ArrayDeque and java.util.LinkedList. The java.util.concurrent.BlockingDeque interface works similarly to java.util.concurrent.BlockingQueue. The same methods for insertion and removal with time limits for waiting for the insertion or removal to become possible are provided. However, the interface also provides the flexibility of a deque. Insertions and removals can take place at both ends. The blocking function is combined with the deque function.


Set interfaces

Java's java.util.Set interface defines the set. A set can't have any duplicate elements in it. Additionally, the set has no set order. As such, elements can't be found by index. Set is implemented by java.util.HashSet, java.util.LinkedHashSet, and java.util.TreeSet. HashSet uses a hash table. More specifically, it uses a java.util.HashMap to store the hashes and elements and to prevent duplicates. java.util.LinkedHashSet extends this by creating a doubly linked list that links all of the elements by their insertion order. This ensures that the iteration order over the set is predictable. java.util.TreeSet uses a
red–black tree In computer science, a red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions. When th ...
implemented by a java.util.TreeMap. The red–black tree makes sure that there are no duplicates. Additionally, it allows TreeSet to implement java.util.SortedSet. The java.util.Set interface is extended by the java.util.SortedSet interface. Unlike a regular set, the elements in a sorted set are sorted, either by the element's compareTo() method, or a method provided to the constructor of the sorted set. The first and last elements of the sorted set can be retrieved, and subsets can be created via minimum and maximum values, as well as beginning or ending at the beginning or ending of the sorted set. The SortedSet interface is implemented by java.util.TreeSet. java.util.SortedSet is extended further via the java.util.NavigableSet interface. It's similar to SortedSet, but there are a few additional methods. The floor(), ceiling(), lower(), and higher() methods find an element in the set that's close to the parameter. Additionally, a descending iterator over the items in the set is provided. As with SortedSet, java.util.TreeSet implements NavigableSet.


Map interfaces

Maps are defined by the java.util.Map interface in Java. Maps are simple data structures that associate a key with an element. This lets the map be very flexible. If the key is the hash code of the element, the map is essentially a set. If it's just an increasing number, it becomes a list. Maps are implemented by java.util.HashMap, java.util.LinkedHashMap, and java.util.TreeMap. HashMap uses a
hash table In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...
. The hashes of the keys are used to find the elements in various buckets. LinkedHashMap extends this by creating a
doubly linked list In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the se ...
between the elements, allowing them to be accessed in the order in which they were inserted into the map. TreeMap, in contrast to HashMap and LinkedHashMap, uses a red–black tree. The keys are used as the values for the nodes in the tree, and the nodes point to the elements in the map. The java.util.Map interface is extended by its subinterface, java.util.SortedMap. This interface defines a map that's sorted by the keys provided. Using, once again, the compareTo() method or a method provided in the constructor to the sorted map, the key-element pairs are sorted by the keys. The first and last keys in the map can be called. Additionally, submaps can be created from minimum and maximum keys. SortedMap is implemented by java.util.TreeMap. The java.util.NavigableMap interface extends java.util.SortedMap in various ways. Methods can be called that find the key or map entry that's closest to the given key in either direction. The map can also be reversed, and an iterator in reverse order can be generated from it. It's implemented by java.util.TreeMap.


Extensions to the Java collections framework

Java collections framework is extended by the
Apache Commons The Apache Commons is a project of the Apache Software Foundation, formerly under the Jakarta Project. The purpose of the Commons is to provide reusable, open source Java software. The Commons is composed of three parts: proper, sandbox, and dormant ...
Collections library, which adds collection types such as a bag and bidirectional map, as well as utilities for creating unions and intersections. Google has released its own collections libraries as part of the guava libraries.


See also

* Collection *
Container A container is any receptacle or enclosure for holding a product used in storage, packaging, and transportation, including shipping. Things kept inside of a container are protected on several sides by being inside of its structure. The term ...
*
Standard Template Library The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called '' algorithms'', '' ...
*
Java concurrency The Java programming language and the Java virtual machine (JVM) have been designed to support concurrent programming, and all execution takes place in the context of threads. Objects and resources can be accessed by many separate threads; each ...
*
Java ConcurrentMap The Java programming language's Java Collections Framework version 1.5 and later defines and implements the original regular single-threaded Maps, and also new thread-safe Maps implementing the interface among other concurrent interfaces. In Java ...


References

Java (programming language) Data structures libraries and frameworks