Реализация своего ArrayList

#java

Здравствуйте,есть задача написать свою коллекцию,но не понимаю как подойти к этому,как
создать динамический массив в котором будут храниться все данные?
    

Ответы

Ответ 1

Основные методы и логика масштабирования внутреннего массива в обе стороны:

public class MyArrayList {
   private final int INIT_SIZE = 16;
   private final int CUT_RATE = 4;
   private Object[] array = new Object[INIT_SIZE];
   private int pointer = 0;

   /*
   Добавляет новый элемент в список. При достижении размера внутреннего
   массива происходит его увеличение в два раза.
   */
   public void add(T item) {
     if(pointer == array.length-1)
        resize(array.length*2); // увеличу в 2 раза, если достигли границ
     array[pointer++] = item;
   }

   /*
   Возвращает элемент списка по индексу.
   */
   public T get(int index) {
      return (T) array[index];
   }

   /*
   Удаляет элемент списка по индексу. Все элементы справа от удаляемого 
   перемещаются на шаг налево. Если после удаления элемента количество    
   элементов стало в CUT_RATE раз меньше чем размер внутреннего массива, 
   то внутренний массив уменьшается в два раза, для экономии занимаемого 
   места.
   */
   public void remove(int index) {
      for (int i = index; i INIT_SIZE && pointer < array.length / CUT_RATE) 
         resize(array.length/2); // если элементов в CUT_RATE раз меньше чем 
                                 // длина массива, то уменьшу в два раза
   }
   /*Возвращает количество элементов в списке*/
   public int size() {
      return pointer;
   }

   /*Вспомогательный метод для масштабирования.*/
   private void resize(int newLength) {
      Object[] newArray = new Object[newLength];
      System.arraycopy(array, 0, newArray, 0, pointer);
      array = newArray;
   }      
}


Ответ 2

Для начала, прочитайте про Обобщения(Generics) в Java - это нужно для того, чтобы
понять, как сделать коллекцию для любого типа. 

Позже, на основании массива (ведь ArrayList и реализован на основе массива) сделайте
динамическое расширение массива при достижении максимальной длины. Делается это в двух
словах так: 


Проверяете при добавлении не последний ли это элемент в массиве? 
Если true -> создаете новый массив с бОльшим размером, чем в текущем, копируете содержимое
текущего массива, а затем подменяете ссылки на массивы.


Таким же образом можно создавать динамически расширяемые стэки, очереди, etc.

Если нужны коллекции не на основе массива - смотрите в сторону LinkList или Tree,
в интернете есть масса статей, как сделать свою коллекцию на основании LinkList или Tree.

p.s. Если нужно - есть исходники с LinkList и Tree, которые мы проходили в универе ;)

upd. Исходники с некоторыми объяснениями на list и tree.


Ответ 3

Если не знаете как решить задачу целиком разбейте ее на подзадачи:


Создайте класс обертку для обычного массива
Реализуйте методы добавления, удаления и пр. Если вы хотите создать "честную" коллекцию,
то нужно реализовать интерфейс java.util.Collection или java.util.List
Реализуйте динамическое увеличение размера, если в массиве не хватает места для следующего
элемента. Это делается, обычно, созданием нового массива большего размера и копированием
в него элементов из старого.
Добавьте дженерики.


Ответ 4

Можно сделать имплементацию (реализация интерфейса) от List к своему классу, который
реализует коллекцию типа ArrayList, чтобы не забыть реализовать нужные тебе методы.