Списки: односвязные и двусвязные списки

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

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

Важно! В данном случае речь не идёт о классе list из Python, тут идёт речь о структуре данных из теории алгоритмов.

Виды списков:

• Односвязный список (Singly Linked List): Каждый узел содержит данные и ссылку на следующий узел.
• Двусвязный список (Doubly Linked List): Каждый узел содержит данные, ссылку на следующий узел и ссылку на предыдущий узел.

5.2 Принцип работы односвязного списка

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

• Узел (Node): Состоит из двух частей: данных и ссылки на следующий узел.
• Голова (Head): Указатель на первый узел списка.

Принцип работы:

• Добавление узла: Происходит путём создания нового узла и обновления ссылки последнего узла на новый узел.
• Удаление узла: Требует обновления ссылки предыдущего узла на следующий узел удаляемого узла.

Пример реализации:

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

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

    def append(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 display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Пример использования:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Вывод: 1 -> 2 -> 3 -> None

5.3 Принцип работы двусвязного списка

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

• Узел (Node): Состоит из трёх частей: данных, ссылки на следующий узел и ссылки на предыдущий узел.
• Голова (Head): Указатель на первый узел списка.
• Хвост (Tail): Указатель на последний узел списка (необязательно, но часто используется).

Принцип работы:

• Добавление узла: Происходит путём создания нового узла и обновления ссылок последнего узла и нового узла.
• Удаление узла: Требует обновления ссылок предыдущего и следующего узлов удаляемого узла.

Пример реализации:

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

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

    def append(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
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Пример использования:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Вывод: 1 <-> 2 <-> 3 <-> None

5.4 Основные операции

Основные операции: вставка, удаление, поиск

Вставка:

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

Удаление:

• Односвязный список: Удаление узла требует прохода по списку до узла, который необходимо удалить, и обновления ссылки предыдущего узла на следующий узел удаляемого узла.
• Двусвязный список: Удаление узла требует обновления ссылок next и prev соседних узлов удаляемого узла.
• Поиск: Проход по списку от головы до хвоста и сравнение данных каждого узла с искомым значением. Временная сложность — O(n).

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

Давайте для примера реализуем стек на базе односвязного списка.

Стек можно легко реализовать с помощью односвязного списка, используя методы добавления push и удаления pop элементов. У него должно быть 2 метода:

• push — добавление нового элемента в конец списка
• pop — изъятие последнего элемента из конца списка

Пример реализации:

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Пример использования:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Вывод: 3 -> 2 -> 1 -> None
print(stack.pop())  # Вывод: 3
stack.display()  # Вывод: 2 -> 1 -> None

2

Задача

Модуль 1: Python Core, 15 уровень, 4 лекция

Недоступна

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

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

Открыть

2

Задача

Модуль 1: Python Core, 15 уровень, 4 лекция

Недоступна

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

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

Открыть