Односвязный список Python: определение и особенности

Связный список является одной из самых распространенных структур данных, которые используются в Python, да и вообще в программировании. На основе связанного списка строятся более сложные структуры, например: стек, очередь и буфер.

Связный список в Python представляет собой структуру элементов информации, которые связываются между собой ссылками. При этом каждый элемент списка обычно содержит один и тот же тип информации, который является специфичным для этого списка. Каждый отдельный элемент списка именуется узлом.

В зависимости от вида связи между узлами, связные списки могут быть 2-х видов:

• односвязный список Python — в каждом отдельном узле такого списка содержится ссылка (указатель) только на следующий узел;

• двусвязный — в каждом отдельном узле такого списка содержится ссылка на следующий и предыдущий узлы.

Односвязный список Python

Односвязный список Python — это последовательность узлов информации, где каждый отдельный узел указывает только на следующий узел. Такой список можно легко исследовать от начала и до конца списка. В обратном порядке исследовать список очень непросто.

Как выглядит односвязный список Python в коде:

# Объявляем класс узла

class myNode:

   

    # Объявляем функцию, которая будет инициализировать создание узлов

    def __init__(self, data):

        self.data = data  # Назначаем дату

        self.nextnode = None  # Инициализируем следующий узел как «null»

        

        

a = myNode(1) # Объявляем дату для каждого узла

b = myNode(2)

c = myNode(3)

 

a.nextmynode = b # объединяем первый узел со вторым

b.nextmynode = c # объединяем второй узел с третьим

 

a.next.value # вернет значение следующего узла, то есть «b = 2»

Односвязный список Python: операции над узлами

Односвязный список Python поддерживает ряд операций над собственными узлами. Например: 

1. Добавление узла в список. Данная операция осуществляется при помощи функции «add_list_item()». При этом нужно помнить, что узел добавляется в конец списка. Если в списке вообще нет узлов, тогда объявленный таким образом узел встанет в начало списка и будет его возглавлять.

2. Поиск по списку. Это действие возможно при помощи функции «unordered_search()». Поиск начинается с первого узла списка и далее по порядку. При осуществлении поиска одновременно подсчитывается количество узлов. В результате выполнения этого метода мы получаем список узлов, в которых обнаружено совпадение с искомой информацией.

3. Удаление узла из списка. При удалении узла обязательно нужно откорректировать ссылку, которая указывает на удаляемый узел, так как теперь она должна указывать на узел, следующий после удаляемого. Это действие осуществляется при помощи функции «remove_list_item_by_id()». Узел удаляется по его номеру.

Манипуляции с двусвязными узлами осуществляются теми же функциями. Работа с двусвязным списком практически идентична, с той лишь разницей, что нужно брать во внимание наличие двух указателей в одном узле, ведь каждый узел в двусвязном списке указывает на следующий узел и на предыдущий.

Зачем использовать связный список

Односвязный или двусвязный списки в Python чем-то похожи на массивы, поэтому иногда возникает вопрос: «Зачем использовать связный список, если можно использовать массив?». Проблема в том, что массив имеет ограниченный или заданный размер, поэтому, когда в массив нужно добавить дополнительный элемент, превышающий его размер, это вызывает лишние трудности и проблемы.

Программисты не любят проблем с кодом, поэтому иногда используют связный список, а не массив. Если взглянуть на реализацию, тогда становится понятным, что связный список в Python чем-то похож на динамический массив, однако все они имеют собственные преимущества и недостатки.

Заключение

Односвязный список в Python — это последовательность элементов, связанных в одном направлении. Он удобен, когда нужно сохранить неопределенное количество информации, связанной между собой. Добавлять новый узел в связный список Python легче и «дешевле», если сравнивать даже с динамическим массивом.