Java Collections Framework Part 6 - Queues

This is the sixth part of the tutorial, and this link goes to the previous post java collections framework part 5

Queues

A queue is a collection that implements the interface java.util.Queue , usually a queue is an ordered collection that follows the FIFO (First-In, First-Out) rule, but the queue implementations allow other ways to order the collection as well, such as LIFO or based on priority and so on.

The Queue interface defines the following methods:

boolean add(E e): Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.

E element(): Retrieves, but does not remove, the head of this queue.

Boolean offer(E e): Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.

E peek(): Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

E poll(): Retrieves and removes the head of this queue, or returns null if this queue is empty.

E remove(): Retrieves and removes the head of this queue.

Whatever the ordering used, the head of the queue is that element which would be removed by a call to remove() or poll(). In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties.

PriorityQueue

The class java.util.PriotiyQueue is an implementation of the Queue interface, it is an ordered collection and allows duplicates, it works as a “Priority-In, Priority-Out” collection, its elements are ordered by priority and its default priority is given by its natural order, it can be defined another priority order with an instance of a Comparator.

Example

The previous example should print the elements in the collection according to its priority, in this case it should print 1 2 3 4 5 6 7 8 9, this means they priority is the natural order.

To specify a different priority an instance of a Comparator should be used:

Example

The previous example should print its elements according to the new priority specified at the time the collection was created, this new priority is the inverse of the natural order and the example should print 9 8 7 6 5 4 3 2 1

Deque

The java.util.Deque interface extends the Queue interface, the deque name means “double-ended queue”. In a double-ended queue elements can be inserted and removed at both ends of the queue, unlike queue that elements only can be inserted at the tail and removed at the head.

With this a deque can also act as a LIFO collection or Stack.

The Deque interface defines new methods besides the ones defined in the Queue interface:

void addFirst(E e) : Inserts e at the head if there is enough space

void addLast(E e): Inserts e at the tail if there is enough space

void push(E e): Inserts e at the head if there is enough space

boolean removeFirstOccurrence(Object o): Removes the first occurrence of o

boolean removeLastOccurrence(Object o): Removes the last occurrence of o

Iterator<E> descendingIterator(): Gets an iterator that returns the elements in reverse order

boolean offerFirst(E e): Inserts e at the head if the deque has space

boolean offerLast(E e): Inserts e at the tail if the deque has space

E peekFirst(): Gets but do not removes the first element

E peekLast(): Gets but do not removes the last element

E pollFirst(): Gets and removes the first element

E pollLast(): Gets and removes the last element

E getFirst(): Gets but do not removes the first element

E getLast(): Gets but do not removes the last element

E removeFirst(): Gets and removes the first element

E removeLast(): Gets and removes the last element

E pop(): Gets and removes the first element

Example

In the previous example a deque collection was created and elements were added in different ways, first the elements were added at the head so the collection final order was:

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

The the elements were added to the tail the collection final order was:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

And this is also the default behavior for adding elements, in the example were used methods for querying the head and the tail of the collection. The example should print:

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

0

9

0

LinkedList

The class java.util.LinkedList besides being a List also implements the Deque interface, this class is very popular because with one class many different behaviors can be implemented.

Go to part 7

Java Collections Framework Part 5 - Maps

This is the sixth part of the tutorial, and this link goes to the previous post java collections framework part 4

Maps

A Map implements the java.util.Map interface, this interface doesn't extends from the Collection interface. A map is a collection of key-value mappings, they don't allow duplicate keys and like Sets, maps rely on the equals() method to determine whether two keys are the same or different.

Maps do not have order but some implementations are sorted like the TreeMap.

Maps like the Collection interface have methods for adding and removing elements, querying collection contents, and providing different views of the contents of a collection, and some of this methods are:

V put(K key, V value): Add or replace a key-value association, returns the old value (may be null) if the key was present; otherwise returns null.

void putAll(Map<? extends K,? extends V> m): Adds each of the key-value associations in the supplied map into the receiver.

