Зв’язані списки в 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, який представляє кожен вузол у списку. Кожен вузол містить значення та посилання на наступний вузол. Клас пов’язаного списку служить контейнером для вузлів, а атрибут 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

Створення циклічного пов’язаного списку

Щоб створити Circular Linked List, ми визначаємо клас 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

Зв’язаний список проти масиву

Зв’язані списки та масиви є широко використовуваними структурами даних, але вони мають різні характеристики, що робить їх придатними для різних сценаріїв. Давайте порівняємо пов’язані списки та масиви з точки зору ефективності пам’яті, ефективності вставки та видалення та ефективності довільного доступу.

Ефективність пам'яті

Зв’язані списки є більш ефективними для використання пам’яті, ніж масиви, оскільки вони не вимагають безперервного розподілу пам’яті. Кожен вузол у зв’язаному списку повинен зберігати лише значення та посилання на наступний вузол, тоді як масиви мають виділяти пам’ять для всіх елементів, навіть якщо вони не використовуються.

Ефективність вставки та видалення

Зв’язані списки відмінно підходять для операцій вставки та видалення, особливо коли елементи часто додаються або видаляються з середини списку. Вставлення або видалення елемента в пов’язаному списку вимагає лише оновлення посилань на сусідні вузли, тоді як масиви можуть вимагати переміщення елементів, щоб врахувати зміни.

Ефективність довільного доступу

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

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

Вибір між пов’язаними списками та масивами залежить від конкретних вимог програми. Якщо очікуються часті модифікації та динамічна зміна розміру, зв’язані списки є кращим вибором. З іншого боку, якщо довільний доступ і ефективність пам'яті є вирішальними, масиви є більш придатними.

Програми пов’язаного списку

Тепер, коли ми добре розуміємо зв’язані списки та їхню роботу, давайте розглянемо деякі практичні застосування, у яких зв’язані списки можна ефективно використовувати.

Ви також можете записатися на наш Безкоштовні курси Сьогодні!

Реалізація стеків і черг

Одним із найпоширеніших застосувань пов’язаних списків є реалізація стеків і черг. І стеки, і черги є абстрактними типами даних, які можна легко реалізувати за допомогою пов’язаних списків.

Стек — це структура даних, яка відповідає принципу «останній прийшов першим вийшов» (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 (First In-First Out). Елементи додаються на одному кінці, який називається заднім, і видаляються з іншого кінця, який називається переднім. Зв’язані списки також можна використовувати для ефективної реалізації черг.

Ось приклад реалізації черги за допомогою пов’язаного списку в 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 тут:

ЧАСТІ ЗАПИТАННЯ

споріднений

• Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
• PlatoData.Network Vertical Generative Ai. Додайте собі сили. Доступ тут.
• PlatoAiStream. Web3 Intelligence. Розширення знань. Доступ тут.
• ПлатонЕСГ. вуглець, CleanTech, Енергія, Навколишнє середовище, Сонячна, Поводження з відходами. Доступ тут.
• PlatoHealth. Розвідка про біотехнології та клінічні випробування. Доступ тут.
• джерело: https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/