Списки: однозв'язні та двозв'язні списки

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