void clear(): Removes all associations from this map.

V remove(Object key): Removes the association, if any, with the given key; returns the value with which it was associated, or null.

V get(Object k): Returns the value corresponding to k, or null if k is not present as a key.

boolean containsKey(Object k): Returns true if k is present as a key.

boolean containsValue(Object v): Return true if v is present as a value.

int size(): Returns the number of mappings.

boolean isEmpty(): Returns true if there are no mappings.

Set<Map.Entry<K, V>> entrySet(): Returns a Set view of the associations.

Set<K> keySet(): Return a Set view of the keys

Collection<V> values(): Return a Collection view of the values

The java.util.HashMap class is an implementation of the Map interface. HashMap it keeps its elements unsorted and unordered.

You should know that HashMap allows one null key and multiple null values in a collection.

Example:

In the previous example a HashMap of Integers as keys and Strings as values was created, five elements were added and then an element was added again replacing its previous value. The output of the example should be:

Map:{[1, one] [2, two] [3, three-again] [4, four] [5, five] }

The java.util.Hashtable class is also an implementation of the Map interface and it is almost identical

to the HashMap class but it is synchronized so it performs slower than HashMap and another difference is that Hashtable doesn't let you have anything that's null.

The java.util.LinkedHashMap class extends from the HashMap class and therfore is an Implementation of the Map interface, and as the LinkedHashSet class the LinkedHashMap it maintains insertion order (or, optionally, access order). Access ordered is defined by the argument of of the constructor:

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

A value false will give an insertion-ordered map, if order constructor is used to create the LinkedHashMap by default it would be an insertion-ordered map.

Example:

The output of the example should be the following:

Map { [1-1] [2-2] [3-3] [4-4] [5-5] }

Changing the the iteration order for an access order in the previous example:

Notice that after adding the elements an access to the element “1” is done with this the iteration order is changed and the output should be the following:

Map Keys { [2] [3] [4] [5] [1] }

Also notice that the output format has changed and now just the keys are printed, this is because if the element is obtained inside the iteration loop a ConcurrentModificationException would arise because the iteration order is changed , and this can not be done while the map is iterated. So be careful when the Map is in this mode.

TreeMap

The class java.util.TreeMap is an implementation of the Map interface, it also implements the

java.util.NavigableMap and java.util.SortedMap interfaces. This collection is pretty similar to TreeSet, it is an sorted collection and guarantees that the keys will be in ascending order, according to their natural order, or by a Comparator provided at map creation time, depending on which constructor is used.

The TreeMap class implements methods that help navigate the map, and some of these methods are:

K ceilingKey(key): Returns the lowest key >= key

K higherKey(key): Returns the lowest key > key

K floorKey(key): Returns the highest key <= key

K lowerKey(key): Returns the highest key < key

Map.Entry<K,V> pollFirstEntry(): Returns and removes the first key-value pair

Map.Entry<K,V> pollLastEntry(): Returns and removes the last key-value pair

NavigableMap<K,V> descendingMap(): Returns a NavigableMap in reverse order

NavigableSet<K> descendingKeySet(): Returns a reverse-order key set

NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive):Returns a part of the map whose keys range from fromKey to toKey.

NavigableMap<K,V> headMap(K toKey, boolean inclusive):Returns a part of the map whose keys are less than toKey.

NavigableMap<K,V> tailMap(K fromKey, boolean inclusive):Returns a part of the map whose keys are greater than or equal to fromKey.

Example:

The example should print in console the following:

keys: [1, 2, 3, 4, 5]

Ceiling: 3

Higher: 4

Floor: 3

Lower: 2

Descending keys: [5, 4, 3, 2, 1]

Head map: {1=one, 2=two}

Tail map: {1=one, 2=two}

Poll first: 1=one

Poll last: 5=five

keys: [2, 3, 4]

You can notice how the elements in the map are printed in ascending order, but the map can also be iterated in descending order with the method descendingKeySet().

