Hello, there is a task to write my collection, but I don’t understand how to approach this, how to create a dynamic array in which all data will be stored?

  • one
    I also advise you to see the native implementation of grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… . Only, since this is a task for learning purposes - the point is not to copy it, but to understand it and figure it out - markov
  • Thanks, it seems like "Ice has broken", the collections cannot be used, I solved the problem with an array like this: - I declared an array of Object type in the class (without initialization) in the add method I made the String variable where I add all the data through the space, and then through split (" ") add everything to the array. Tell me, is this a normal solution? - Seryoga
  • Well, this is a solution, but, of course, it is more a crutch, not universal, shorter than bad. No need to use collections, you can simply use c-style arrays, they are used in fact by Java. If they cannot be used, then you need to implement such a thing as a linked list. Here each element stores a link to the previous and next, and the licht stores a link to the end and the beginning. But it is more complicated and I think that it is the implementation of the ArrayList - markov type that is expected from you

4 answers 4

The main methods and logic of scaling the internal array in both directions:

public class MyArrayList<T> { 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<pointer; i++) array[i] = array[i+1]; array[pointer] = null; pointer--; if (array.length > 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; } }

    For starters, read about Generics in Java - this is needed in order to understand how to make a collection for any type.

    Later, based on the array (after all, ArrayList is implemented on the basis of the array) make a dynamic expansion of the array when the maximum length is reached. This is done in a nutshell like this:

    1. Do you check when adding the last element in the array?
    2. If true -> create a new array with a larger size than the current one, copy the contents of the current array, and then substitute references to the arrays.

    In the same way, you can create dynamically expandable stacks, queues, etc.

    If collections are not based on an array, look to LinkList or Tree, there are lots of articles on the Internet on how to make your collection based on LinkList or Tree.

    ps If you need to - there are source codes with LinkList and Tree, which we went through in the university;)

    upd. Sources with some explanations on list and tree.

    • one
      ps Если нужно - есть исходники... - well, then post them! Meaning instead of the code itself to give any guarantees for its provision? Well, or remove this curiosity-provoking postscript. - ߊߚߤߘ
    • @Arhad added link, you can read. - Ep1demic

    If you do not know how to solve the problem entirely, break it into subtasks:

    1. Create a wrapper class for a regular array
    2. Implement add, remove, and other methods. If you want to create an "honest" collection, then you need to implement the java.util.Collection or java.util.List interface
    3. Implement a dynamic increase in size if there is not enough space in the array for the next item. This is usually done by creating a larger new array and copying elements from the old one into it.
    4. Add generics.

      You can make implementation (interface implementation) from List to your class, which implements an ArrayList collection, so as not to forget to implement the methods you need.