Реализация связанного списка на Python

[

Реализация связанного списка в Python: введение

Linked lists представляют собой менее известного двоюродного брата списков. Они не так популярны или круты, и, возможно, вы даже не помните их из вашего курса по алгоритмам. Но в правильном контексте они могут действительно блеснуть.

Понимание связанных списков

Связанные списки представляют собой упорядоченную коллекцию объектов. Что отличает их от обычных списков? Связанные списки отличаются от списков тем, как они хранят элементы в памяти. В то время как списки используют непрерывный блок памяти для хранения ссылок на свои данные, связанные списки хранят ссылки в качестве части собственных элементов.

Каждый элемент связанного списка называется узел, и каждый узел имеет два различных поля:

Data хранит значение, которое должно быть сохранено в узле.
Next содержит ссылку на следующий узел в списке.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Связанный список является набором узлов. Первый узел называется головой (head) и используется в качестве начальной точки для любого прохода по списку. У последнего узла должна быть ссылка next, указывающая на None, чтобы определить конец списка.

class LinkedList:
    def __init__(self):
        self.head = None

Теперь, когда вы знаете структуру связанного списка, вы готовы рассмотреть практические применения.

Практические применения

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

Например, рассмотрим реализацию стека с помощью связанного списка:

class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped_node = self.head
        self.head = self.head.next
        popped_node.next = None
        return popped_node.data

В этом примере каждый элемент добавляется и удаляется из вершины стека, а передача ссылок между узлами позволяет эффективно добавлять и удалять элементы.

Сравнение производительности: списки против связанных списков

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

Для наглядного сравнения производительности рассмотрим пример добавления элементов в середину списка с использованием обычного списка и связанного списка:

import time

# Реализация добавления элементов в середину обычного списка
def add_to_list(lst, index, value):
    start_time = time.time()
    lst.insert(index, value)
    end_time = time.time()
    print("Время выполнения для обычного списка:", end_time - start_time)

# Реализация добавления элементов в середину связанного списка
def add_to_linked_list(linked_list, index, value):
    start_time = time.time()
    current_node = linked_list.head
    for i in range(index - 1):
        current_node = current_node.next
    new_node = Node(value)
    new_node.next = current_node.next
    current_node.next = new_node
    end_time = time.time()
    print("Время выполнения для связанного списка:", end_time - start_time)

# Создание обычного списка и связанного списка
lst = []
linked_list = LinkedList()

for i in range(10000):
    lst.append(i)
    linked_list.append(i)

# Добавление элемента в середину обычного списка
add_to_list(lst, len(lst)//2, "new_value")

# Добавление элемента в середину связанного списка
add_to_linked_list(linked_list, len(linked_list)//2, "new_value")

В результате выполнения этого кода вы увидите, что добавление элемента в середину связанного списка занимает меньше времени по сравнению с обычным списком.

Заключение

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

Теперь, когда вы осознали возможности и преимущества связанных списков, можете начать использовать их в своих проектах на Python.