The sub maps obtained with the methods headMap(), tailMap() and others are backed maps ant hey behave just like any other backed collection this is if submap is modified then also the map is modified

and viceversa.

Go to part 6

Java Collections Framework Part 4 - Sets

This is the sixth part of the tutorial, and this link goes to the previous post  java collections framework part 3

Sets

A Set implements the interface java.util.Set, it has the same methods as those of the Collection interface.

Sets do not accept duplicate elements, if the add() method is called with an object that already is in the set it should return false. The elements of the set must have a good implementation of the equals() method.

There are different implementations of the Set interface they can have order, can be sorted, or neither this is they can be unordered and unsorted.

HashSet

The class java.util.HashSet is an implementation of the Set interface, it is not sorted and it doesn't have an order. If the hashset is iterated it states that it does not guarantee that the order will remain constant over time.

The elements of this type of set must implement the the hashcode() and the equals() methods, this is because it is implemented as a hash table in which elements are stored at a position derived from their contents. So, Two elements are considered equal or duplicate if they return the same hash code from the hashcode() method and they return true from testing them with the equals() method.

The Set first gets the hash code from the element then places the element in a bucket of the hash table for that hash code, if the bucket already has an element then it tests for duplicity the elements with their equals().

Example:

In the previous example the Element class has two implementations of the hashcode() method one that uses the hashcode of its value attribute of type String and other that generates random integers, if the implementation that uses the String is used then the Set would not accept duplicate elements this is because same strings should generate the same hashcode so the ouptut with this implementation should not contain any duplicate element as this:

[3, 2, 1, 4]

But if the implementation that generates random integer is used then the Set would accept duplicate elements because it would be placing each element in a different bucket of its hash table, the output would be something like this:.

[3, 2, 1, 4, 1]

LinkedHashSet

The class java.util.LinkedHashSet extends from the class HashSet and therefore is an implementation of the Set interface. LinkedHashSet is hash table and a doubly-linked list, it has an order, its iterators will return their elements in the order in which they were added.

The LinkedHashSet doesn't define any new method, it just adds the linked functionality to the HashSet class.

Example:

In the previous example the output should in the order in which the elements were added, so it should print this:

[ 6, 5, 3, 4, 1, ]

TreeSet

The class java.util.TreeSet is an implementation of the Set interface, it also implements the java.util.NavigableSet and java.util.SortedSet interfaces, it is an sorted collection and guarantees that the elements will be in ascending order, according to their natural order, or by a Comparator provided at set creation time, depending on which constructor is used.

The TreeSet class implements methods that help navigate the set, and some of these methods are:

E ceiling(e): Returns the lowest element >= e

E higher(e): Returns the lowest element > e

E floor(e): Returns the highest element <= e

E lower(e): Returns the highest element < e

E pollFirst(): Returns and removes the first entry

E pollLast(): Returns and removes the last entry

NavigableSet  descendingSet(): Returns a NavigableSet in reverse order

Example:

The example should print

First:1

Last:5

Higher:4

Lower:2

Ceiling:3

Floor:3

The TreeSet class also has more methods that return section of its collection, some of this methods are:

NavigableSet headSet(e, b*): Returns a subset ending at element e and exclusive of e

NavigableSet tailSet(e, b*): Returns a subset starting at and inclusive of element e

NavigableSet subSet(s, b*, e, b*): Returns a subset starting at element s and ending just before element e

The collections that return this methods are backed collections, this means when an element is added to the original or to the backed collection, the new entries were automatically added to the other collection

Example:

The example should print

Set: [a, b, c, d, g]

Sub set: [c, d]

Set: [a, b, c, d, e, g]

Sub set: [c, d, e]

Note that the subset was modified and also the set is modified, this is because subset is a backed collection of the set.

Go to part 5

Java Collections Framework Part 3 - Lists

This is the sixth part of the tutorial, and this link goes to the previous post java collections framework part 2

