dsa

Data Structures & Algorithms - Spring 2018
Log | Files | Refs | README

ListArrayBased.java (3193B)


      1 package lab8;
      2 
      3 // ********************************************************
      4 // Array-based implementation of the ADT list.
      5 // *********************************************************
      6 public class ListArrayBased<T> implements ListInterface<T>
      7 {
      8 
      9     private static final int MAX_LIST = 3;
     10     protected T []items;  // an array of list items
     11     protected int numItems;  // number of items in list
     12 
     13     public ListArrayBased()
     14     {
     15         items = (T[]) new Object[MAX_LIST];
     16         numItems = 0;
     17     }  // end default constructor
     18 
     19     public boolean isEmpty()
     20     {
     21         return (numItems == 0);
     22     } // end isEmpty
     23 
     24     public int size()
     25     {
     26         return numItems;
     27     }  // end size
     28 
     29     public void removeAll()
     30     {
     31         // Creates a new array; marks old array for
     32         // garbage collection.
     33         items = (T[]) new Object[MAX_LIST];
     34         numItems = 0;
     35     } // end removeAll
     36 
     37     public void add(int index, T item)
     38             throws  ListIndexOutOfBoundsException
     39     {
     40         if (numItems == items.length )  //fixes implementation errors and programming errors.
     41         {
     42             throw new ListException("ListException on add");
     43         }  // end if
     44         if (index >= 0 && index <= numItems)
     45         {
     46             // make room for new element by shifting all items at
     47             // positions >= index toward the end of the
     48             // list (no shift if index == numItems+1)
     49             for (int pos = numItems-1; pos >= index; pos--)  //textbook code modified to eliminate logic error causing ArrayIndexOutOfBoundsException
     50             {
     51                 items[pos+1] = items[pos];
     52             } // end for
     53             // insert new item
     54             items[index] = item;
     55             numItems++;
     56         }
     57         else
     58         {
     59             // index out of range
     60             throw new ListIndexOutOfBoundsException(
     61                     "ListIndexOutOfBoundsException on add");
     62         }  // end if
     63     } //end add
     64 
     65     public T get(int index)
     66             throws ListIndexOutOfBoundsException
     67     {
     68         if (index >= 0 && index < numItems)
     69         {
     70             return items[index];
     71         }
     72         else
     73         {
     74             // index out of range
     75             throw new ListIndexOutOfBoundsException(
     76                     "ListIndexOutOfBoundsException on get");
     77         }  // end if
     78     } // end get
     79 
     80     public void remove(int index)
     81             throws ListIndexOutOfBoundsException
     82     {
     83         if (index >= 0 && index < numItems)
     84         {
     85             // delete item by shifting all items at
     86             // positions > index toward the beginning of the list
     87             // (no shift if index == size)
     88             for (int pos = index+1; pos < numItems; pos++) //textbook code modified to eliminate logic error causing ArrayIndexOutOfBoundsException
     89 
     90             {
     91                 items[pos-1] = items[pos];
     92             }  // end for
     93             items[numItems - 1] = null; // Fixes memory leak.
     94             numItems--;
     95         }
     96         else
     97         {
     98             // index out of range
     99             throw new ListIndexOutOfBoundsException(
    100                     "ListIndexOutOfBoundsException on remove");
    101         }  // end if
    102     } //end remove
    103 
    104 
    105 
    106 }