Списки могут быть полезны, когда разработчик хочет, чтобы набор данных был упорядоченным и изменяемым. Хотя это очень распространенная структура данных, она не самая быстрая: скорость зависит от того, как реализован список. Существует один способ реализации списков для более быстрого выполнения: он известен как связанные списки.
Связанные списки — это линейные структуры данных, содержащие последовательность узловых объектов. Узел — это объект, содержащий данные, хранящиеся внутри него. Каждый узел отслеживает элемент и следующий узел, на который он ссылается. Эти элементы связаны с помощью указателей, которые продолжают работать до тех пор, пока не останется узла, на который можно было бы указать. Преимущество связанных списков заключается в их способности жить в любом месте памяти, тогда как для массивов требуется инициация последовательности памяти. Это означает, что программы со связанными списками имеют более высокую сложность выполнения, чем программы без них. Сложность времени выполнения измеряет скорость, с которой программа компилируется и запускается.
Существуют различные типы связанных списков: односвязные списки, круговые списки и двусвязные списки для более сложных программ. Мы часто используем двусвязные списки, когда хотим, чтобы два указателя указывали как на следующий узел, так и на предыдущий узел.
Хотя связанные списки могут быть полезными, у них есть некоторые недостатки. При поиске определенного элемента нам пришлось бы начинать с головы и проверять каждый узел, пока мы не найдем нужный элемент. Если связанный список состоит из n элементов, поиск нужного элемента может занять до n времени (время выполнения O(n)).
Вот как мы можем реализовать связанный список в Python:
Это класс узла, который инициализирует объект узла.
class Node:
# Function to initialize the node object.
def __init__(self, data):
self.data = data # Initialize data.
self.next = None # Initialize next which points to nothing.
Это класс связанного списка, который инициализирует объект связанного списка.
class LinkedList:
# Function to initialize the Linked list object.
def __init__(self):
self.head = None # Initialize head to none (first node).
Для получения дополнительной информации о реализации и некоторых основных операциях в связанных списках, пожалуйста, нажмите на ссылку здесь.