Lists

A list implements the interface java.util.List. Lists are based by indexed elements, they are ordered by index positions. Lists can contain duplicate elements.

List have methods based in index that other collections don't have:

void add(int index, E element): Inserts the specified element at the specified position in this list.

boolean addAll(int index, Collection<? extends E> c): Inserts all of the elements in the specified collection into this list at the specified position.

E get(int index): Returns the element at the specified position in this list.

E remove(int index): Removes the element at the specified position in this list.

E set(int index, E element): Replaces the element at the specified position in this list with the specified element.

List <E> subList(int fromIndex, int toIndex): Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.

int indexOf(Object o): Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

int lastIndexOf(Object o): Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.

The class java.util.ArrayList is an implementation of a list. It stores its element starting at index 0, it is like a growable array. It is NOT synchronized as its counterpart the java.util.Vector class.

Example:

List <String> list = new ArrayList <String> ();
list.add("1");
list.add("2");
list.add(2, "3");
System.out.println(list.size());
System.out.println(list.indexOf(“3”));

In the example the index has to be not bigger than the index of the last element plus one. The size of the list would be 3 since it contains 3 elements and it would print 2 as the index of the element “3”, this is because they start at index 0.

The java.util.Vector class basically is the same as the ArrayList class with the difference that it is thread safe, this means that its methods are synchronized. The Vector class may perform slower than the ArrayList class, so if a list is needed and only one thread will interact with it, so it is better to choose ArrayList over Vector.

The java.util.Stack class is a List implementation which extends from Vector class. But it also implements other functionality besides being and index ordered collection, it can implement a LIFO (Last In, First Out) collection.

For this functionality the Stack class has the following methods:

boolean empty(): Tests if this stack is empty.

E peek(): Looks at the object at the top of this stack without removing it from the stack.

E pop(): Removes the object at the top of this stack and returns that object as the value of this function.

E push(E item): Pushes an item onto the top of this stack.

Example:

Stack <String> stack = new Stack <String> ();
stack.push("1");
stack.push("2");
stack.push("3");  
stack.push("4");  
stack.push("5");  
System.out.println(stack .pop());//Removes the top of the stack
System.out.println(stack .peek());//Doesn't remove the element

In the example the element 5 is printed and removes since it was the top of the stack, then the element 4 is printed but not removed.

The Stack list it also can act as a normal list and get its elements with an iterator:

Example:

...
Iterator iter = stack.iterator();
while(iter.hasNext()) {
 System.out.print(iter.next()+ " ");
}

In this way the elements are obtained as a list not as a stack, this is the first printed element would be 1 then 2 and so on.

The Stack is an old implementation of a LIFO stack, since java 1.6 new mechanisms were added for this with the interface java.util.Deque.

Tha java.util.LinkedList class is a List implementation, it is also an index ordered collection, but its elements are doubly-linked to one another. This behavior allows adding or removing from the beginning or end, making it easier to implement a stack or queue, so it can be a LIFO (Last In, First Out) or FIFO (First In, First Out) collection. It implements the java.util.Deque and java.util.Queue interfaces.

And some of its methods are:

void addFirst(E e): Inserts the specified element at the beginning of this list.

void addLast(E e): Appends the specified element to the end of this list.

boolean offerFirst(E e): Inserts the specified element at the front of this list.

boolean offerLast(E e): Inserts the specified element at the end of this list.

E pollFirst(): Retrieves and removes the first element of this list, or returns null if this list is empty.

E pollLast(): Retrieves and removes the last element of this list, or returns null if this list is empty.

E peekFirst(): Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.

E peekLast(): Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.

E removeFirst(): Removes and returns the first element from this list.

E removeLast(): Removes and returns the last element from this list.

These are some of its methods and the class contains many others, so before using it, its API should be reviewed.

Example:

