Data Structures, Algorithms, & Applications in Java
Chapter 8, Exercise 25

public class TridiagonalAsIrregularArray
{
   // data members
   int rows;              // matrix dimension
   Object zero;           // zero element
   Object [][] element;   // element array

   // constructor
   public TridiagonalAsIrregularArray(int theRows, Object theZero)
   {
      // validate theRows
      if (theRows < 1)
         throw new IllegalArgumentException
                   ("number of rows must be > 0");
   
      rows = theRows;
      zero = theZero;

      // create and initialize the irregular array
      element = new Object [rows][];
      // do row 1 of the matrix
      element[0] = new Object [2];
      element[0][0] = element[0][1] = zero;
      // do row rows of the matrix
      element[rows - 1] = new Object [2];
      element[rows - 1][0] = element[rows - 1][1] = zero;
      // do the remaining ros
      for (int i = 1; i < rows - 1; i++)
      {
         element[i] = new Object[3];
         element[i][0] = element[i][1] = element[i][2] = zero;
      }

   }
   
   // methods
   /** throws IndexOutOfBoundsException when i < 1
     * or j < 1 or i > rows or j > rows */
   void checkIndex(int i, int j)
   {
      if (i < 1 || j < 1 || i > rows || j > rows)
         throw new IndexOutOfBoundsException
                   ("i = " + i + " j = " + j +
                    " rows = " + rows + " cols = " + rows);
   }

   /** return the element this(i,j)
     * throws IndexOutOfBoundsException when i or j invalid */
   public Object get(int i, int j)
   {
      checkIndex(i, j);

      // determine element to return
      if (i - j >= -1 && i - j <= 1)
      {// in the tridiagonal
         if (i == 1)
            return element[i - 1][j - 1];
         else
            return element[i - 1][j - i + 1];
       }
       else
         // not in the tridiagonal
         return zero;
   }
   
   /** set this(i,j) = newValue
     * throws IndexOutOfBoundsException when i or j invalid */
   public void set(int i, int j, Object newValue)
   {
      checkIndex(i, j);

      // store newValue
      if (i - j >= -1 && i - j <= 1)
      {// in the tridiagonal
         if (i == 1)
            element[i - 1][j - 1] = newValue;
         else
            element[i - 1][j - i + 1] = newValue;
      }
      else
         // not in the tridiagonal
         if (!((Zero) newValue).equalsZero())
                   throw new IllegalArgumentException
                         ("elements not on tridiagonal must be zero");
   }
}

(a)

The test program and output appear in the files TridiagonalAsIrregularArray.*.

(b)

The irregular array representation needs space for the rows entries of element[] in addition to space for the 3*rows-2 entries of the tridiagonal. Therefore, approximately 33% extra space is required. The differential is higher if we represent a boolean matrix rather than a generic matrix. In this case, 4rows bytes are needed for the references in the boolean array element[][] and (3rows - 2)/8 bytes are needed for the boolean entries of the tridiagonal. When using the one-dimensional array representation, the 3rows - 2 entries of the boolean array element require only (3rows - 2)/8 bytes of space. So the irregular array representation takes almost 12 times as much space as does the one-dimensional array representation.

When representing a matrix of type double or long, rather than a generic matrix, the relative space overhead incurred by the irregular array scheme is less because each matrix element takes 8 bytes, whereas each reference of element[] still takes 4 bytes.

With respect to run time, methods such as input, output, add, etc. can be implemented using a single for loop when the one-dimensional array representation is used (see Exercise 15). When the irregular array representation is used, two nested for loops are needed. Because of the added overheads of having two loops rather than one and of having to index into a two-dimensional array rather than into a one-dimensional array, we expect the one-dimensional array representation to be faster than the irregular array representation.