Datastrukturer spiller en nøkkelrolle i programmeringsverdenen. De hjelper oss med å organisere dataene våre på en måte som kan brukes effektivt.
I denne opplæringen skal vi lære om den enkeltlenkede listen og den dobbeltlenkede listen.
En koblet liste er en lineær datastruktur. Den lagrer ikke dataene i sammenhengende minneplasseringer som matriser. Og hvert element i linked kalles en node, og de kobles sammen ved hjelp av pekerne. Den første noden i den koblede listen kalles hodet.
Størrelsen på den koblede listen er dynamisk. Så vi kan ha et hvilket som helst antall noder vi vil med mindre lagringen er tilgjengelig i enheten.
Det finnes to typer koblede lister. La oss se den detaljerte opplæringen om dem én etter én.
Innholdsfortegnelse
#1. Enkeltlenket liste
En enkeltlenket liste inneholder en enkelt peker koblet til neste node i den koblede listen. Vi må lagre dataene og pekeren for hver node i den koblede listen.
Den siste noden i den koblede listen inneholder null som neste peker for å representere slutten på den koblede listen.
Du kan se illustrasjonen av en lenket nedenfor.
Nå har vi en full forståelse av en enkeltlenket liste. La oss se trinnene for å implementere det i Python.
Enkeltkoblet listeimplementering
1. Det første trinnet er å lage noden for den koblede listen.
Hvordan lage den?
I Python kan vi enkelt lage noden ved å bruke klassen. Klassen inneholder data og en peker for neste node.
Se på koden for noden.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Vi kan lage noden med alle typer data ved å bruke klassen ovenfor. Vi får se det om litt.
Nå har vi noden med oss. Deretter må vi lage en koblet liste med flere noder. La oss lage en annen klasse for en koblet liste.
2. Lag en klasse kalt LinkedList med head initialisert til None. Se koden nedenfor.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Vi har Node- og LinkedList-klasser med oss. Hvordan setter vi inn en ny node i den koblede listen? Et enkelt svar kan være å bruke en metode i LinkedList-klassen. Ja, det ville vært fint. La oss skrive en metode for å sette inn en ny node i den koblede listen.
For å sette inn en ny node i den koblede listen, må vi følge visse trinn.
La oss se dem.
- Sjekk om hodet er tomt eller ikke.
- Hvis hodet er tomt, tilordne den nye noden til hodet.
- Hvis hodet ikke er tomt, hent den siste noden i den koblede listen.
- Tilordne den nye noden til den siste noden neste pekeren.
La oss se koden for å sette inn en ny node i den koblede listen.
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
Hurra! vi har fullført metoden for å sette inn en ny node i den koblede listen. Hvordan kan vi få tilgang til nodedataene fra den koblede listen?
For å få tilgang til dataene fra den koblede listen, må vi iterere gjennom den koblede ved å bruke neste peker slik vi gjør for å få den siste noden i innsettingsmetoden. La oss skrive en metode i LinkedList-klassen for å skrive ut alle nodedata i den koblede listen.
4. Følg trinnene nedenfor for å skrive ut alle nodedata i den koblede listen.
- Initialiser en variabel med hode.
- Skriv en løkke som itererer til vi når slutten av den koblede listen.
- Skriv ut nodedataene.
- Flytt neste peker
La oss se koden.
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')
Puh! vi fullførte opprettelsen av den koblede med nødvendige metoder. La oss teste den koblede listen ved å instansiere den med noen data.
Vi kan lage noden med Node(1)-kode. La oss se den fullstendige koden for implementeringen av den koblede listen sammen med eksempelbruken.
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()
Kjør programmet ovenfor for å få følgende resultat.
1->2->3->4->5->6->7->Null
Det er det for den koblede listen. Nå vet du hvordan du implementerer en enkeltlenket liste. Du kan enkelt implementere den dobbeltlenkede listen med kunnskap om den enkeltlenkede listen. La oss dykke inn i neste del av opplæringen.
#2. Dobbeltkoblet liste
En dobbeltlenket liste inneholder to pekere koblet til forrige node og neste node i den koblede listen. Vi må lagre dataene og to pekere for hver node i den koblede listen.
Den forrige pekeren til den første noden er null og den neste pekeren til den siste noden er null for å representere slutten på den koblede listen på begge sider.
Du kan se illustrasjonen av en lenket nedenfor.
Den dobbeltkoblede listen har også lignende trinn som den enkeltkoblede listen i implementering. Igjen å forklare de samme tingene vil være kjedelig for deg. Gå gjennom koden i hvert trinn, og du vil forstå den veldig raskt. La oss gå.
Dobbel lenket listeimplementering
1. Opprette en node for den dobbeltkoblede listen med forrige nodepeker, data og neste nodepeker.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Dobbeltkoblet listeklasse.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. En metode for å sette inn en ny node i den dobbeltkoblede listen.
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. En metode for å vise de dobbeltkoblede listedataene.
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()
Vi har sett koden til den dobbeltkoblede listen. Og det er ingen kode for bruken av den dobbeltkoblede listeklassen. Det er til deg. Bruk den dobbeltkoblede listeklassen som ligner på den enkeltlenkede listen. Ha det gøy 🙂
Konklusjon
Du kan finne mange problemer basert på koblede lister. Men du må kjenne til den grunnleggende implementeringen av de koblede som du har lært i denne opplæringen. Håper du hadde en flott tid å lære det nye konseptet.
Lykke til med koding 🙂