Python-da siyahıya bənzər məlumat strukturu olmasaydı, onu necə həyata keçirərdiniz?

Mən onu dinamik massiv əsasında həyata keçirərdim.

Əsas prinsiplər:

1. Elementləri saxlamaq üçün sabit ölçülü massivdən istifadə etmək.
2. Massivin tutumu dolduqda, daha böyük ölçülü yeni massiv yaratmaq (adətən 1.5-2 dəfə böyük) və bütün elementləri ora köçürmək.
3. Mövcud elementlərin sayını saxlamaq.
4. Əlavə etmək, silmək, indekslə giriş, təkrarlama və uzunluğu müəyyən etmək üçün metodlar təmin etmək.

Əsas struktur nümunəsi:

class MyList:
    def __init__(self, capacity=10):
        self._capacity = capacity # Maksimum tutum
        self._size = 0           # Mövcud element sayı
        self._array = [None] * self._capacity # Daxili massiv

    def _resize(self, new_capacity):
        new_array = [None] * new_capacity
        for i in range(self._size):
            new_array[i] = self._array[i]
        self._array = new_array
        self._capacity = new_capacity

    def append(self, item):
        if self._size == self._capacity:
            self._resize(self._capacity * 2) # Ölçünü 2 dəfə artır
        self._array[self._size] = item
        self._size += 1

    def __len__(self):
        return self._size

    def __getitem__(self, index):
        if 0 <= index < self._size:
            return self._array[index]
        raise IndexError("indeks xaricində")

    def __setitem__(self, index, item):
        if 0 <= index < self._size:
            self._array[index] = item
        else:
            raise IndexError("indeks xaricində")

    def __iter__(self):
        for i in range(self._size):
            yield self._array[i]

    # Digər metodlar: insert, pop, remove, index və s. əlavə oluna bilər.

Bu yanaşmanın üstünlükləri:

• İndeksə görə giriş (get/set) orta hesabla O(1).
• Sonuna sürətli əlavə (append) orta hesabla O(1) (yaddaşın yenidən ayrılması xərclərinin amortizasiyası sayəsində).
• Təkrarlama O(n), burada n elementlərin sayı.

Çətinliklər və kompromisslər:

• Ortadakı elementlərin əlavə olunması və ya silinməsi O(n) vaxt alır.
• Yaddaşın yenidən ayrılması və köçürmə bahalı əməliyyatlar ola bilər, lakin nadir hallarda baş verir və çoxlu əlavə əməliyyatlarına paylanır (amortizasiya analizi).

list ilə tam analoq üçün, insert, pop, remove, index, dilimlər və s. çox sayda digər metodların da həyata keçirilməsi lazımdır, bu isə standart əməliyyatların səmərəliliyini qoruyur.