Application of storage structures in object-oriented programming.

  • Collections are objects that reference a set of objects.
  • They are dynamic structures.
  • Any object can be stored in a collection.
  • They may or may not provide element ordering, insert and delete elements, allow or not duplicate elements...

The iterator:

  • Models sequential traversal through the elements of any collection in an abstract way.
  • Defines a standard interface that frees you from knowing the details of the internal representation of the data type.
  • We have two main methods:
  • hasNext().
  • next().
  • remove() (optional).

For example:

Collection<T> coleccion = new ArrayList<>();

Iterator itr = coleccion.iterator();

while(itr.hasNext()) {

   T element = itr.next();

System.out.print(element + " ");

Collections in the JDK (Java Development Kit).

The Collection interface identifies any collection of objects, with or without duplicates.

  • Set: Inherits from Collection, but does not allow duplicate elements or objects.
  • List: Inherits from Collection, allows duplicates, expresses index and position order relationships.
  • Map (hash table): inherits from neither Set nor Collection. They are collections of key-value pairs (K,V) (key, Value).

API.

Set interface

Corresponds to the mathematical definition of a set (duplicates are not allowed).

The interface is identical to that of Collection.

Constructors must create a collection without duplicates; the add method cannot add an element that is already present in the set.

Set implementations:

  • HashSet: Implemented with a hash table. It has no element ordering.
  • TreeSet (implementation of SortedSet), implemented using a tree. Guarantees element ordering. Includes methods to take advantage of the order:
  • first().
  • last().
  • headSet(e).
  • tailSet(e).
  • subSet(e1,e2).

TreeSet example

package Colecciones;

import java.util.*;

public class TreeSet_Ejemplo {

    public static void main(String[] args) {

     Set<Integer> s = new TreeSet<>();

     String numerosIntroducidos = new String();

     for(String valor : args){

         numerosIntroducidos += " " + valor;

     }

     System.out.println("Numeros introducido: " + numerosIntroducidos);

     for (String arg : args) {

         if (!s.add(Integer.parseInt(arg))) {

             System.out.println("Duplicado detectado: " + arg);

         }

         System.out.println( s.size() + " Palabras diferentes detectadas: " + s);

     }

    }

}

List interface

  • Corresponds to a group of elements that express a linear order relationship, one after the other.
  • Allows duplicates.
  • Extends the Collection interface.
  • Access to elements via indices, like arrays.
  • add (int, Object).
  • get(int).
  • remove(int).
  • set(int,Object).
  • indexOf(Object).
  • lastIndexOf(Object).
  • subList(int fromIndex, int toIndex).
  • Specialized Iterator: ListIterator (next(), previous(), …)

Other considerations:

  • add (Object), adds to the end of the list.
  • remove (Object), removes from the beginning of the list.

For more information, see the API.

List implementations

  • ArrayList:
  • List implemented as an array.
  • An element can be accessed, queried, inserted, or removed using its index or range (number of elements preceding it).
  • Allows very fast random access to elements, but performs insertion and deletion operations in the middle of the list slowly.

LinkedList:

  • Implementation based on a doubly linked list.
  • More efficient than ArrayList for insertions and deletions, but worse for accessing elements.

ArrayList example

package Colecciones;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

public class ArrayList_Ejemplo {

 public static void main(String args[]) {

     List<Integer> l = new ArrayList<> ();

     for (int i = 0; i < args.length; i++){

         l.add(Integer.parseInt(args[i]));

     }

     System.out.println(l);

     l.add(l.size(),Integer.parseInt(args[0]));

     System.out.println(l);

     Collections.shuffle(l);

     System.out.println(l);

     Collections.shuffle(l);

     System.out.println(l);

 }

}

LinkedList example

package Colecciones;

import java.util.*;

public class LinkedList_Ejemplo {

 private LinkedList<Integer>  list = new LinkedList<>();

    public void push (Integer o){

        list.addFirst(o);

 }

 public Object top(){

        return list.getFirst();

 }

 public Object pop (){

        return list.removeFirst();

 }

 public static void main(String args[]) {

        LinkedList_Ejemplo s = new LinkedList_Ejemplo();

        s.push(1);

        s.push(2);

        s.push(3);

           s.push(5);

        s.push(4);

        System.out.println(s.list.toString());

        System.out.println(s.pop()); // Saca el último número introducido.

        System.out.println(s.list.toString());

        System.out.println(s.top()); // Muestra el último número introducido

        System.out.println(s.list.toString());

 }

}

Map interface

A Map stores key/value pairs (hash).

Elements are called entries (entry). Each entry is a pair of elements (k,v), where k is the key and v is the value.

entry = (k,v).

Does not allow duplicates: one value per key.

When a new entry is added, if an entry with the same key already exists, the previously stored value is overwritten.

For more information, see API.

Map implementations

HashMap

Implementation based on a hash table.

Does not order key-value pairs (key, value).

TreeMap

Implementation using a red-black balanced search tree.

Key-value pairs are ordered by key.

Includes methods to take advantage of the order:

  • firstKey()
  • lastKey()
  • headMap(k)
  • tailMap(k)
  • subMap(k1, k2).

For more information, we can check the API.