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