JAVA   16

ArrayList

Guest on 11th May 2022 04:35:40 PM

  1. // Class ArrayList<E> can be used to store a list of values of type E.
  2.  
  3. import java.util.*;
  4.  
  5. public class ArrayList<E> {
  6.     private E[] elementData; // list of values
  7.     private int size;        // current number of elements in the list
  8.  
  9.     public static final int DEFAULT_CAPACITY = 100;
  10.  
  11.     // post: constructs an empty list of default capacity
  12.     public ArrayList() {
  13.         this(DEFAULT_CAPACITY);
  14.     }
  15.  
  16.     // pre : capacity >= 0 (throws IllegalArgumentException if not)
  17.     // post: constructs an empty list with the given capacity
  18.     @SuppressWarnings("unchecked")
  19.     public ArrayList(int capacity) {
  20.         if (capacity < 0) {
  21.             throw new IllegalArgumentException("capacity: " + capacity);
  22.         }
  23.         elementData = (E[]) new Object[capacity];
  24.         size = 0;
  25.     }
  26.  
  27.     // post: returns the current number of elements in the list
  28.     public int size() {
  29.         return size;
  30.     }
  31.  
  32.     // pre : 0 <= index < size() (throws IndexOutOfBoundsException if not)
  33.     // post: returns the value at the given index in the list
  34.     public E get(int index) {
  35.         checkIndex(index);
  36.         return elementData[index];
  37.     }
  38.  
  39.     // post: creates a comma-separated, bracketed version of the list
  40.     public String toString() {
  41.         if (size == 0) {
  42.             return "[]";
  43.         } else {
  44.             String result = "[" + elementData[0];
  45.             for (int i = 1; i < size; i++) {
  46.                 result += ", " + elementData[i];
  47.             }
  48.             result += "]";
  49.             return result;
  50.         }
  51.     }
  52.  
  53.     // post : returns the position of the first occurrence of the given
  54.     //        value (-1 if not found)
  55.     public int indexOf(E value) {
  56.         for (int i = 0; i < size; i++) {
  57.             if (elementData[i].equals(value)) {
  58.                 return i;
  59.             }
  60.         }
  61.         return -1;
  62.     }
  63.  
  64.     // post: returns true if list is empty, false otherwise
  65.     public boolean isEmpty() {
  66.         return size == 0;
  67.     }
  68.  
  69.     // post: returns true if the given value is contained in the list,
  70.     //       false otherwise
  71.     public boolean contains(E value) {
  72.         return indexOf(value) >= 0;
  73.     }
  74.  
  75.     // post: appends the given value to the end of the list
  76.     public void add(E value) {
  77.         ensureCapacity(size + 1);
  78.         elementData[size] = value;
  79.         size++;
  80.     }
  81.  
  82.     // pre : 0 <= index <= size() (throws IndexOutOfBoundsException if not)
  83.     // post: inserts the given value at the given index, shifting subsequent
  84.     //       values right
  85.     public void add(int index, E value) {
  86.         if (index < 0 || index > size) {
  87.             throw new IndexOutOfBoundsException("index: " + index);
  88.         }
  89.         ensureCapacity(size + 1);
  90.         for (int i = size; i >= index + 1; i--) {
  91.             elementData[i] = elementData[i - 1];
  92.         }
  93.         elementData[index] = value;
  94.         size++;
  95.     }
  96.  
  97.     // pre : 0 <= index < size() (throws IndexOutOfBoundsException if not)
  98.     // post: removes value at the given index, shifting subsequent values left
  99.     public void remove(int index) {
  100.         checkIndex(index);
  101.         for (int i = index; i < size - 1; i++) {
  102.             elementData[i] = elementData[i + 1];
  103.         }
  104.         elementData[size - 1] = null;
  105.         size--;
  106.     }
  107.  
  108.     // pre : 0 <= index < size() (throws IndexOutOfBoundsException if not)
  109.     // post: replaces the value at the given index with the given value
  110.     public void set(int index, E value) {
  111.         checkIndex(index);
  112.         elementData[index] = value;
  113.     }
  114.  
  115.     // post: list is empty
  116.     public void clear() {
  117.         for (int i = 0; i < size; i++) {
  118.             elementData[i] = null;
  119.         }
  120.         size = 0;
  121.     }
  122.  
  123.     // post: appends all values in the given list to the end of this list
  124.     public void addAll(ArrayList<E> other) {
  125.         ensureCapacity(size + other.size);
  126.         for (int i = 0; i < other.size; i++) {
  127.             add(other.elementData[i]);
  128.         }
  129.     }
  130.  
  131.     // post: returns an iterator for this list
  132.     public Iterator<E> iterator() {
  133.         return new ArrayListIterator();
  134.     }
  135.  
  136.     // post: ensures that the underlying array has the given capacity; if not,
  137.     //       the size is doubled (or more if given capacity is even larger)
  138.     public void ensureCapacity(int capacity) {
  139.         if (capacity > elementData.length) {
  140.             int newCapacity = elementData.length * 2 + 1;
  141.             if (capacity > newCapacity) {
  142.                 newCapacity = capacity;
  143.             }
  144.             elementData = Arrays.copyOf(elementData, newCapacity);
  145.         }
  146.     }
  147.  
  148.     // post: throws an IndexOutOfBoundsException if the given index is
  149.     //       not a legal index of the current list
  150.     private void checkIndex(int index) {
  151.         if (index < 0 || index >= size) {
  152.             throw new IndexOutOfBoundsException("index: " + index);
  153.         }
  154.     }
  155.  
  156.     private class ArrayListIterator implements Iterator<E> {
  157.         private int position;           // current position within the list
  158.         private boolean removeOK;       // whether it's okay to remove now
  159.  
  160.         // post: constructs an iterator for the given list
  161.         public ArrayListIterator() {
  162.             position = 0;
  163.             removeOK = false;
  164.         }
  165.  
  166.         // post: returns true if there are more elements left, false otherwise
  167.         public boolean hasNext() {
  168.             return position < size();
  169.         }
  170.  
  171.         // pre : hasNext() (throws NoSuchElementException if not)
  172.         // post: returns the next element in the iteration
  173.         public E next() {
  174.             if (!hasNext()) {
  175.                 throw new NoSuchElementException();
  176.             }
  177.             E result = elementData[position];
  178.             position++;
  179.             removeOK = true;
  180.             return result;
  181.         }
  182.  
  183.         // pre : next() has been called without a call on remove (throws
  184.         //       IllegalStateException if not)
  185.         // post: removes the last element returned by the iterator
  186.         public void remove() {
  187.             if (!removeOK) {
  188.                 throw new IllegalStateException();
  189.             }
  190.             ArrayList.this.remove(position - 1);
  191.             position--;
  192.             removeOK = false;
  193.         }
  194.     }
  195. }

Raw Paste


Login or Register to edit or fork this paste. It's free.