Учебные заметки: структуры данных и алгоритмы Python
Обзор
Связанные списки - это обычная и простая структура данных. Он определяется как набор узлов, которые вместе образуют линейную последовательность. Каждый узел в связанных списках содержит данные и ссылку на следующий узел в последовательности. Таким образом, порядок элементов данных не обеспечивается на основе их физического размещения в памяти. В качестве альтернативы каждый элемент имеет указатель на следующий узел.
Перемещение по узлам связанного списка называется перемещением . На изображении выше есть ссылка на член последовательности под названием head, который используется для идентификации первого узла в связанном списке. Некоторые приложения могут также ссылаться на другой элемент, называемый tail, чтобы идентифицировать последний узел списка, но его также можно распознать как последний узел, если в качестве следующей ссылки указать Нет.
Преимущества
- O (1) времени вставки и удаления в любой позиции в отличие от массивов, которые требуют O (n) для выполнения той же операции
- Могут непрерывно расширяться, без необходимости заранее указывать их размер.
Недостатки
- Доступ к элементу в списке осуществляется O (k), где k - это k-й элемент из заголовка.
Вставка узлов в связанные списки
Важной характеристикой связного списка является то, что он не имеет заранее определенного фиксированного размера, поэтому пространство пропорционально распределяется по его текущему количеству элементов. Если мы хотим вставить новый элемент в начало списка, процедура состоит из 4 шагов;
- Создание нового узла
- Установите его элемент на новый элемент
- Установите следующую ссылку нового узла для ссылки на текущую голову
- Затем установите заголовок списка так, чтобы он указывал на новый узел
Вставки также могут быть легко выполнены в конце связанных списков при условии, что во время процесса сохраняется ссылка на хвостовой узел. Эту вставку можно разбить на 4 этапа;
- Создание нового узла
- Присвойте следующей ссылке нового узла значение None
- Установите следующую ссылку текущего хвоста, чтобы указать на вновь созданный узел
- Обновите ссылку на хвост, чтобы она указывала на новый узел
Удаление узлов в связанных списках
Удаление элементов из заголовка односвязного списка - это практически операция, обратная вставке нового элемента в заголовок.
Напротив, удаление последнего узла немного сложнее. Чтобы удалить последний узел списка, мы должны иметь возможность получить доступ к узлу, который находится перед последним узлом - что возможно, если мы пройдем связанный список от заголовка к элементу n-1. Однако узел, который находится перед последним узлом, не может быть доступен по следующей ссылке из хвоста. Более эффективный способ поддержать такую операцию - сделать наш список двусвязным.
Пример односвязного списка в Python:
# Code Source: https://www.udemy.com/course/python-for-data-structures-algorithms-and-interviews/learn/lecture/3179640#overview # Example of simply linked list class Node(object): def __init__(self, value): self.value = value self.nextnode = None a = Node(1) b = Node(2) c = Node(3) # linking the nodes together a.nextnode = b b.nextnode = c print(b.value) >>>> 2 print(b.nextnode.value) >>>> 3
Двусвязные списки
Двусвязный список имеет явную ссылку на предыдущий узел, а также на следующий узел. В начало и конец списков добавляются специальные узлы, известные как заголовок и трейлер. Вместе фиктивные узлы известны как часовые. Это обобщение односвязного списка допускает большее количество операций обновления O (1), включая вставки и удаления.
Вставка узлов в двусвязные списки
Из-за контрольных узлов все вставки в двусвязный список происходят между парой существующих узлов. Например, когда новый элемент вставляется в начало последовательности, мы просто вставляем узел между заголовком и следующим узлом заголовка.
Удаление узлов в двусвязных списках
Для операций удаления предыдущий и следующий узлы удаленного элемента напрямую связаны друг с другом - эта операция удаляет узел, который мы хотим удалить из списка. Стражи позволяют удалить первый или последний элемент последовательности с той же реализацией.
Пример двусвязного списка в Python:
# Code Source: https://www.udemy.com/course/python-for-data-structures-algorithms-and-interviews/learn/lecture/3179640#overview # Example of doubly linked list class Node(object): def __init__(self, value): self.value = value self.nextnode = None self.prevnode = None a = Node(1) b = Node(2) c = Node(3) # linking the list together a.nextnode = b b.prevnode = a b.nextnode = c c.prevnode = b print(b.value) >>>> 2 print(b.nextnode.value) >>>> 3 print(b.prevnode.value) >>>> 1
Заворачивать
Связанные списки - это набор узлов, которые вместе образуют линейную последовательность. Каждый узел в списках содержит данные и ссылку на следующий узел в последовательности. Поскольку предопределенного размера нет, пространство распределяется пропорционально его текущему количеству элементов. Удаление последнего узла может быть довольно сложным, поэтому двусвязные списки могут быть лучшим решением, когда требуется эта операция. Двусвязный список имеет явную ссылку на предыдущий узел, а также на следующий узел.
Спасибо за чтение!
Если вам понравилась эта статья, свяжитесь со мной, подписавшись на мою БЕСПЛАТНУЮ еженедельную рассылку. Не пропустите мой пост об искусственном интеллекте, машинном обучении и фрилансе.
