Что такое связанные списки в Python и как ими пользоваться? 💡

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

Вот пример создания связанного списка:

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

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

    def add_element(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current_node = self.head
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node
    

Приведенный выше код определяет классы Node и LinkedList. Класс Node содержит данные элемента списка и ссылку на следующий элемент, а класс LinkedList используется для добавления новых элементов в связанный список.

Вот пример добавления элементов в связанный список:

linked_list = LinkedList()
linked_list.add_element(5)
linked_list.add_element(10)
linked_list.add_element(15)
    

Теперь связанный список содержит элементы 5, 10 и 15.

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

Надеюсь, это помогло вам понять, что такое связанные списки в Python!

Связанные списки в Python: что это?

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

Определение класса Node

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

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

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

Определение класса LinkedList

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

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

В конструкторе класса LinkedList мы инициализируем атрибут head, который будет указывать на первый элемент связанного списка.

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

Для добавления элемента в связанный список мы создадим метод push(), который будет принимать значение элемента и добавлять его в начало списка.

def push(self, new_data):
    new_node = Node(new_data)
    new_node.next = self.head
    self.head = new_node

В методе push() создается новый узел с заданным значением new_data и ссылкой next на текущую голову списка. Затем указатель головы списка переустанавливается на новый узел.

Удаление элементов из связанного списка

Для удаления элемента из связанного списка мы создадим метод deleteNode(), который будет принимать значение элемента и удалять его из списка.

def deleteNode(self, key):
    temp = self.head

    if temp is not None:
        if temp.data == key:
            self.head = temp.next
            temp = None
            return

    while temp is not None:
        if temp.data == key:
            break
        prev = temp
        temp = temp.next

    if temp is None:
        return

    prev.next = temp.next
    temp = None

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

Обход элементов связанного списка

Для обхода элементов связанного списка мы создадим метод printList(), который будет выводить значения всех элементов списка.

def printList(self):
    temp = self.head
    while temp:
        print(temp.data)
        temp = temp.next

Метод printList() просто перебирает все элементы списка, начиная с головы, и выводит их значения.

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

# Создание экземпляра связанного списка
linked_list = LinkedList()

# Добавление элементов в список
linked_list.push(3)
linked_list.push(6)
linked_list.push(9)

# Вывод элементов списка
linked_list.printList()

В этом примере мы создаем экземпляр класса LinkedList, добавляем некоторые элементы с помощью метода push(), а затем выводим все элементы списка с помощью метода printList(). В результате выполнения кода будет выведено:

9
6
3

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