Создание пользовательской коллекции (алгоритмы добавления и удаления элемента коллекции)


#1

Какие есть актуальные алгоритмы для написания методов Add и Remove? Если можно, то также напишете их преимущества и недостатки. Заранее спасибо!


#2

1 вариант:

при добавлении элемента в коллекцию увеличивать размер массива (где хранятся элементы) на 1 и новый элемент добавлять в самый конец
при удалении элемента из коллекции: уменьшать размер массива на 1

2 вариант:

при добавлении элемента в коллекции вместо того, что бы увеличивать размер массива на 1 увеличивать его, например, на 10 и следующее увеличение размера массива проводить после заполнения всех свободных ячеек

при удалении: удалять элемент и производить перемещение элементов так, что бы все они шли от начала и до конца (не было пустых ячеек). Уменьшение размера массива требует доп. логики (например, если кол. элементов 154, а массив размером 170, то возможно нужно уменьшить его размер до 160 и т.д.)

примечание: при этом алгоритме свойство Count не должно возвращать размер массива, а должно вернуть именно количество существующих элементов в нём (для этого проще всего создать отдельное поле и при добавлении элемента инкрементировать его, а при удалении декрементировать)


1й вариант лёгок в реализации, но при этом требует частого пересоздания массива
2й вариант уменьшает количество пересозданий массива, но при этом требует дополнительных проверок, могут возникать ситуации, что ещё есть свободные места в массиве, но при этом в них нет нужды


#3

2й предложенный Вами вариант также можно немного изменить, вместо того, что бы сдвигать элементы после удаления оставить всё как есть, а следующий элемент для добавления поместить на 1е постое место в массиве, например если у Вас есть такой массив:

{1, 2, 3, 4, 5, -, - , -} // - обозначает, что элемент пустой

после удаления 3 из массива оставить то место пустым:

{1, 2, -, 4, 5, -, - , -}

а при добавлении следующего элемента (например, 76) подставить его на 1е встреченное пустое место, то есть выйдет:

{1, 2, 76, 4, 5, -, - , -}

Сдвигать же элементы в таком случае нужно лишь в при уменьшении размера массива.


#4

спасибо всем!