Структури даних відіграють ключову роль у світі програмування. Вони допомагають нам упорядковувати наші дані таким чином, щоб їх можна було ефективно використовувати.
У цьому підручнику ми збираємося дізнатися про однозв’язний список і двозв’язаний список.
Зв’язаний список — це лінійна структура даних. Він не зберігає дані в безперервних місцях пам’яті, як у масивах. І кожен елемент у linked називається вузлом, і вони з’єднані за допомогою вказівників. Перший вузол у пов’язаному списку називається головою.
Розмір пов’язаного списку є динамічним. Отже, ми можемо мати будь-яку кількість вузлів, якщо тільки пам’ять не доступна на пристрої.
Існує два типи пов’язаних списків. Давайте по черзі переглянемо докладний підручник про них.
#1. Однозв’язаний список
Однозв’язаний список містить один покажчик, з’єднаний з наступним вузлом у зв’язаному списку. Ми повинні зберігати дані та покажчик для кожного вузла у зв’язаному списку.
Останній вузол у зв’язаному списку містить null як наступний вказівник, що представляє кінець зв’язаного списку.
Ви можете переглянути ілюстрацію за посиланням нижче.
Тепер ми маємо повне розуміння однозв’язаного списку. Давайте подивимося кроки, щоб реалізувати це в Python.
Реалізація однозв’язаного списку
1. Першим кроком є створення вузла для пов’язаного списку.
Як його створити?
У Python ми можемо легко створити вузол за допомогою класу. Клас містить дані та вказівник на наступний вузол.
Подивіться на код вузла.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Ми можемо створити вузол з будь-яким типом даних, використовуючи наведений вище клас. Ми побачимо це трохи пізніше.
Тепер у нас є вузол. Далі ми повинні створити пов’язаний список із кількома вузлами. Давайте створимо ще один клас для пов’язаного списку.
2. Створіть клас під назвою LinkedList із заголовком, ініціалізованим на None. Перегляньте код нижче.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. У нас є класи Node і LinkedList. Як вставити новий вузол у пов’язаний список? Простою відповіддю може бути використання методу в класі LinkedList. Так, це було б добре. Давайте напишемо метод для вставки нового вузла в пов’язаний список.
Щоб вставити новий вузол у пов’язаний список, ми повинні виконати певні кроки.
Давайте їх подивимось.
- Перевірте, порожня головка чи ні.
- Якщо голова порожня, призначте новий вузол для голови.
- Якщо заголовок не порожній, отримати останній вузол пов’язаного списку.
- Призначте новий вузол останньому вказівнику наступного вузла.
Давайте подивимося код для вставки нового вузла в пов’язаний список.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node != None: last_node = last_node.next ## assigning the new node to the next pointer of last node last_node.next = new_node else: ## head is empty ## assigning the node to head self.head = new_node
Ура! ми завершили метод вставлення нового вузла в пов’язаний список. Як ми можемо отримати доступ до даних вузлів зі зв’язаного списку?
Щоб отримати доступ до даних зі зв’язаного списку, ми повинні пройти пов’язаний список, використовуючи вказівник next, як ми робимо, щоб отримати останній вузол у методі вставки. Давайте напишемо метод у класі LinkedList для друку всіх даних вузлів у зв’язаному списку.
4. Виконайте наведені нижче дії, щоб надрукувати всі дані вузлів у зв’язаному списку.
- Ініціалізація змінної за допомогою голови.
- Напишіть цикл, який повторюється, доки ми не досягнемо кінця пов’язаного списку.
- Роздрукуйте дані вузла.
- Перемістіть наступний покажчик
Давайте подивимось код.
class LinkedList:
####
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
Фу! ми завершили створення зв’язку з необхідними методами. Давайте перевіримо пов’язаний список, створивши для нього деякі дані.
Ми можемо створити вузол за допомогою коду Node(1). Давайте подивимося повний код реалізації пов’язаного списку разом із прикладом використання.
class Node:
def __init__(self, data):
## data of the node
self.data = data
## next pointer
self.next = None
class LinkedList:
def __init__(self):
## initializing the head with None
self.head = None
def insert(self, new_node):
## check whether the head is empty or not
if self.head:
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## assigning the new node to the next pointer of last node
last_node.next = new_node
else:
## head is empty
## assigning the node to head
self.head = new_node
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## instantiating the linked list
linked_list = LinkedList()
## inserting the data into the linked list
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))
## printing the linked list
linked_list.display()
Запустіть наведену вище програму, щоб отримати наступний результат.
1->2->3->4->5->6->7->Null
Ось і все для пов’язаного списку. Тепер ви знаєте, як реалізувати однозв’язаний список. Ви можете легко реалізувати подвійний зв’язаний список, знаючи однозв’язаний список. Давайте зануримося в наступний розділ підручника.
#2. Двізв’язаний список
Двозв’язаний список містить два покажчики, пов’язані з попереднім вузлом і наступним вузлом у зв’язаному списку. Ми повинні зберігати дані та два покажчики для кожного вузла у зв’язаному списку.
Попередній покажчик першого вузла має значення null, а наступний покажчик останнього вузла має значення null для представлення кінця пов’язаного списку з обох сторін.
Ви можете переглянути ілюстрацію за посиланням нижче.
Двозв’язаний список також має подібні етапи реалізації однозв’язаного списку. Знову пояснювати те саме вам буде нудно. Перегляньте код на кожному кроці, і ви зрозумієте його дуже швидко. Ходімо.
Реалізація двозв’язаного списку
1. Створення вузла для двозв’язаного списку з покажчиком попереднього вузла, даними та покажчиком наступного вузла.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Клас двозв’язаного списку.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Спосіб вставки нового вузла в двозв’язаний список.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node.next != None: last_node = last_node.next ## assigning the last node to the previous pointer of the new node new_node.prev = last_node ## assigning the new node to the next pointer of last node last_node.next = new_node
4. Спосіб відображення даних двозв’язаного списку.
class LinkedList:
####
def display(self):
## printing the data in normal order
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## printing the data in reverse order using previous pointer
print("Reverse Order: ", end='')
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
Ми бачили код двозв’язного списку. І немає коду для використання класу двозв’язаного списку. Це тобі. Використовуйте клас двозв’язаного списку, подібний до однозв’язаного списку. Отримуйте задоволення 🙂
Висновок
Ви можете знайти багато проблем на основі пов’язаних списків. Але ви повинні знати базову реалізацію linked, яку ви вивчали в цьому підручнику. Сподіваюся, ви чудово провели час, вивчивши нову концепцію.
Щасливого кодування 🙂