LinkedList <String> ll = new LinkedList <String> ();
ll.add("1");
ll.add("2");
ll.add("3");
ll.add("4");
System.out.println("First: "+ ll.getFirst());
System.out.println("Last: "+ ll.getLast());
ll.addFirst(“5”);
System.out.println("First: "+ ll.pollFirst());
System.out.println("First: "+ ll.peekFirst());

The example should print 1, 4 and then 5, 1.

Lists and Arrays

The java collections framework has some mechanisms to convert arrays to lists and lists to arrays, but with some implications such as the lists and the arrays produced they become joined or bind.

The java.util.Collection interface has the toArray() method which returns an array containing all of the elements in the collection and since List interface extends from the Collection interface it has an implementation for this method.The returned array will be "safe" in that no references to it are maintained by this collection, this means that in this cases the List and array are not linked or bind.

Example:

List <Integer> ls = new ArrayList <Integer> ();ls.add(1);
ls.add(2);
ls.add(3);
Object[] obj = ls.toArray();//Returns Object[] array  
for(Object o:obj)
 System.out.print(o + " ");
Integer [] in = new Integer[3];  
ls.toArray(in);//Copies the list to the array passed

In the previous example the conversion to an array from a list the two versions of the toArray() method are used.

The java.util.Arrays class has the asList() method, it copies all of the elements from an array into a List, returns a fixed-size list backed or bind by the specified array.

Example:

String [] s = {"one", "two", "three", "four"};
List  ls = Arrays.asList(s);
ls.set(0, "1");//If the list is updated the array is updated too and viceversa
System.out.println(“Array updated”+Arrays.toString(s));
//ls.add("five"); //Will produce an error since it is linked to the array

In the previous example an array is converted to an array and they are linked or bind, so since arrays are fixed size no element can be added to the list, and if one element is updated in the list or in the array the other will see the change.

List ordered and search

The class java.util.Collections has the sort() method to sort lists in a specific order, it is overloaded with two versions one that accepts just a list, and the other that accepts a list and an instance of the java.util.Comparator interface.

There are some restrictions with the version of the sort() method that accepts just a list, and these are:

• The list elements mus implement the java.lang.Comparable interface.
• All the elements in the list must be mutually comparable, this means they must be of the same type.

Example:

List <String>  lst = new ArrayList <String> ();
lst.add("2");
lst.add("5");
lst.add("4");
lst.add("1");
lst.add("3");
Collections.sort(lst);
System.out.print("Arraylist of strings: ");
System.out.println(lst);

In the previous example the String classes implement Comparable interface and the list only contains strings, so there should not be a problem ordering the collection. The collection is ordered according to its natural order, this means according to the comparable interface, and the output should be Arraylist of strings: [1, 2, 3, 4, 5]

The other version of the sort method the one that takes an instance of Comparator interface besides the list, the list elements are not required to implement the Comparable interface, and the sort order is given by the Comparator interface.

Example:

List <String> lst = new ArrayList <String>();
lst.add("2");
lst.add("5");
lst.add("4");
lst.add("1");
lst.add("3");
Collections.sort(lst, new Comparator <String> (){
 public int compare(String one, String two) {  
  return two.compareTo(one);
 }
});
System.out.print("Arraylist of strings: ");
System.out.println(lst);

In the previous example the list is ordered according to the Comparator order and it is just reversing the natural order, the output should be Arraylist of strings: [5, 4, 3, 2, 1]

The The class java.util.Collections has the binarySearch() method which searches the list for a specific element, the list must be sorted before a search is done, if is not the results are unpredictable.

It returns and int indicating the index of the element or (-(insertion point) – 1), where insertion point is the point at which the element would be inserted into the list

Example (The list would be the used in the previous examples):

System.out.println("three=" + Collections.binarySearch(ls, "3"));
System.out.println("five="+ Collections.binarySearch(ls, "5"));

The output of the example would be 2, -5

If a collection is ordered with an instance of the Comparator interface, then there is an overloaded method of binary search in the Colletions interface which accepts the Comparator to do the search.

Go to part 4