Связные списки

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

Определение односвязного списка и его структура

Что такое односвязный список?

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

Структура односвязного списка

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

• Данные: информация, которую хранит узел (например, число, строка и т.д.)
• Ссылка: указатель на следующий узел в списке

[Данные | Ссылка] -> [Данные | Ссылка] -> [Данные | Ссылка] -> NULL

Пример использования односвязного списка

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

Определение двусвязного списка и его структура

Что такое двусвязный список?

Двусвязный список — это структура данных, где каждый узел содержит ссылки на как следующий, так и предыдущий узел. Это позволяет легко перемещаться по списку в обоих направлениях.

Структура двусвязного списка

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

• Данные: информация, которую хранит узел
• Ссылка на предыдущий узел: указатель на узел, который находится перед текущим
• Ссылка на следующий узел: указатель на узел, который находится после текущего

NULL <- [Предыдущий | Данные | Следующий] <-> [Предыдущий | Данные | Следующий] <-> [Предыдущий | Данные | Следующий] -> NULL

Пример использования двусвязного списка

Двусвязные списки полезны, когда необходимо частое перемещение как вперед, так и назад, например, в реализации навигационных систем или редакторов текста

Преимущества и недостатки связных списков по сравнению с массивами

Преимущества связных списков

1. Динамическое выделение памяти: Связные списки могут расти и уменьшаться по мере необходимости, в отличие от массивов, которые имеют фиксированный размер
2. Удобство добавления и удаления: Добавление и удаление узлов в связном списке происходит за постоянное время O(1), в то время как для массивов это может потребовать перемещения элементов

Недостатки связных списков

1. Дополнительная память: Каждый узел требует дополнительной памяти для хранения ссылок, что может быть неэффективно для небольших наборов данных
2. Сложность доступа: Доступ к элементам в связном списке требует последовательного обхода узлов, что делает операции поиска менее эффективными (O(n)) по сравнению с массивами (O(1))

Практическое задание

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

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

• Реализуйте методы для добавления элемента в начало, конец и по индексу
• Реализуйте методы для удаления элемента и поиска элемента

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

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

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

    def add_to_end(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_node(self, key):
        current = self.head
        if current and current.data == key:
            self.head = current.next
            current = None
            return
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        if current is None:
            return
        prev.next = current.next
        current = None

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

Создайте класс для двусвязного списка:

• Реализуйте методы для добавления элемента, удаления элемента и поиска элемента

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

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

    def add_to_start(self, data):
        new_node = DNode(data)
        new_node.next = self.head
        if self.head:
            self.head.prev = new_node
        self.head = new_node

    def add_to_end(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def delete_node(self, key):
        current = self.head
        if current and current.data == key:
            self.head = current.next
            if self.head:
                self.head.prev = None
            current = None
            return
        while current and current.data != key:
            current = current.next
        if current is None:
            return
        if current.next:
            current.next.prev = current.prev
        if current.prev:
            current.prev.next = current.next
        current = None

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

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