Список: LinkedList & ArrayList

<aside> ❗ Пользоваться коллекциями стандартной библиотеки нельзя.

</aside>

Ваша задача в этой практике - переписать List в С++, используя шаблонные классы ArrayList<T> и LinkedList<T>. К сожалению, при использовании шаблонов, мы не можем использовать виртуальные функции, поэтому у нас не будет базового интерфейса IList.

Благодаря использованию шаблонов, мы сможем хранить в структуре данных List объекты любых типов, а не только int, как было ранее.

Но, раз мы стали использовать C++, то конечно же нам надо воспользоваться всеми его фичами:

1. Конструкторы копирования. (TODO: добавить тест, что копирвание связного списка копирует данные)
2. Конструктор, который создает список, сразу заполненный элементами, например ArrayList<int> arr = {1,2,3,4,5,6,7,8,9}; (См std::initializer_list<Q>)
3. Конструктор для ArrayList, который создает пустой массив, НО с заданной capacity. Повышает эффективность использования ArrayList: нам не нужно делать копирования даных, когда capacity исчерпает себя.
4. Оператор [], вместо функции T Get(int index). Если промазали по индексу, то надо выбрасывать исключение.
5. Все функции из реализации для Си должны быть методами класса:
   1. public доступом, если это функции для работы с самой абстракцией списка
   2. private доступом - если это ваши вспомогательные методы (типа копирования куска памяти).
6. Деструкторы, которые чистят память.
7. Поддержка range-based-for, чтобы вашим листом можно было пользоваться следующим образом:

LinkedList<int> list = {1,2,3,4,5,6,7,8,9}; 
for (auto& element: list) {
	cout << element << " ";
}
// Выведет
// 1 2 3 4 5 6 7 8 9 

8. Методы begin и end, как у std::vector. А у LinkedList вам еще придется создать класс итератор.:

typedef<typename T>
class LinkedList {
    public:
        class iterator {
            public:
                typedef T value_type;
                typedef std::forward_iterator_tag iterator_category;
                typedef int difference_type;
                
                // конструктор
                iterator(T* ptr) : ptr_(ptr) { }
                
                iterator operator++();
                iterator operator++(int junk);
                T& operator*();
                T* operator->();
                bool operator==(const iterator& rhs);
                bool operator!=(const iterator& rhs);
        };

};

LinkedList<int> list = {1,2,3,4,5,6,7,8,9}; 
for (auto el = list.begin(); el != list.end(); e++) {
  cout << *el << " ";
}
// Выведет
// 1 2 3 4 5 6 7 8 9