Связный список — линейная, однородная , элементарная структура данных, предназначенная для хранения данных одного ии того же типа, в которой порядок объектов определяется указателями.
В отличие от массива, связный список хранит элементы не обязательно последовательно. Данным свойством и обосновано название “Связный список”, поскольку при помощи указателей данные связываются в единое целое. У связного списка принято различать концевые элементы: головой называют начальный элемент списка, хвостом — конечный.
Односвязный список — связный список, в котором каждый из элементов списка содержит указатель непосредственно на следующий элемент.
Двусвязный список — связный список, в котором каждый из элементов содержит указатель как на следующий элемент списка, так и на предыдущий.
Достоинства : 1. позволяет итерироваться по элементам списка в обоих направлениях.
Кольцевой список — связный список, в котором последний элемент ссылается на первый.
Достоинства : 1. возможность просмотра всех элементов списка, начиная с произвольного
2. быстрый доступ к первому и последнему элементам (если реализован на двусвязном списке)
Двумя наиболее частыми операциями над списками являются индексация и присваивание на заданную позицию. Обе они занимают равное количество времени, вне зависимости от того, насколько велик список. Когда операции не зависят от размера списка (как названные выше), говорят, что они имеют O(1)
def test1(): # t = 6.54352807999 ms
l = []
for i in range(1000):
l = l + [i]
def test2(): # t = 0.306292057037 ms
l = []
for i in range(1000):
l.append(i)
def test3(): # t = 0.147661924362 ms
l = [i for i in range(1000)]
def test4(): # t = 0.0655000209808 ms
l = list(range(1000))
Эффективность операторов для списков в Python в терминах нотации “большое О”
