Простая реализация списка на базе массива:
- Храним сам массив элементов (
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;
}
}
}