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