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

Введение

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

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

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

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

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

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

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

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

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

class Linked List:
    def __init__(self):
        self.head = None

Создание односвязного списка

Чтобы создать односвязный список, нам нужно определить класс Node, который представляет каждый узел в списке. Каждый узел содержит значение и ссылку на следующий узел. Класс Linked List служит контейнером для узлов, а атрибут head указывает на первый узел в списке.

Вставка узлов в односвязный список

Вставка узлов в односвязный список предполагает обновление ссылок соседних узлов. Вот пример вставки узла в начало списка:

def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

Удаление узлов из односвязного списка

Удаление узлов из односвязного списка требует обновления ссылок соседних узлов. Вот пример удаления узла с определенным значением:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                break
            current = current.next

Поиск в односвязном списке

Поиск определенного значения в односвязном списке предполагает обход списка до тех пор, пока значение не будет найдено или не будет достигнут конец списка. Вот пример поиска значения:

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

Реверсирование односвязного списка

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

def reverse(self):
    previous = None
    current = self.head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    self.head = previous

Двусвязный список

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

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

class DoublyLinked List:
    def __init__(self):
        self.head = None

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

Чтобы создать двусвязный список, мы определяем класс Node, который содержит значение, ссылку на следующий узел и ссылку на предыдущий узел. Класс DoublyLinked List служит контейнером для узлов, а атрибут head указывает на первый узел в списке.

Вставка узлов в двусвязный список

Вставка узлов в двусвязный список предполагает обновление ссылок соседних узлов. Вот пример вставки узла в начало списка:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if self.head:
        self.head.previous = new_node
    new_node.next = self.head
    self.head = new_node

Удаление узлов из двусвязного списка

Удаление узлов из двусвязного списка требует обновления ссылок соседних узлов. Вот пример удаления узла с определенным значением:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
        if self.head:
            self.head.previous = None
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                if current.next:
                    current.next.previous = current
                break
            current = current.next

Поиск в двусвязном списке

Поиск определенного значения в двусвязном списке предполагает обход списка в любом направлении до тех пор, пока значение не будет найдено или не будет достигнут конец списка. Вот пример поиска значения:

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

Реверсирование двусвязного списка

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

def reverse(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = current.previous
        current.previous = next_node
        if not next_node:
            self.head = current
        current = next_node

Циркулярный связанный список

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

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

class CircularLinked List:
    def __init__(self):
        self.head = None

Создание циклического связанного списка

Чтобы создать циклический связанный список, мы определяем класс Node, который содержит значение и ссылку на следующий узел. Класс CircularLinked List служит контейнером для узлов, а атрибут head указывает на первый узел в списке. Кроме того, следующая ссылка последнего узла устанавливается на заголовок, создавая круговую структуру.

Вставка узлов в циклический связанный список

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

def insert_at_beginning(self, value):
    new_node = Node(value)
    if not self.head:
        self.head = new_node
        new_node.next = self.head
    else:
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head
        self.head = new_node

Удаление узлов из циклического связанного списка

Удаление узлов из циклического связанного списка требует обновления ссылок соседних узлов. Вот пример удаления узла с определенным значением:

def delete_node(self, value):
    if not self.head:
        return
    current = self.head
    if current.value == value:
        while current.next != self.head:
            current = current.next
        if current == self.head:
            self.head = None
        else:
            current.next = self.head.next
            self.head = self.head.next
    else:
        previous = None
        while current.next != self.head:
            previous = current
            current = current.next
            if current.value == value:
                previous.next = current.next
                break

Поиск в кольцевом связанном списке

Поиск определенного значения в циклическом связанном списке предполагает обход списка до тех пор, пока не будет найдено значение или не будет пройден весь список. Вот пример поиска значения:

def search(self, value):
    if not self.head:
        return False
    current = self.head
    while True:
        if current.value == value:
            return True
        current = current.next
        if current == self.head:
            break
    return False

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

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

def reverse(self):
    if not self.head:
        return
    previous = None
    current = self.head
    next_node = current.next
    while True:
        current.next = previous
        previous = current
        current = next_node
        next_node = next_node.next
        if current == self.head:
            break
    self.head = previous

Общие операции со связанными списками

Связанные списки поддерживают различные общие операции, которые можно выполнять с элементами. Давайте рассмотрим некоторые из этих операций:

Доступ к элементам в связанном списке

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

def get_element(self, index):
    current = self.head
    count = 0
    while current:
        if count == index:
            return current.value
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Изменение элементов в связанном списке

Изменение элементов в связанном списке включает в себя просмотр списка в поисках нужного элемента и обновление его значения. Вот пример изменения элемента по определенному индексу:

def modify_element(self, index, new_value):
    current = self.head
    count = 0
    while current:
        if count == index:
            current.value = new_value
            return
        count += 1
        current = current.next
    raise IndexError("Index out of range")

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

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

def get_length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

Проверка того, пуст ли связанный список

Чтобы проверить, пуст ли связанный список, мы можем просто проверить, имеет ли головной узел значение None. Вот пример проверки того, пуст ли связанный список:

def is_empty(self):
    return self.head is None

Объединение связанных списков

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

def concatenate(self, other_list):
    if not self.head:
        self.head = other_list.head
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = other_list.head

Связанный список против массива

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

Эффективность памяти

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

Эффективность вставки и удаления

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

Эффективность произвольного доступа

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

Выбор правильной структуры данных

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

Приложения связанных списков

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

Вы также можете записаться к нам Бесплатные курсы Cегодня!

Реализация стеков и очередей

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

Стек — это структура данных, которая соответствует принципу «последним пришел — первым обслужен» (LIFO). Элементы добавляются и удаляются с одного и того же конца, известного как вершина стека. Связанные списки предоставляют эффективный способ реализации стеков, поскольку мы можем легко добавлять или удалять элементы из заголовка списка.

Вот пример реализации стека с использованием связанного списка в Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = 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 = self.head.data
        self.head = self.head.next
        return popped

Очередь, с другой стороны, следует принципу «первым пришел — первым обслужен» (FIFO). Элементы добавляются на одном конце, известном как задний, и удаляются с другого конца, известного как передний. Связанные списки также можно использовать для эффективной реализации очередей.

Вот пример реализации очереди с использованием связанного списка в Python:

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

Обработка больших наборов данных

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

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

Алгоритмы обхода графа

Алгоритмы обхода графа, такие как поиск в ширину (BFS) и поиск в глубину (DFS), также могут быть реализованы с использованием связанных списков. При обходе графа мы посещаем каждую вершину или узел графа в определенном порядке.

Связанные списки можно использовать для представления списка смежности графа, где каждый узел в связанном списке представляет вершину, а соседние с ним вершины сохраняются как узлы связанного списка. Такое представление позволяет эффективно перемещаться и исследовать граф.

Полиномиальное представление

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

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

Плейлисты музыки и видео

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

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

Заключение

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

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

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

Вы также можете прочитать дополнительные статьи, связанные со списками Python, здесь:

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

Похожие страницы:

• SEO-контент и PR-распределение. Получите усиление сегодня.
• PlatoData.Network Вертикальный генеративный ИИ. Расширьте возможности себя. Доступ здесь.
• ПлатонАйСтрим. Интеллект Web3. Расширение знаний. Доступ здесь.
• ПлатонЭСГ. Углерод, чистые технологии, Энергия, Окружающая среда, Солнечная, Управление отходами. Доступ здесь.
• ПлатонЗдоровье. Биотехнологии и клинические исследования. Доступ здесь.
• Источник: https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/