связанный список — это структура данных, состоящая из цепочки объектов node . Каждый узел содержит значение и указатель на следующий узел в цепочке.
Связанные списки предпочтительнее массивов из-за их динамического размера и простоты вставки и свойства удаления.
Указатель заголовка указывает на первый узел, а последний элемент списка указывает на null . Когда список пуст, указатель заголовка указывает на null.
Связанные списки в Python
Исходный Python не поставляется со встроенной структурой данных связанных списков, подобной той, что имеется в Java.
Давайте посмотрим, как мы можем создать нашу собственную реализацию стандартного основанного на классах односвязного списка в Python.
1. Начнем с одного узла
Давайте начнем с одного узла, поскольку связывание нескольких узлов дает нам полный список. Для этого мы создаем класс Node , который содержит некоторые данные и единственный указатель next , который будет использоваться для укажите на следующий объект типа Node в связанном списке.
# Единственный узел односвязного списка класса Node: # конструктор def __init __ (self, data, next = None): self.data = data self.next = next # Создание единственного nodefirst = Node (3) print (first.data)
2. Объединение узлов для получения связанного списка
Следующим шагом является объединение нескольких отдельных узлов, содержащих data , с помощью указателей next , и иметь единственный указатель head , указывающий на полный экземпляр связанного списка.
Используя указатель head , мы будем иметь возможность просматривать весь список, даже выполнять всевозможные манипуляции со списком, пока мы находимся в нем.
Для этого мы создаем класс LinkedList с одним head указатель:
# Один узел односвязного списка класса Node: # constructor def __init __ (self, data = None, next = None): self.data = data self. next = next # Класс связанного списка с одной головкой nodeclass LinkedList: def __init __ (self): self.head = None # Связанный список с одним nodeLL = LinkedList () LL.head = Node (3) print (LL.head .data)
3. Добавьте необходимые методы в класс LinkedList
И последнее, но не менее важное: мы можем добавить в нашу реализацию различные методы управления связанными списками.
Давайте посмотрим на методы insert и print для нашей реализации LinkedList ниже:
# Один узел отдельного связанный listclass Node: # конструктор def __init __ (self, data = None, next = None): self.data = data self.next = next # Класс связанного списка с одной головкой nodeclass LinkedList: def __init __ (self): self. head = None # метод вставки связанного списка def insert (self, data): newNode = Node (data) if (self.head): current = self.head while (current.next): current = current.next current. next = newNode else: self.head = newNode # метод печати для связанного списка def printLL (self): current = self.head while (current): print (current) .data) current = current.next # Односвязный список с методами вставки и печатиLL = LinkedList () LL.insert (3) LL.insert (4) LL.insert (5) LL.printLL ()
