Как можно с нуля реализовать list?

1️⃣ Как кратко ответить

Реализовать list с нуля можно с помощью динамического массива. Начинаем с выделения фиксированного размера памяти, добавляем элементы, увеличивая размер массива при необходимости. При превышении текущей емкости создаем новый массив большего размера, копируем элементы и освобождаем старую память.

2️⃣ Подробное объяснение темы

Реализация списка с нуля требует понимания того, как работают динамические массивы. В Python встроенный тип list реализован как динамический массив, который позволяет хранить элементы в непрерывном блоке памяти и изменять его размер по мере необходимости.

Зачем это нужно

Списки — это фундаментальная структура данных, используемая для хранения упорядоченных коллекций элементов. Они позволяют быстро получать доступ к элементам по индексу и эффективно добавлять или удалять элементы.

Как это работает

1. Инициализация: Начинаем с выделения памяти для фиксированного количества элементов. Это начальная емкость списка.

2. Добавление элементов: При добавлении нового элемента проверяем, есть ли свободное место. Если да, добавляем элемент. Если нет, увеличиваем емкость.

3. Увеличение емкости: Когда текущая емкость исчерпана, создаем новый массив большего размера (обычно в 2 раза больше), копируем в него элементы из старого массива и освобождаем старую память.

4. Удаление элементов: Удаление элемента требует сдвига всех последующих элементов влево, чтобы заполнить образовавшуюся пустоту.

Пример реализации

class CustomList:
    def __init__(self):
        # Изначально выделяем память для 4 элементов
        self.capacity = 4
        self.size = 0
        self.data = [None] * self.capacity
​
    def append(self, item):
        # Проверяем, есть ли место для нового элемента
        if self.size == self.capacity:
            # Увеличиваем емкость вдвое
            self._resize(2 * self.capacity)
 ​       
        # Добавляем элемент в конец
        self.data[self.size] = item
        self.size += 1
​
    def _resize(self, new_capacity):
        # Создаем новый массив с увеличенной емкостью
        new_data = [None] * new_capacity
        # Копируем элементы из старого массива в новый
        for i in range(self.size):
            new_data[i] = self.data[i]
        # Обновляем ссылку на новый массив и емкость
        self.data = new_data
        self.capacity = new_capacity
​
    def remove(self, index):
        # Проверяем, что индекс в пределах текущего размера
        if 0 <= index < self.size:
            # Сдвигаем элементы влево, начиная с удаляемого
            for i in range(index, self.size - 1):
                self.data[i] = self.data[i + 1]
            # Уменьшаем размер
            self.size -= 1
            # Обнуляем последний элемент
            self.data[self.size] = None
        else:
            raise IndexError("Index out of range")
​
    def __getitem__(self, index):
        # Возвращаем элемент по индексу
        if 0 <= index < self.size:
            return self.data[index]
        else:
            raise IndexError("Index out of range")
​
    def __len__(self):
        # Возвращаем количество элементов в списке
        return self.size

• __init__: Инициализирует список с начальной емкостью 4.
• append: Добавляет элемент в конец списка, увеличивая емкость при необходимости.
• _resize: Увеличивает емкость массива, создавая новый массив и копируя в него элементы.
• remove: Удаляет элемент по индексу, сдвигая последующие элементы влево.
• __getitem__: Возвращает элемент по индексу.
• __len__: Возвращает текущее количество элементов в списке.