Введение
Связанный список — это структура данных, состоящая из последовательности узлов, каждый из которых содержит значение и ссылку на следующий узел в последовательности. В отличие от массивов, связанные списки не требуют непрерывного выделения памяти, что делает их более гибкими и эффективными для определенных операций. В этой статье мы рассмотрим преимущества и недостатки связанных списков и способы их реализации в 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/
- :является
- :нет
- :куда
- 1
- 10
- 16
- 48
- 5
- 9
- a
- О нас
- АБСТРАКТ НАЯ
- доступ
- доступа
- вмещать
- Добавить
- добавленный
- дополнение
- Дополнительно
- адресация
- примыкающий
- Преимущества
- алгоритмы
- Все
- выделять
- распределение
- позволять
- позволяет
- причислены
- an
- и
- любой
- Применение
- Приложения
- МЫ
- массив
- гайд
- статьи
- AS
- At
- назад
- основанный
- BE
- , так как:
- начало
- Лучшая
- между
- изоферменты печени
- Ломать
- но
- by
- CAN
- определенный
- изменение
- характеристика
- проверка
- контроль
- выбор
- Выбирая
- круговой
- класс
- код
- коэффициенты
- Общий
- обычно
- сравнить
- краткий
- заключение
- Рассматривать
- Состоящий из
- состоит
- потреблять
- Container
- содержит
- контраст
- считать
- Создайте
- Создающий
- решающее значение
- Текущий
- данным
- Наборы данных
- занимавшийся
- решения
- защиту
- определять
- удалять
- зависит
- желанный
- подробность
- различный
- направлять
- направление
- инструкция
- do
- доменов
- вдвойне
- динамический
- динамично
- каждый
- легко
- легко
- фактически
- затрат
- эффективный
- эффективно
- или
- элемент
- элементы
- еще
- пустой
- столкновение
- конец
- зачислять
- Весь
- особенно
- Эфир (ETH)
- Даже
- пример
- Excel
- ожидаемый
- опыт
- исследование
- Больше
- показатель степени
- выражения
- дополнительно
- ложный
- быстрее
- Файл
- Найдите
- обнаружение
- First
- фиксированной
- гибкого
- следующим образом
- Что касается
- найденный
- частое
- часто
- от
- передний
- Более того
- хорошо
- график
- Расти
- рука
- обрабатывать
- Есть
- здесь
- High
- Как
- How To
- Однако
- HTTPS
- идеальный
- if
- осуществлять
- в XNUMX году
- Осуществляющий
- in
- индекс
- Индексы
- неэффективное
- информация
- сообщил
- интерфейсы
- интуитивный
- включает в себя
- IT
- ЕГО
- известный
- Отсутствие
- большой
- Фамилия
- Длина
- Используя
- LINK
- связанный
- Список
- Списки
- Главная
- сделать
- ДЕЛАЕТ
- Создание
- управления
- манипулировать
- Манипуляция
- математика
- макс-ширина
- Май..
- смысл
- означает
- Медиа
- Память
- средняя
- миллионы
- изменения
- БОЛЕЕ
- самых
- двигаться
- умножение
- Музыка
- Навигация
- Необходимость
- потребности
- близлежащий
- следующий
- узел
- узлы
- Ничто
- номер
- of
- предлагают
- on
- ONE
- только
- Операционный отдел
- Оптимизировать
- or
- заказ
- Другое
- наши
- внешний
- за
- выполнять
- производительность
- выполнены
- Платон
- Платон Интеллектуальные данные
- ПлатонДанные
- игроки
- Точка
- пунктов
- многочлен
- многочлены
- должность
- практическое
- Практическое применение
- предыдущий
- принцип
- Проблема
- проблемам
- Программы
- обеспечивать
- приводит
- обеспечение
- Питон
- повышение
- случайный
- ассортимент
- достигать
- достиг
- Читать
- учет
- ссылка
- Рекомендации
- Связанный
- удаление
- удален
- представлять
- представление
- представленный
- представляет
- требовать
- Требования
- требуется
- результат
- в результате
- возвращают
- обратный
- правую
- то же
- сообщили
- Сценарии
- бесшовные
- Поиск
- поиск
- Во-вторых
- SELF
- Последовательность
- служит
- набор
- несколько
- СДВИГАЯ
- аналогичный
- упростить
- просто
- Размер
- Размеры
- небольшой
- Решение
- Решения
- некоторые
- песня
- конкретный
- стек
- Стеки
- Начало
- магазин
- хранить
- Структура
- структур
- вычитание
- такие
- подходящее
- поддержка
- SVG
- обмен
- Сложность задачи
- срок
- terms
- чем
- который
- Ассоциация
- График
- их
- Их
- Там.
- Эти
- они
- этой
- три
- время
- в
- инструментом
- Инструментарий
- топ
- траверс
- правда
- два
- напишите
- Типы
- понимание
- В отличие от
- до
- Обновление ПО
- обновление
- используемый
- полезный
- Информация о пользователе
- Пользовательский опыт
- удобно
- через
- ценный
- ценностное
- переменные
- различный
- Различная
- разносторонний
- Видео
- Видео
- Войти
- vs
- Путь..
- we
- Что
- Что такое
- когда
- в то время как
- будь то
- который
- в то время как
- будете
- без
- Работа
- являетесь
- ВАШЕ
- зефирнет