Source of ArrayList.java


  1: //ArrayList.java

  3: class ArrayList
  4: {
  5:     // Private members
  6:     private int[] arrayData;
  7:     private int arrayListLength;

  9:     // The default constructor initializes the list with a capacity of 4
 10:     public ArrayList()
 11:     {
 12:         this(4);
 13:     }

 15:     public ArrayList(int capacity)
 16:     {
 17:         this.arrayData = new int[capacity];
 18:         this.arrayListLength = 0;
 19:     }

 21:     public void append(int newItem)
 22:     {
 23:         // Resize if the array is full
 24:         if (arrayData.length == arrayListLength)
 25:         {
 26:             resize(arrayListLength * 2);
 27:         }

 29:         // Insert the new item at index arrayListLength
 30:         arrayData[arrayListLength] = newItem;

 32:         // Increment the array's length
 33:         ++arrayListLength;
 34:     }

 36:     public void resize(int newAllocationSize)
 37:     {
 38:         // Create a new array with the indicated size
 39:         int[] newArray = new int[newAllocationSize];

 41:         // Copy items in current array into the new array
 42:         for (int i = 0; i < arrayListLength; ++i)
 43:         {
 44:             newArray[i] = arrayData[i];
 45:         }

 47:         // Assign the arrayData member with the new array
 48:         arrayData = newArray;
 49:     }

 51:     public void prepend(int newItem)
 52:     {
 53:         // Resize if the array is full
 54:         if (arrayData.length == arrayListLength)
 55:         {
 56:             resize(arrayListLength * 2);
 57:         }

 59:         // Shift all array items to the right,
 60:         // starting from the last index and moving
 61:         // down to the first index.
 62:         for (int i = arrayListLength; i > 0; --i)
 63:         {
 64:             arrayData[i] = arrayData[i - 1];
 65:         }

 67:         // Insert the new item at index 0
 68:         arrayData[0] = newItem;

 70:         // Update the array list's length
 71:         ++arrayListLength;
 72:     }

 74:     public void insertAfter
 75:     (
 76:         int index,
 77:         int newItem
 78:     )
 79:     {
 80:         // Resize if the array is full
 81:         if (arrayData.length == arrayListLength)
 82:         {
 83:             resize(arrayListLength * 2);
 84:         }

 86:         // Shift all the array items to the right,
 87:         // starting from the last item and moving down to
 88:         // the item just past the given index.
 89:         for (int i = arrayListLength; i > index + 1; --i)
 90:         {
 91:             arrayData[i] = arrayData[i - 1];
 92:         }

 94:         // Insert the new item at the index just past the
 95:         // given index.
 96:         arrayData[index + 1] = newItem;

 98:         // Update the array's length
 99:         ++arrayListLength;
100:     }

102:     public int search(int item)
103:     {
104:         // Iterate through the entire array
105:         for (int i = 0; i < arrayListLength; ++i)
106:         {
107:             // If the current item matches the search
108:             // item, return the current index immediately.
109:             if (arrayData[i] == item)
110:             {
111:                 return i;
112:             }
113:         }

115:         // If the above loop finishes without returning,
116:         // then the search item was not found.
117:         return -1;
118:     }

120:     public void removeAt(int index)
121:     {
122:         // # Make sure the index is valid for the current array
123:         if (index >= 0 && index < arrayListLength)
124:         {
125:             // Shift down all items after the given index
126:             for (int i = index; i < arrayListLength - 1; ++i)
127:             {
128:                 arrayData[i] = arrayData[i + 1];
129:             }

131:             // Update the array's length
132:             --arrayListLength;
133:         }
134:     }

136:     public void print()
137:     {
138:         for (int i = 0; i < arrayListLength; ++i)
139:         {
140:             System.out.print(arrayData[i] + " ");
141:         }
142:     }

144:     public void printInfo()
145:     {
146:         System.out.print("Allocation size: " + arrayData.length);
147:         System.out.print(", length: " + arrayListLength);
148:     }
149: }