Strukture podataka predstavljaju temelj u svetu programiranja. One nam omogućavaju da organizujemo informacije na način koji omogućava njihovu efikasnu upotrebu.
U ovom vodiču detaljnije ćemo istražiti jednostruko i dvostruko povezane liste.
Povezana lista je linearna struktura podataka koja, za razliku od nizova, ne skladišti podatke na susednim memorijskim lokacijama. Svaki element u povezanoj listi naziva se čvor, a čvorovi su povezani pomoću pokazivača. Prvi čvor u listi se naziva glava.
Veličina povezane liste je dinamična, što znači da broj čvorova nije ograničen, osim raspoloživom memorijom uređaja.
Postoje dva osnovna tipa povezanih listi. Detaljno ćemo ih razmotriti pojedinačno.
#1. Jednostruko povezana lista
Jednostruko povezana lista sadrži jedan pokazivač koji je usmeren na sledeći čvor u listi. Svaki čvor u jednostruko povezanoj listi sadrži podatke i pokazivač na sledeći čvor.
Poslednji čvor u listi sadrži NULL kao sledeći pokazivač, čime označava kraj liste.
Ilustraciju možete pogledati ispod.
Sada kada imamo osnovno razumevanje jednostruko povezane liste, pogledajmo korake za njenu implementaciju u Python-u.
Implementacija jednostruko povezane liste
1. Prvi korak je kreiranje čvora za povezanu listu.
Kako kreirati čvor?
U Python-u, čvor možemo jednostavno kreirati koristeći klasu. Klasa će sadržati podatke i pokazivač na sledeći čvor.
Primer koda za čvor:
class Node: def __init__(self, data): # podaci čvora self.data = data # pokazivač na sledeći čvor self.next = None
Pomoću ove klase možemo kreirati čvor sa bilo kojom vrstom podataka. To ćemo uskoro videti.
Sada kada imamo definisan čvor, potrebno je da kreiramo povezanu listu sa više čvorova. Stoga, kreiraćemo drugu klasu za povezanu listu.
2. Kreirajmo klasu pod nazivom `LinkedList` sa glavom inicijalizovanom na None. Kod je prikazan ispod.
class LinkedList: def __init__(self): # inicijalizacija glave sa None self.head = None
3. Sada imamo klase `Node` i `LinkedList`. Kako ubaciti novi čvor u povezanu listu? Najjednostavnije rešenje je korišćenje metode unutar klase `LinkedList`. Hajde da napišemo metodu za ubacivanje novog čvora u listu.
Za ubacivanje novog čvora u listu, potrebno je pratiti određene korake:
- Proveriti da li je glava prazna.
- Ako je glava prazna, dodeliti novi čvor glavi.
- Ako glava nije prazna, pronaći poslednji čvor u listi.
- Dodeli novi čvor pokazivaču `next` poslednjeg čvora.
Pogledajmo kod za ubacivanje novog čvora:
class LinkedList: #### def insert(self, new_node): # proverava da li je glava prazna if self.head: # dobijanje poslednjeg čvora last_node = self.head while last_node.next != None: last_node = last_node.next # dodeljivanje novog čvora pokazivaču 'next' poslednjeg čvora last_node.next = new_node else: # glava je prazna # dodeljivanje čvora glavi self.head = new_node
Odlično! Završili smo metodu za ubacivanje novog čvora. Kako možemo pristupiti podacima u čvorovima liste?
Da bismo pristupili podacima iz liste, potrebno je iterirati kroz listu koristeći pokazivač `next`, kao što smo radili pri pronalaženju poslednjeg čvora u prethodnoj metodi. Hajde da napišemo metodu unutar klase `LinkedList` za ispis svih podataka u čvorovima.
4. Pratite sledeće korake za prikaz svih podataka iz čvorova:
- Inicijalizovati promenljivu sa glavom.
- Napisati petlju koja se ponavlja dok ne dođemo do kraja liste.
- Ispisati podatke iz čvora.
- Preći na sledeći čvor.
Pogledajmo kod:
class LinkedList:
####
def display(self):
# promenljiva za iteraciju
temp_node = self.head
# iteracija dok ne dođemo do kraja liste
while temp_node != None:
# ispis podataka čvora
print(temp_node.data, end='->')
# prelazak na sledeći čvor
temp_node = temp_node.next
print('Null')
Sjajno! Kreirali smo povezanu listu sa osnovnim metodama. Testirajmo je instanciranjem sa nekim podacima.
Čvor možemo kreirati pomoću koda `Node(1)`. U nastavku se nalazi kompletan kod implementacije povezane liste sa primerom upotrebe.
class Node:
def __init__(self, data):
# podaci čvora
self.data = data
# pokazivač na sledeći čvor
self.next = None
class LinkedList:
def __init__(self):
# inicijalizacija glave sa None
self.head = None
def insert(self, new_node):
# provera da li je glava prazna
if self.head:
# dobijanje poslednjeg čvora
last_node = self.head
while last_node.next != None:
last_node = last_node.next
# dodeljivanje novog čvora pokazivaču 'next' poslednjeg čvora
last_node.next = new_node
else:
# glava je prazna
# dodeljivanje čvora glavi
self.head = new_node
def display(self):
# promenljiva za iteraciju
temp_node = self.head
# iteracija dok ne dođemo do kraja liste
while temp_node != None:
# ispis podataka čvora
print(temp_node.data, end='->')
# prelazak na sledeći čvor
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
# instanciranje povezane liste
linked_list = LinkedList()
# ubacivanje podataka u listu
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))
# prikaz liste
linked_list.display()
Pokretanjem gornjeg programa dobićete sledeći rezultat:
1->2->3->4->5->6->7->Null
To je sve što se tiče jednostruko povezane liste. Sada znate kako da implementirate jednostruko povezanu listu. Dvostruko povezanu listu možete lako implementirati koristeći znanje o jednostruko povezanoj listi. Hajde da pređemo na sledeći odeljak vodiča.
#2. Dvostruko povezana lista
Dvostruko povezana lista sadrži dva pokazivača – jedan koji pokazuje na prethodni čvor i drugi koji pokazuje na sledeći čvor u listi. Svaki čvor u dvostruko povezanoj listi sadrži podatke i dva pokazivača.
Prethodni pokazivač prvog čvora je NULL, a sledeći pokazivač poslednjeg čvora je NULL, čime se označava kraj liste sa obe strane.
Ilustraciju možete pogledati ispod.
Dvostruko povezana lista ima slične korake implementacije kao jednostruko povezana lista. Objašnjavanje istih stvari ponovo bi bilo zamorno. Prođite kroz kod u svakom koraku i razumećete ga vrlo brzo. Krenimo.
Implementacija dvostruko povezane liste
1. Kreiranje čvora za dvostruko povezanu listu sa pokazivačem na prethodni čvor, podacima i pokazivačem na sledeći čvor.
class Node: def __init__(self, data): # pokazivač na prethodni čvor self.prev = None # podaci čvora self.data = data # pokazivač na sledeći čvor self.next = None
2. Klasa za dvostruko povezanu listu.
class LinkedList: def __init__(self): # inicijalizacija glave sa None self.head = None
3. Metod za ubacivanje novog čvora u dvostruko povezanu listu.
class LinkedList: #### def insert(self, new_node): # provera da li je glava prazna if self.head: # dobijanje poslednjeg čvora last_node = self.head while last_node.next != None: last_node = last_node.next # dodeljivanje poslednjeg čvora pokazivaču 'prev' novog čvora new_node.prev = last_node # dodeljivanje novog čvora pokazivaču 'next' poslednjeg čvora last_node.next = new_node
4. Metod za prikaz podataka iz dvostruko povezane liste.
class LinkedList:
####
def display(self):
# ispis podataka normalnim redosledom
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
# ispis podataka obrnutim redosledom pomoću pokazivača 'prev'
print("Reverse Order: ", end='')
# dobijanje poslednjeg čvora
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()
Videli smo kod za dvostruko povezanu listu. Nema koda za korišćenje klase dvostruko povezane liste – to je za vas. Koristite klasu dvostruko povezane liste slično kao kod jednostruke liste. Zabavite se 🙂
Zaključak
Možete pronaći mnoge probleme zasnovane na povezanim listama. Ali morate znati osnovnu implementaciju povezanih listi koju ste naučili u ovom vodiču. Nadam se da ste se lepo proveli učeći novi koncept.
Srećno kodiranje 🙂