Создание динамического массива в Java без использования коллекции
Меня спросили в интервью: «Как создать динамический массив без использования какой-либо коллекции, такой как ArrayList, vector и т.
Я сказал, что это невозможно, поскольку массив имеет фиксированный размер. Они сказали, что нет, возможно, вам нужно написать программу, чтобы ответить на этот вопрос.
Я не смог ответить на этот вопрос. Они дали мне одну подсказку «использовать дженерики», хотя мне кажется очень трудным ответить на этот вопрос. Кто-нибудь может мне помочь?
4 ответа
Реализация Коллекций использует похожую концепцию. Вам нужно определить общий массив с default_size, скажем, n = 10 (скажем), и по умолчанию load_factor = 0.75 (скажем)
И переменная index для хранения текущей позиции в массиве.
когда index > n*load_factor создайте новый массив большего размера и скопируйте в него все элементы, и это будет ваш новый массив, аналогично при удалении элемента index < n*load_factor (эти критерии зависят от многих параметров, это всего лишь пример) уменьшают размер массива.
Частичный пример кода
Что такое динамический массив в Java? Вот концептуальный пример: Мы хотим хранить данные в массиве, но не знаем, насколько они будут большими. Поэтому, когда мы хотим вставить, и нет места, нам нужно найти больший блок памяти и скопировать все записи в этом блоке. Теперь рассмотрим два способа сделать это.
Плохой способ
Мы выделяем блок из 1000 записей.
Каждый раз, когда нет ‘ В достаточном количестве места мы выделяем новый блок с еще 100 записями.
Сколько времени это займет:
Чтобы вставить n записей, количество копий будет 1000 × К + 100 × (1 + 2 + , , , + ( К — 1)) = 1000 к + 50 к (к-1) Следовательно, занимаемое время является квадратичным по k, а также по n.
Хороший способ
Выделите блок из 1000 записей, а при нехватке места выделите новый блок в два раза больше.
Сколько времени это займет
Общее количество копий: 1000 × (1 + 2 + 4 + ··· + 2 ^ ( К — 1) ) = 1000 × (2 ^ к — 1) & Л; = п
Общее количество вставок: 1000 × (1 + 1 + 2 + 4 + ··· + 2 ^ ( К — 1) ) = 1000 × 2 ^ к = п
Таким образом, общее время линейно по n, а среднее время постоянно.
Когда вы поймете эту концепцию, вы сможете создать динамический массив на любом языке, который вы знаете.
У меня есть идея для вашего вопроса. Динамический массив — это то, что меняет свой размер во время выполнения. Я только что закончил двенадцатый класс и делюсь тем, что пришло мне в голову .
Вы можете скопировать все значения в текущем массиве во временный массив и добавить новое значение в массив, которое может увеличить размер массива. Вы также можете увеличить размер по мере необходимости.
Надеюсь, это поможет .
Они в основном хотели кое-что узнать. Например, как бы вы смоделировали «Держатель» для такого массива, как бы вы сделали общедоступным get(int index) или set(T value, int index) или size .
«Использовать дженерики» было очень хорошим советом, так как вы должны были начать хотя бы с:
Если вы записали это, они могли бы также спросить, почему бы не T[] array = new T[10] , и вы должны были сказать, что не можете создать универсальный массив в Java (вы могли бы даже упомянуть @SafeVarArgs ). Далее вы должны были сказать, что массивы ковариантны и что приведение разрешено для массивов, но не для коллекций; также это сгенерирует предупреждение компилятора, которое вам нужно подавить.
Позже вы могли бы добавить метод, например add(T value) и как это реализовать. Здесь они ожидали, что вы знаете, что Arrays.copyOfRange или System.arrayCopy и как это работает ,
Они могли бы даже спросить, почему бы не добавить все подтипы T и правильный синтаксис для этого ( look for generics bounds )
Вам также может понадобиться подумать о том, как delete элемента будет работать с определенным индексом? Не могли бы вы null ? Вы бы удалили это? Если так, как бы вы сделали это из массива? Вы бы сократили размер массива, когда что-то будет удалено? (подсказка: коллекции java этого не делают, если вы не укажете им явно: ArrayList#trimToSize() )
Когда ваш внутренний массив заполнен и вы хотите добавить еще один элемент, на сколько вы его расширите? 50% , 75% ? Или достаточно места для одного элемента? Если бы вы знали, как работают внутренние коллекции jdk, ответ был бы очень простым.
Как создать двухмерный динамический массив на Java?
Как создать динамический двухмерный массив?
Количество элементов в массиве не известно и оно может изменяться.
Как создать двухмерный динамический массив типа double
Погуглил, посмотрел на форуме, нашёл способ создания квадратной матрицы, а вот MxN не нашёл( .
Создать двухмерный динамический массив
Создать двухмерный динамический массив, имея следующее описание const n = 100; type mas = array.
Создать двухмерный динамический массив строк
Ввести 2-мерный массив. Количество строк и столбцов заранее неизвестно. Признаком конца ввода.
Сообщение от Skazitel
Сообщение от Skazitel
mik-a-el, ну. я не думаю, что тут есть, что оценивать, кроме чесания левой рукой правого уха. с огромныит потерями в памяти.
Xentar, Спасибо!
Добавлено через 16 минут 36 секунд
Сообщение от Xentar
Сообщение от Freezer
это ты имел ввиду?
Добавлено через 4 минуты 10 секунд
Xardas красава молодца! хорошую работу проделал=)))если не против возьму и себе в пользование вдруг пригодится))))если ты не против естессно)
Сообщение от Mecid
Кстати, а что эффективнее: приводить постоянно объект к нужному типу, или ввести переменную нужного класса, которая будет ссылаться на этот объект (строки 6, 7, 8, 14)?
Ну и еще задам тогда вопросик.
В строчке 6 последнего листинга я использую статический метод equals() класса Arrays. Насколько правомочно здесь его использование? Ведь он, по идее, сравнивает все элементы двух входных массивов. А у меня одномерный массив массивов типа double. Каким образом он (метод equals() класса Arrays) будет сравнивать соответствующие массивы? Аналогичным ли образом (путем вызова метода equals() класса Arrays)? И не получится ли здесь банальное сравнение адресов, которые для разных матриц, естественно, будут разными.
Или теперь, когда я добавил код поэлементного сравнения (строки 11-15), эту строку вообще можно исключить? А если они эквивалентны (по результату), то что эффективнее?
Изучаем Java
Массив — это структура данных, в которой хранятся величины одинакового типа. Доступ к отдельному элементу массива осуществляется с помощью целого индекса. Например, если а — массив целых чисел, то значение выражения а [ i ] равно i-му целому числу в массиве.
Массив объявляется следующим образом: сначала указывается тип массива, т.е тип элементов, содержащихся в массиве, за которым ставится пара пустых квадратных скобок, а затем — имя переменной. Например, вот как объявляется массив, состоящий из целых чисел:
int[] a;
Однако этот оператор лишь объявляет переменную а, не инициализируя ее настоящим массивом. Чтобы создать массив, нужно применить оператор new.
Этот оператор создает массив, состоящий из 100 целых чисел. Элементы этого массива нумеруются от 0 до 99 (а не от 1 до 100). После создания массив можно заполнять, например, с помощью цикла.
int [ ] а = new int[100];
for (int i = 0; i < 100; i++)
a[i] = i; // Заполняет массив числами от 0 до 99.
Если вы попытаетесь обратиться к элементу а [100] (или любому другому элементу, индекс которого выходит за пределы диапазона от 0 до 99), создав массив, состоящий из 100 элементов, программа прекратит работу, поскольку возникнет исключительная ситуация, связанная с выходом индекса массива за пределы допустимого диапазона.
Чтобы подсчитать количество элементов в массиве, используйте метод имяМасси-
ва.length.
for (int i = 0; i < a. length; i++ System.out.println (a[i]);
После создания массива изменить его размер невозможно (хотя можно, конечно, изменять отдельные его элементы). Если в ходе выполнения программы необходимо часто изменять размер массива, лучше использовать другую структуру данных, называемую списком массивов (array list).
Массив можно объявить двумя способами:
Большинство программистов на языке Java предпочитают первый стиль, поскольку в нем четче отделяется тип массива int [ ] (целочисленный массив) от имени переменной.
Инициализаторы массивов и безымянные массивы
В языке Java есть средство для одновременного создания массива и его инициализации. Вот пример такой синтаксической конструкции:
Отметим, что в этом случае не нужно применять оператор new. Кроме того, можно даже инициализировать безымянный массив:
Это выражение выделяет память для нового массива и заполняет его числами, указанными в фигурных скобках. При этом подсчитывается их количество и, соответственно, определяется размер массива. Эту синтаксическую конструкцию удобно применять для повторной инициализации массива без образования новой переменной. Например, выражение
smallPrimes = new int;
представляет собой укороченную запись выражения
int[] anonymous = ;
smailPrimes = anonymous;
Можно создать массив нулевого размера. Такой массив может оказаться полезным при написании метода, вычисляющего некий массив, который оказывается пустым. Массив нулевой длины объявляется следующим образом:
Заметим, что такой массив не эквивалентен объекту null.
Копирование массивов
Один массив можно скопировать в другой, но при этом обе переменные будут ссылаться на один и тот же массив.
int[] luckyNumbers = smailPrimes;
luckyNuimbers[5] = 12; // Теперь элемент smailPrimes[5]также равен 12.
Результат показан на рис. 3.14. Если необходимо скопировать все элементы одного массива в другой, следует использовать метод arraycopy из класса System. Его вызов выглядит следующим образом:
System.arraycopy(from, fromlndex, to, tolndex, count);
Массив to должен иметь достаточный размер, чтобы в нем поместились все копируемые элементы.
Рис. 3.14. Копирование массива
Например, показанные ниже операторы, результаты работы которых изображены на рис. 3.15, создают два массива, а затем копируют последние четыре элемента первого массива во второй. Копирование начинается со второй позиции в исходном массиве, а копируемые элементы помещаются в целевой массив, начиная с третьей позиции.
int[] smailPrimes = ;
int[] luckyNumbers = ;
System.аггаусору(smailPrimes, 2, luckyNumbers, 3, 4);
for (int i = 0; i < luckyNumbers.length; i++)
System.println(i +.»: » + luckyNumbersfi]);
Выполнение этих операторов приводит к следующему результату.
Рис. 3.15. Копирование элементов массива
Массив в языке Java значительно отличается от массива в языке C++. Однако он практически совпадает с указателем на динамический массив. Это значит, что оператор
int[] a = new int[100]; //Java
эквивалентен оператору
i n t * = new i n t [ 1 0 0 ] ; // C++,
а не
int a[100]; // C++
В языке Java оператор [ ] no умолчанию проверяет диапазон изменения индексов. Кроме того, в языке Java нет арифметики указателей — нельзя увеличить указатель а, чтобы обратиться к следующему элементу массива.
Реализация динамического массива на java
Как создать свой динамический массив на Java, с использованием SET ?
Эти статьи: первая и вторая могут Вам помочь.
Set предназначен для хранения уникальных элементов, посему использовать его в этом случае нецелесообразно. Лучше использовать List для хранения данных.
Если проанализировать функционал, то можно выделить следующие ключевые функции массива:
- возможность создать массив любого типа
- возможность указать размерность массива
- возможность для каждого элемента получить значение и изменить значение
- возможность изменять размерность массива (явно или автоматически)
В результате получается что-то эдакое:
Вот вам и минимальная реализация, можете добавить любой нужный вам функционал.