Структури даних: Основи програмування
Структури даних є фундаментальним елементом в програмуванні. Вони дозволяють організовувати інформацію таким чином, щоб її використання було максимально ефективним та зручним.
В цьому посібнику ми розглянемо два важливих типи структур даних: однозв’язний список та двозв’язний список, розібравшись у їхній будові та принципах роботи.
Зв’язаний список – це лінійна структура даних, де елементи (вузли) не зберігаються у суміжних областях пам’яті, як у масивах. Кожен вузол містить дані та покажчик на наступний елемент. Перший вузол в списку називається головою.
Особливістю зв’язаних списків є їх динамічний розмір, що дозволяє зберігати будь-яку кількість елементів, обмежену лише доступною пам’яттю пристрою.
Існує два основних види зв’язаних списків. Давайте детальніше розглянемо кожен з них.
Однозв’язний список: Покроковий аналіз
Однозв’язний список характеризується наявністю одного покажчика в кожному вузлі, який вказує на наступний вузол у списку. Кожен вузол містить дані та цей покажчик.
Останній вузол у такому списку має покажчик на null, що позначає його кінець.
Щоб краще зрозуміти принцип роботи, ви можете звернутися до ілюстрації за посиланням.
Тепер, коли ви маєте чітке уявлення про структуру однозв’язного списку, розглянемо його реалізацію на Python.
Реалізація однозв’язного списку в Python
1. Створення вузла є першим кроком.
Як це зробити?
У Python для створення вузла можна використати клас. Цей клас міститиме дані вузла та покажчик на наступний вузол.
Ось приклад коду для класу вузла:
class Node:
def __init__(self, data):
self.data = data
self.next = None
За допомогою цього класу можна створити вузол з будь-яким типом даних. Ми розглянемо це далі.
Тепер, маючи вузол, перейдемо до створення самого зв’язаного списку.
2. Створімо клас LinkedList, який ініціалізує голову (перший елемент) як None.
class LinkedList:
def __init__(self):
self.head = None
3. Маючи класи Node та LinkedList, як ми можемо додавати нові вузли до списку? Для цього потрібно розробити метод в класі LinkedList, який буде відповідати за вставку нового вузла.
Вставка нового вузла виконується за певними кроками:
- Перевірити, чи є голова списку порожньою.
- Якщо голова порожня, новий вузол стає головою.
- Якщо голова не порожня, потрібно знайти останній вузол.
- Призначити новий вузол як наступний вузол для останнього.
Переглянемо код для вставки нового вузла:
class LinkedList:
####
def insert(self, new_node):
if self.head:
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
else:
self.head = new_node
Чудово, метод для вставки нового вузла готовий. Але як отримати доступ до даних вузлів зі списку?
Для цього потрібно пройти по всьому списку, використовуючи покажчик next. Розробимо метод для виведення даних всіх вузлів у зв’язаному списку.
4. Ось кроки для виведення даних всіх вузлів:
- Ініціалізація тимчасової змінної з головою списку.
- Цикл, який триває до кінця списку.
- Вивести дані вузла.
- Перейти до наступного вузла.
Перегляньмо код:
class LinkedList:
####
def display(self):
temp_node = self.head
while temp_node:
print(temp_node.data, end='->')
temp_node = temp_node.next
print('Null')
Отже, ми створили клас зв’язаного списку з необхідними методами. Давайте перевіримо його роботу.
Для створення вузла можна використати конструкцію Node(1). Ось повний код реалізації з прикладом використання:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert(self, new_node):
if self.head:
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
else:
self.head = new_node
def display(self):
temp_node = self.head
while temp_node:
print(temp_node.data, end='->')
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
linked_list = LinkedList()
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
linked_list.display()
Запустіть код, щоб отримати наступний результат:
1->2->3->4->5->6->7->Null
Це все, що стосується однозв’язного списку. Тепер ви знаєте, як його реалізувати. Маючи ці знання, ви легко зможете розібратися з двозв’язним списком. Перейдімо до наступної частини посібника.
Двозв’язний список: Подвійний зв’язок
Двозв’язний список відрізняється від однозв’язного тим, що кожен його вузол містить два покажчики: на попередній та на наступний вузол. Таким чином, кожен вузол зберігає дані та ці два покажчики.
Попередній покажчик першого вузла має значення null, так само як і наступний покажчик останнього вузла, що позначає кінець списку з обох сторін.
Для кращого розуміння ви можете переглянути ілюстрацію за посиланням.
Реалізація двозв’язного списку схожа на реалізацію однозв’язного, тому ми не будемо детально зупинятися на кожному кроці. Просто розгляньте код, і ви все зрозумієте.
Реалізація двозв’язного списку в Python
1. Створення вузла для двозв’язного списку з покажчиками на попередній та наступний вузли.
class Node:
def __init__(self, data):
self.prev = None
self.data = data
self.next = None
2. Клас двозв’язного списку.
class LinkedList:
def __init__(self):
self.head = None
3. Метод вставки нового вузла.
class LinkedList:
####
def insert(self, new_node):
if self.head:
last_node = self.head
while last_node.next:
last_node = last_node.next
new_node.prev = last_node
last_node.next = new_node
4. Метод відображення даних двозв’язного списку в прямому та зворотному порядках.
class LinkedList:
####
def display(self):
print("Normal Order: ", end='')
temp_node = self.head
while temp_node:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
print("Reverse Order: ", end='')
last_node = self.head
while last_node.next:
last_node = last_node.next
temp_node = last_node
while temp_node:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
Ми розглянули код двозв’язного списку. Залишилося тільки застосувати його, що ви можете зробити самостійно, за аналогією з однозв’язним списком.
Висновок
Існує безліч задач, які можна вирішити за допомогою зв’язаних списків. Але спочатку необхідно освоїти базові принципи їхньої реалізації, які ми розглянули в цьому посібнику. Сподіваємося, вам було цікаво вивчати цю концепцію.
Успіхів у програмуванні!