Структуре података играју кључну улогу у свету програмирања. Они нам помажу да организујемо своје податке на начин који се може ефикасно користити.
У овом водичу ћемо научити више о једноструко повезаној и двоструко повезаној листи.
Повезана листа је линеарна структура података. Не складишти податке на суседним меморијским локацијама као што су низови. И сваки елемент у повезаном се зове чвор и они су повезани помоћу показивача. Први чвор на повезаној листи назива се глава.
Величина повезане листе је динамичка. Дакле, можемо имати било који број чворова колико желимо осим ако складиште није доступно на уређају.
Постоје две врсте повезаних листа. Хајде да погледамо детаљан водич о њима један по један.
Преглед садржаја
#1. Једноструко повезана листа
Једноструко повезана листа садржи један показивач повезан са следећим чвором на повезаној листи. Морамо да ускладиштимо податке и показивач за сваки чвор на повезаној листи.
Последњи чвор у повезаној листи садржи нулл као следећи показивач који представља крај повезане листе.
Можете видети илустрацију линка испод.
Сада имамо потпуно разумевање једноповезане листе. Хајде да видимо кораке за имплементацију у Питхон-у.
Имплементација појединачно повезане листе
1. Први корак је креирање чвора за повезану листу.
Како га створити?
У Питхон-у можемо лако да креирамо чвор користећи класу. Класа садржи податке и показивач за следећи чвор.
Погледајте код за чвор.
class Node: def __init__(self, data): ## 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 != 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
Ура! завршили смо метод за уметање новог чвора у повезану листу. Како можемо приступити подацима о чворовима са повезане листе?
Да бисмо приступили подацима са повезане листе, морамо итерирати кроз повезану користећи следећи показивач као што радимо да бисмо добили последњи чвор у методи уметања. Хајде да напишемо метод унутар класе ЛинкедЛист за штампање свих података о чворовима на повезаној листи.
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')
Фуј! завршили смо креирање повезаних неопходним методама. Хајде да тестирамо повезану листу тако што ћемо је инстанцирати неким подацима.
Чвор можемо креирати са Ноде(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. Двоструко повезана листа
Двоструко повезана листа садржи два показивача повезана са претходним чвором и следећим чвором у повезаној листи. Морамо да ускладиштимо податке и два показивача за сваки чвор у повезаној листи.
Претходни показивач првог чвора је нулл, а следећи показивач последњег чвора је нулл за представљање краја повезане листе са обе стране.
Можете видети илустрацију линка испод.
Двоструко повезана листа такође има сличне кораке као и једноструко повезана листа у примени. Поново објашњавање истих ствари биће вам досадно. Прођите кроз код у сваком кораку и врло брзо ћете га разумети. Идемо.
Имплементација двоструко повезане листе
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()
Видели смо код двоструко повезане листе. И не постоји код за коришћење класе двоструко повезане листе. То је за тебе. Користите класу двоструко повезане листе сличне једнострукој листи. Забавите се 🙂
Закључак
Можете пронаћи многе проблеме на основу повезаних листа. Али, морате знати основну имплементацију линкова коју сте научили у овом водичу. Надам се да сте се добро провели учећи нови концепт.
Срећно кодирање 🙂