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

Узнайте, как реализовать односвязный список в Python. Изучите динамическое распределение памяти, операции с узлами, вставку, обход и удаление.

Попробуйте в редакторе

Обзор

Связанный список — это линейная структура данных, элементы которой не хранятся в смежных ячейках памяти. Вместо этого каждый элемент (называемый узлом) представляет собой отдельный объект, содержащий ссылку на следующий узел последовательности.

Основным преимуществом связанного списка по сравнению с традиционным массивом является его динамическое изменение размера и возможность вставки или удаления элементов в начале за постоянное время O(1). Однако доступ к элементам по индексу требует линейного обхода, который занимает время O(n).

В Python мы реализуем связанный список, определяя класс Node для хранения данных и указателя ссылки, а также класс LinkedList для управления головным узлом, вставками в заголовок или хвост и удалениями.

Код и вывод выполнения

Реализация односвязного списка на Python, демонстрирующая создание, добавление и обход списка узлов.

linked_list.py

Попробуйте в редакторе

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

class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        
    def delete(self, key):
        curr = self.head
        if curr and curr.data == key:
            self.head = curr.next
            curr = None
            return
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        if not curr:
            return
        prev.next = curr.next
        curr = None
        
    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> None")

# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()

print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()

Терминальный выход

Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> None

Пошаговая реализация

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

Часто задаваемые вопросы

В чем разница между односвязными и двусвязными списками?

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

Почему в Python нет встроенного класса LinkedList?

Массивы (списки) Python реализованы как динамические массивы. Благодаря управлению памятью Python и оптимизацииCPythonстандартные списки чрезвычайно быстры и эффективны для большинства задач, что снижает практическую потребность во встроенном связанном списке.

Связанные темы

Учебное пособие по структуре данных стека Python

Реализуйте стек LIFO на Python. Запустите наш пример кода интерактивного стека, чтобы узнать ограничения по push, pop, peek и емкости.

Учебное пособие по структуре данных очереди Python

Освойте операции с очередью FIFO в Python. Выполните и запустите наш пример интерактивной очереди, демонстрирующий методы постановки и удаления из очереди.