Реализация метода Remove для своей коллекции на базе массива

210

06 марта 2019, 06:10

Как реализовать для своей коллекции метод Remove(T item) (такой же, как в List<>), удаляющий указанный элемент, но не меняющий реальной емкости массива?

У меня есть коллекция и ее параметры:

T[] arreay = new T[5];
public int count;
public int size;
public void Insert(int index, T item)
{
    size++;
    T[] arr = new T[size];
    for (int i = 0; i < index; ++i)
    {
        arreay[i] = arr[i];
    }
    arreay[index] = item;
    for (int i = index + 1; i < size; ++i)
    {
        arreay[i] = arr[i];
    }
}

Answer 1

Простая реализация списка на базе массива:

Храним сам массив элементов (elemenets)
Храним реальное количество элементов в массиве (size). Это позволит не пересоздавать массив при вызове метода Remove, а также иметь изначально массив не нулевого размера и увеличивать размер массива "с запасом" (для упрощения в примере кода массив увеличивается только до требуемого размера)

Метод Insert(int index, T item):

Проверяет что index допустим
Проверяет что в массив войдёт ещё один элемент (size + 1) и, при необходимости, увеличивает размер массива
Сдвигает элементы в массиве от index до size вправо на одну позицию (index -> index + 1, ..., size - 1 -> size)
Добавляет новый элемент по индексу index
Увеличивает size на единицу

Метод Remove(T item):

Ищет первое вхождение item в массив
Если элемент найден (его index больше либо равен 0), то:
- Сдвигает элементы с index до size влево на одну позицию (index <- index + 1, ..., size - 1 <- size)
- Уменьшает size на единицу

Метод Add(T item) (в вопросе про него речь не шла, но он короткий и всё равно его пришлось писать для тестирования кода):

Проверяет что в массив войдёт ещё один элемент (size + 1) и, при необходимости, увеличивает размер массива
Добавляет новый элемент в конец массива (по индексу size)
Увеличивает size на единицу

Пример кода:

public class MyList<T>
{
    private T[] elements = new T[5];
    private int size = 0;
    public void Insert(int index, T item)
    {
        if (index < 0 || index >= size)
            throw new IndexOutOfRangeException($"Index: {index}, Size: {size}");
        EnsureCapacity(size + 1);
        for (var i = size; i > index; i--)
            elements[i] = elements[i - 1];
        elements[index] = item;
        size++;
    }
    public void Remove(T item)
    {
        var index = Array.IndexOf(elements, item, 0, size);
        if (index < 0)
            return;
        for (var i = index; i < size - 1; i++)
            elements[i] = elements[i + 1];
        size--;
    }
    public void Add(T item)
    {
        EnsureCapacity(size + 1);
        elements[size] = item;
        size++;
    }
    private void EnsureCapacity(int capacity)
    {
        if (elements.Length < capacity)
        {
            var arr = new T[capacity];
            Array.Copy(elements, arr, size);
            elements = arr;
        }
    }
}