Список — это структура данных, где элементы идут один за другим. Хотя добавлять и удалять элементы легко, доступ к ним медленный.
Это схематичное изображение. В нем три блока данных: синий, желтый и красный. Они обозначены как Blue, Yellow и Red. Каждый блок имеет указатель (pointer), который показывает на следующий блок в памяти.
Данные в списках не обязаны занимать смежные участки памяти.
Поскольку данные хранятся по частям, доступ к каждой из них возможен только путем последовательного обхода всех указателей. Это называется последовательным, или секвенциальным, доступом. Например, чтобы получить доступ к красному блоку Red, сначала нужно обратиться к синему блоку Blue, потом к блоку Yellow.
Вставить элемент в список легко. Нужно лишь перенаправить указатели до и после вставляемого элемента. Например, можно добавить новый зеленый блок Green между синими (Blue) и желтыми (Yellow).
Добавление данных завершается перестановкой указателей с Blue на Green и с Green на Yellow.
Чтобы удалить данные, нужно изменить поле указателя. Например, если нужно убрать блок Yellow, достаточно поменять поле указателя зеленого блока с Yellow на Red. Block Yellow останется в памяти, но к нему будет невозможно получить доступ.
Когда эта область потребуется снова, она будет перезаписана и использована повторно.
Как обстоят дела со временем вычислений при работе со списками?
Рассмотрим данные, хранящиеся в списке. Обозначим их количество как n. Если мы начинаем поиск с начала списка (линейный поиск), то доступ к последним данным займет O(n) времени. Однако добавление новых данных в список происходит за постоянное время O(1), независимо от n. Это связано с тем, что для добавления нужно обновить только два указателя. Важно, чтобы позиция для добавления была известна заранее. Аналогично, удаление данных из списка также выполняется за O(1) времени.
В стандартном списке каждый элемент имеет один указатель. Однако можно создать двунаправленный список с двумя указателями: на предыдущий и последующий элементы. Это удобно, так как список можно просматривать как с начала, так и с конца.
Однако у двунаправленных списков есть недостаток: количество указателей удваивается, что требует больше памяти для хранения данных. Кроме того, при вставке или удалении элементов нужно переназначить вдвое больше указателей.
Примеры с обычным списком (list) в Python
В Python встроенный тип list — это динамический массив, а не связный список. Он хранит элементы подряд в памяти, поэтому:
- доступ по индексу быстрый (O(1)),
- но вставка и удаление в середине требует сдвига элементов (O(n)).
colors = ["Blue", "Yellow", "Red"]
print(colors)
colors.insert(1, "Green") # вставляем в позицию 1
print(colors)
colors.remove("Yellow") # удаляем по значению
print(colors)
colors.append("Black") # Добавление в конец
print(colors)Пример связного списка на Python в виде класса
# Узел связного списка
class Node:
def __init__(self, data):
self.data = data # значение
self.next = None # указатель на следующий элемент
# Создаем список Blue -> Yellow -> Red
blue = Node("Blue")
yellow = Node("Yellow")
red = Node("Red")
blue.next = yellow
yellow.next = red
# Обход списка
current = blue
while current:
print(current.data)
current = current.next