Az adatstruktúrák kulcsszerepet játszanak a programozási világban. Segítenek abban, hogy adatainkat hatékonyan felhasználható módon rendszerezzük.
Ebben az oktatóanyagban az egyszeri hivatkozású listáról és a duplán linkelt listáról fogunk tanulni.
A linkelt lista egy lineáris adatstruktúra. Nem tárolja az adatokat összefüggő memóriahelyeken, például tömbökön. És minden egyes összekapcsolt elemet csomópontnak neveznek, és a mutatók segítségével kapcsolódnak össze. A hivatkozott lista első csomópontját fejnek nevezzük.
A linkelt lista mérete dinamikus. Tehát tetszőleges számú csomópontunk lehet, hacsak nem áll rendelkezésre a tárhely az eszközben.
A linkelt listáknak két típusa van. Nézzük meg egyenként a részletes bemutatót róluk.
Tartalomjegyzék
#1. Egyedül linkelt lista
Az egyszeresen csatolt lista egyetlen mutatót tartalmaz, amely a csatolt lista következő csomópontjához kapcsolódik. A linkelt listában minden csomóponthoz el kell tárolnunk az adatokat és a mutatót.
A csatolt lista utolsó csomópontja a nullát tartalmazza a következő mutatóként, amely a hivatkozott lista végét jelzi.
Az alábbi linken láthatja az illusztrációt.
Most már teljes mértékben megértjük az egyedileg összekapcsolt listát. Lássuk a Pythonban való megvalósítás lépéseit.
Egyedül linkelt lista megvalósítás
1. Az első lépés a csatolt lista csomópontjának létrehozása.
Hogyan kell létrehozni?
A Pythonban egyszerűen létrehozhatjuk a csomópontot az osztály használatával. Az osztály adatokat és egy mutatót tartalmaz a következő csomóponthoz.
Nézd meg a csomópont kódját.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
A csomópontot bármilyen típusú adattal létrehozhatjuk a fenti osztály használatával. Majd meglátjuk egy kicsit.
Most nálunk van a csomópont. Ezután létre kell hoznunk egy linkelt listát több csomóponttal. Hozzunk létre egy másik osztályt egy linkelt listához.
2. Hozzon létre egy LinkedList nevű osztályt None értékre inicializált fejjel. Lásd az alábbi kódot.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Nálunk vannak a Node és a LinkedList osztályok. Hogyan illeszthetünk be új csomópontot a hivatkozott listába? Egy egyszerű válasz lehet a LinkedList osztály metódusának használata. Igen, az jó lenne. Írjunk egy metódust egy új csomópont beszúrására a hivatkozott listába.
Ahhoz, hogy egy új csomópontot beszúrhassunk a linkelt listába, bizonyos lépéseket kell követnünk.
Lássuk őket.
- Ellenőrizze, hogy a fej üres-e vagy sem.
- Ha a fej üres, akkor rendelje hozzá az új csomópontot a fejhez.
- Ha a fej nem üres, szerezze be a hivatkozott lista utolsó csomópontját.
- Rendelje hozzá az új csomópontot az utolsó csomópont következő mutatójához.
Lássuk a kódot egy új csomópont beillesztéséhez a hivatkozott listába.
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
Hurrá! befejeztük az új csomópont beszúrásának módszerét a hivatkozott listába. Hogyan érhetjük el a csomópontok adatait a linkelt listából?
Ahhoz, hogy a csatolt listából hozzáférhessünk az adatokhoz, a következő mutató segítségével ismételgetnünk kell a hivatkozott oldalon, ahogyan az utolsó csomópontot tesszük a beillesztési metódusban. Írjunk egy metódust a LinkedList osztályba, amely kinyomtatja az összes csomópont adatot a linkelt listában.
4. Kövesse az alábbi lépéseket a csatolt listában lévő összes csomóponti adat kinyomtatásához.
- Változó inicializálása fejjel.
- Írjon egy ciklust, amely addig iterál, amíg el nem érjük a hivatkozott lista végét.
- Nyomtassa ki a csomópont adatait.
- Mozgassa a következő mutatót
Lássuk a kódot.
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')
Fú! elvégeztük a kapcsolódó létrehozását a szükséges módszerekkel. Teszteljük a linkelt listát úgy, hogy néhány adattal példányosítjuk.
A csomópontot Node(1) kóddal tudjuk létrehozni. Lássuk a linkelt lista megvalósításának teljes kódját a mintahasználattal együtt.
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()
Futtassa a fenti programot a következő eredmény eléréséhez.
1->2->3->4->5->6->7->Null
A linkelt listához ennyi. Most már tudja, hogyan valósítson meg egy egyedileg összekapcsolt listát. Az egyszeresen linkelt lista ismeretében könnyen megvalósítható a duplán linkelt lista. Ugorjunk bele az oktatóanyag következő részébe.
#2. Duplán linkelt lista
A duplán linkelt lista két mutatót tartalmaz, amelyek az előző csomóponthoz és a csatolt lista következő csomópontjához kapcsolódnak. A linkelt lista minden csomópontjához el kell tárolnunk az adatokat és két mutatót.
Az első csomópont előző mutatója nulla, az utolsó csomópont következő mutatója pedig nulla a csatolt lista mindkét oldalán való végét ábrázolva.
Az alábbi linken láthatja az illusztrációt.
A duplán linkelt lista is hasonló lépéseket tartalmaz, mint az egyszeresen linkelt lista megvalósítása. Ugyanazok a dolgok újbóli elmagyarázása unalmas lesz számodra. Menjen végig a kódon minden lépésben, és nagyon gyorsan megérti. Gyerünk.
Duplán linkelt lista megvalósítás
1. Csomópont létrehozása a duplán linkelt listához az előző csomópont-mutatóval, adatokkal és a következő csomópont-mutatóval.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Duplán linkelt listaosztály.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Egy módszer új csomópont beszúrására a duplán linkelt listába.
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. Egy módszer a duplán linkelt listaadatok megjelenítésére.
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()
Láttuk a duplán linkelt lista kódját. És nincs kód a duplán linkelt listaosztály használatához. Az neked. Használja az egyszeresen linkelt listához hasonló, kétszeresen linkelt listaosztályt. Jó szórakozást 🙂
Következtetés
A linkelt listák alapján sok problémát találhat. De ismernie kell az ebben az oktatóanyagban megtanult hivatkozás alapvető megvalósítását. Remélem, jól érezte magát az új koncepció elsajátításában.
Boldog kódolást 🙂