How I may help
LinkedIn Profile Email me!
Call me using Skype client on your machine

Reload this page Arrays and Collections

Here is a practical (rather than theoretical) comparison of how different programming languages use arrays and Collections. I describe the operations a programmer wants to do (adding, updating, sorting) rather than repeating SDK lists of classes, algorithms, wrappers, etc. Let me know if this helps you make more appropriate selection of collection classes/interfaces to suit the behaviors you want.

 

Topics this page:

  • Languages
  • Collections
  • Initialization of Arrays
  • Populating
  • Walking Vectors
  • Queries
  • Sorting
  • Algorithms
  • Interfaces & Classes
  • Instances
  • Set operations
  • Your comments???
  •  

    Site Map List all pages on this site 
    About this site About this site 
    Go to first topic Go to Bottom of this page


    Set screen Comparing Arrays in Languages

      Arrays in C and C++ are just pointers to an address in memory, and indexes to an array are offsets from that address. This made them error prone and thus a notorious hunting ground for "buffer overrun" security vulnerabilities which enable hackers to gain elevated access to the hacked system.


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen C# Fixed-Sized Array Coding

      C# supports arrays as a definite, distinct reference type (objects of a class with methods and properties), so out-of-bounds errors will result in an error that error handling routines can respond to specifically.

      • System.Array manages static arrays that cannot be resized once instantiated.
      • ArrayList objects from the System.Collection class can have a dynamic number of elements.

      Sample C# code:

      public void ArrayTests(){
      	string[] name = {"Aaron","Matthew","Mark","John"); // define array.
      	int index = Array.IndexOf(names,"Aaron"); // returns index into array.
      	ChangeName(names);
      	Assert.IsTrue(names[0] == "Allen"); // note zero is the first item.
      }
      private void ChangeName(string[] names){ // string[] can instead be an interface.
      	names[0] = "Allen";
      }
      


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen JavaScript Arrays


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Ruby Arrays

      The first and last items in a Ruby array defined with: my_array = ['venus','earth','mars'] can be accessed with my_array.first and my_array.last or my_array.each_with_index do |an_element, index|
      ?> puts "#{an_element} is number #{index}
      end


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen The Java Collections Framework

      A Java collection (implementation of package java.util new to Java 1.2), can store data of different types in a single structure and be sized dynamically (allowed to grow or shrink). It's a refinement of the C++ Standard Template Library (STL) and Smalltalk's collection hierarchy.

      Visio class diagram:

      • Interfaces to implement are in purple and use thin lines.
      • Abstract classes to extend are in blue and use thick lines.
      • Concrete classes to instantiate (with new constructor) are in green.
      • Historical legacy classes Stack and Vector (reworked from JDK 1.1) are in white. Deprecated Dictionary and its Hashtable class are not shown.


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Defensive Array Programming

      Validate all parameters.

      To protect Java array accesses, precede them with assert statement:

        assert((index > 0) && (index < N_ELEMENTS);
        i = array[index];

     


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Java Array Constants

      Unlike C, Java does not support direct manipulation of pointers into arrays.

      In Java, array arguments are always passed by address, not by value.

      Java arrays know how many entries they have when created.
      Unlike C, the size of Java arrays is given when it is created with the new constructor.

      Array constants are specified as a list of scalar constants enclosed in braces.

      int b[] = new int[7]; // set to defaults of 7 elements.
      int a[] = new int[] { 1, 2, 3:2, 5:* };
      

      The variables named “a” and “b” are also called the declarator. Unlike C, the initializer “5” is not specified. The repeat operator (:) specifies repetition of a constant element array. When an asterisk (*) is specified, the constant_element “5” is repeated as many times as necessary until the array has been initialized to the intializer. Thus, the above initializer for variable “a” is the same as:

      int[] a = { 1, 2, 3, 3, 5, 5, 5 };

      Idea Use line breaks to separate each dimension of a nested (multi-dimensional) array [i rows][j columns]:

      int a[2][] = { { 1, 2, 3, 4},
                     { 1, 2, 3, 4}};
      

     

      The Arrays class is concrete.
     
    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Array Manipulations

      An array is a structure that holds multiple values of the same data type (int or string). Java public static main functions declare String args[] to use an array to hold its arguments. To list them:

      n=args.length;
      for( int i=0; i<n; i++ ) { 
         System.out.println( "Parm "+ i +"="+ args[i] ); 
      }

      An index points to the value in each element within an array. Its use of a sequential index means arrays cannot contain duplicates. The first element is selected by subscript 0 (zero).

      The array length property -- the number of elements within an array -- is established when the array is created (at runtime). Arrays are not growable after initialization.

      Array elements are selected by enclosing an integer expression in brackets ([]).

      Unlike C, if an array index refers outside the specified range, Java throws a ArrayIndexOutOfBoundsException rather than allow buffer overrun conditions that can be exploited by hackers.

      Arrays can make use of collection methods for sorting and expansion when converted to a list collection

      List listX=java.util.Arrays.asList( arrayY );
      

     

      Loading and using arrays and collections is one of the major tricks to improve the run-time performance of busy applications because working in memory is faster than opening files and reading and writing to hard disks.

      webpage article Marcus Green's notes on the SCJP exam object 1

      Write code that declares, constructs and initializes arrays of any base type using any of the permitted forms, both for declaration and for initialization.

     
    Go to Top of this page.
    Next topic this page
    Next topic this page
    Set screen
      Subclassing AbstractCollection directly instantiates a bag -- an unordered collection that allows duplicate elements.

      Each additional level in the subclass makes more methods available. For example, when an ArrayList is instantiated by extending AbstractList and implementing List, it inherits methods of the Collection interface because AbstractList extends the AbstractCollection interface, which provides the toString() method.

      Abstract classes allow a collection to implement optional methods.

      To make a collection modifiable, simply override the set( object ) method.

      To make a collection grow, override the add( object ) and remove( int index) methods. New elements are added immediately prior to the implicit cursor. After adding an element, calling previous() returns the new element and calling next() returns what would have been the next element prior to the add operation.

      Reminder iterator() and size() methods are not in the AbstractCollection class because they need to be relevant to each structure.

      To make a twoi-dimensional array, define an array within an array, such as:

        String[] [] FirstName; FirstName = new String[14] [];

        or

        String[] [] FirstName = new String[14] [];

     

     
    Go to Top of this page.
    Next topic this page

    Set screen Populating Collections

      To add an object (line) to vectorTZ:

      vectorTZ.add(line);

      To add objects in collectionC to vectorTZ:

      boolean vectorTZ.addAll( collectionC );

      Boolean functions return true if action was taken successfully and false if not.

      To populate the vector with the intersection of elements in another Collection:

      void vectorTZ.retainAll( c );

     

      Java Collection operations do not need to be within a try-catch block because the Unsupported Operation Exception thrown when an add is attempted on a read-only collection is an extension of the RuntimeException class.

     
    Go to Top of this page.
    Next topic this page

    Set screen Methods for Vectors

      To determine if a vector has been populated with a specific object:

      vectorTZ.contains( ObjectO );

      To assign an object (line) to a specific index:

      vectorTZ.set( int index, object );

      To obtain a row from a vector (cast to String):

      String line = (String)vectorTZ.get(i);

      To rid the vector of a single object “O”:

      boolean vectorTZ.remove( ObjectO );

      To determine if a vector has been populated with objects:

      vectorTZ.isEmpty();

      To determine if a vector contains all the elements in another collection:

      boolean vectorTZ.containsAll( collectionC );

      To get a count of elements in a vector:

      int vectorTZ.size();

      To rid all elements from the vector:

      boolean vectorTZ.removeAllElements();

      To rid all elements also found in another collection:

      void vectorTZ.removeAll( Collection );
      void vectorTZ.clear();


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Sorting/Ordering

      There are several ways to order and re-order objects.

      Primitive String and Integer classes can implement the java.lang.Comparable interface to use a natural sorting order using the lexicographical compareTo() method, which places numbers before alpha letters and upper case A-Z letters before all lowercase a-z letters.

      Linked list Abstract classes allow a Collection to be sorted by being instantiated as another type:

      Set set = new HashSet();
      ...
      Set sortedSet = new TreeSet(set);
      

      To define objects (such as dates) can be inserted in reverse order:

      Comparator comparator = Collections.reverseOrder();
      Set reverseSet = new TreeSet(comparator);
      reverseSet.add("A");
      

      For locale-specific ordering, use Collator with CollationKey.

      The Java Collections Framework provides standard methods for working on all elements in the entire collection all at once:

      • sort( object or primitive ) is stable -- does not reorder equivalent elements while sorting.
      • reverse(list1) order
      • shuffle(list1) randomly


    Go to Top of this page.
    Previous topic this page
    Next topic this page

      Set screen VB Bubble Sort

      This VB function sorts a small string array in ascending order, without using any special external object.

        Function SortAscending(myArray)
        Dim pArray, i, j, temp
        pArray = myArray  'Create another array to hold results.
        For i = UBound(pArray) - 1 To 0 Step -1
            for j= 0 to i
                if uCase(pArray(j)) > uCase(pArray(j+1)) then
                    temp=pArray(j+1)
                    pArray(j+1)=pArray(j)
                    pArray(j)=temp
                end if
            next
        next
        SortAscending = pArray
        end Function 'SortAscending
        

      This approach creates another array, so both the before and after array can be printed out in this sample call:

        theArray = array("C","B","A")
        outputArray = SortAscending (theArray)
        For i=0 to ubound(outputArray)
            print i &" Before: ["& theArray(i) &"] After: ["& outputArray(i) &"]"
        Next
        

        In the real world, theArray will be created by other code.

      TIP: Define a coding standard whether a space is allowed between array name and the (iterator).

      The result

        0 Before: [C] After: [A]
        1 Before: [B] After: [B]
        2 Before: [A] After: [C]

      TIP: When displaying strings, it's best to encase each around [braces] so that leading and trailing spaces become visible.

      TIP: Define a coding standard whether a space should precede and follow each operator such as = and >.

      VB arrays are actually SAFEARRAY variables, which involes some overhead in making them syntactically simpler to program, such as UBound automatically providing the upper bound array index. So bubble sorts are appropriate only for small lists. When the array gets more then 20, instead use a b-tree algorithm.


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Algorithms for Collections

      The Java Collections Framework provides standard methods for working on all elements in the entire collection all at once:

    • fill( list1, o ) -- list1 with a single object o
    • copy( list1, list2 )
    • binarySearch returns an index, which is the negative insertion point if not found. Returns undefined if array is not sorted. Arrays of objects must implement java.lang.Comparable and provide a Comparator.

    • min() -- minimum value
    • max() -- maximum value


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Collections Interfaces & Classes

      There are several implementations of the Collection concept.

      Collection
      Interface
      New Class Usage Arguments & Additional Methods
      Set screen List is an ordered collection of objects. (has a positional index), so it can have duplicate objects.

      List overloads add() with add(int, Object) and addAll( collectionC ) to insert objects at the specified index.

      ArrayList extends AbstractList for a resizable Random Access array that's not synchronized. Cloneable. constructor argument can be a collection or int Capacity, also in ensureCapacity()
    • toArray()
    • Vector expandable array of sequenced objects. Modified to implement Collection. Synchronized.
      Stack A form of Vector to push LIFO (Last-In, First-Out) pop
      LinkedList extends AbstractSequentialList so each element references the next and previous element to emulate Stack, queue, and other end-oriented data structures. This doubly linked chain of objects speeds inserts/deletes but slows indexing. Use xxxFirst() to add, get, or remove at the beginning and xxxLast() at the end.
      Set screen Sets are unordered and so cannot contain duplicates of the same element. Implemented by the HashSet class. The Set interface does not define additional methods of its own. TreeSet implements SortedSet.

      Its constructor argument can be a collection, Comparator, or Sorted Set.

      a sorted binary tree of objects stored in ascending order. Does not allow duplicates. Cloneable.
    • Get the first() and last() elements
    • Use subSet( objectStart, objectEnd ) to obtain a portion of the elements.
    • Use headSet( objectEnd ) to get objects less than objectEnd.
    • Use tailSet( objectStart ) to get objects greater than objectStart.
    • HashSet Unsorted, so no duplicates or null values. Cloneable. constructor argument capacity of elements plus a fillRatio between 0.0 and 1.0.
      LinkedHashSet New to 1.4. Extends HashSet for insertion-order iterations.  
      Set screen Maps store objects based on the values of unique key-value associations between objects (such as IP addresses to domain names (DNS), keys to database records, or dictionary words to their definitions).

      A map can store duplicate objects, but not with duplicate keys.

      It replaces the Dictionary class deprecated in 1.2.

      Reminder The Map interface does not extend the Collection interface.

      It is implemented by classes HashTable and HashMap.

    • Map.Entry - An inner interface of the Map interface that defines methods for working with a single key-value pair.
    • TreeMap implements SortedMap stores objects in an ascending order of their keys, so it automatically sorts objects to the default Comparator.
      HashMap reference by key. Not synchronized like Hashtable of Dictionary. Allows nulls. Uses .equals() to compare.
      WeakHashMap entry vanishes when its key is no longer reachable by any thread. 1.3 adds a constructor to accept a Map.
      IdentityHashMap New to 1.4. Uses the == operator instead of equals() method to compare.

      BitSet, an array of boolean bits, is not a set and not part of the Collections framework.


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Collections Implementation


    Go to Top of this page.
    Previous topic this page
    Next topic this page

      Set screen Hash Codes

      Objects added to a HashSet implement a hashCode() method to calculate an index based on the plain-text string.

      To distribute as evenly as possible over the capacity of the collection, space usage is optimized by tuning the initial capacity and a load factor of between 0.0 and 1.0. A load factor of 0.0 has no room.

      TreeSet has no tuning options, as the tree is always balanced, ensuring log(n) performance for insertions, deletions, and queries.

      The AbstractSet class overrides the equals() and hashCode() methods to ensure two equal sets return the same hash code. Two sets are equal if they are the same size and contain the same elements. By definition, the hash code for a set is the sum of the hash codes for the elements of the set. Thus, no matter what the internal ordering of the sets, two equal sets will report the same hash code.


    Go to Top of this page.
    Next topic this page

      Set screen Synchronized and Sharing

      Arrays cannot be declared shared. Arrays are not thread-safe.

      Collections classes are not synchronized. The synchronized keyword is used to prevent more than one thread from accessing a block of code at a time. Synchronization functionality is added by use of a wrapper class such as

      Map sm = Collections.SynchronizedMap( map1 );


    Go to Top of this page.
    Next topic this page

    Set screen java.util.Collection Framework

      The Java collection framework enables polymorphic processing -- manipulation of one collection type through a different collection type, regardless of the collection's internal implementation.

      The different implementations of Collection can all use the same methods defined by the Collection interface because the parent Collection interface defines the names of generic methods to:

      • determine whether the collection contains() a specified value.
      • get the location an element;
      • navigate the group with Enumerations by getting the next object in the collection;
      • navigate and remove objects with interfaces Iterator or listIterator;
      • process the group as a whole with Algorithms to such as clearing or removing all elements from the collection.

      The Collection superclass is abstract because it is not meant to be implemented, but its subclasses are implemented. An abstract class cannot be instantiated.

      Subclassing AbstractCollection directly implements a bag -- an unordered collection that allows duplicate elements.

      To provide functionality for ordering elements, sorting, handling growth, and handling duplicates, AbstractCollection is subclassed by AbstractList, AbstractSet, and AbstractMap.

      Collection subclasses are concrete (not abstract) so that an implementation does not have to override every method of the abstract class. To implement a List, only size() and get() methods need to override what is inherited from subclassing AbstractList. Functionality to modify a List are optionally defined by overriding set(), add(), and remove() methods. Similarly, to extend an unmodifiable AbstractMap, only the entrySet() method needs to be overridden and the Map.Entry implemented. For a modifiable Map, override add(), remove(), put(), and support remove() of the iterator returned by the entrySet().Iterator().

      The Enumeration interface provides two methods for stepping through an indexed set of objects:

      • hasMoreElements() contained in an Enumeration object.
      • nextElement() contained by an object.

      The Iterator interface enables next(object) and boolean query hasNext(). Its remove() void method delete objects when an enumerator does not. ListIterator extends the Iterator interface by providing methods for iterating through the elements of a list bi directionally: previous(), hasPrevious(), plus previousIndex() and nextIndex()

      iterators for the concrete collection implementations are fail-fast. That means that if you are using an Iterator to traverse a collection while underlying collection is being modified by another thread, then the Iterator fails immediately by throwing a ConcurrentModificationException (another RuntimeException). That means the next time an Iterator method is called, and the underlying collection has been modified, the ConcurrentModificationException exception gets thrown.

      The Comparator interface provides the compare() method for comparing the elements of a collection. Method equals() returns true if two sets are the same size and contain the same elements in the same order.

     

    webpage article Sun's Java Tutorial on Arrays

    webpage article Introduction to the Collections Framework by John Zukowski of the MageLang Institute

    The hierarchy of classes of the java.lang.Object package are: Dictionary-Stores key-value pairs.

      Hashtable-Generates indexes for storing objects in the dictionary. Does not allow null values.
        Properties class.


    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Instances

      In Java, arrays exist as objects. To determine if an object is an array (without regard to the base type) use the isArray() method of the Class class.

      To determine if a value is contained in an array Parent (an instance of the array), use the instanceof operator:

      if (p instanceof Parent) {
      ...
      }

     

     
    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Set screen Java Set Operations

      The Java System class static method arraycopy copies the first dimension of an array. Multi-dimensional arrays use the elements of this first dimension to refer back to the source array elements, which are, in turn, arrays.

      To create a stand-alone array, allocate new sub-arrays, then arraycopy the source array.

      Public methods of a collection provide a view.

     

     
    Go to Top of this page.
    Previous topic this page
    Next topic this page

    Portions ©Copyright 1996-2011 Wilson Mar. All rights reserved. | Privacy Policy

    Related:

  • Programming Languages
  • Java Programming
  • Applications Development
  • On the web

  • How I may help

    Send a message with your email client program


    Your rating of this page:
    Low High




    Your first name:

    Your family name:

    Your location (city, country):

    Your Email address: 



      Top of Page Go to top of page

    Thank you!