Datastrukturer spiller en nøglerolle i programmeringsverdenen. De hjælper os med at organisere vores data på en måde, der kan bruges effektivt.
I denne vejledning skal vi lære om den enkelt-linkede liste og den dobbelt-linkede liste.
En sammenkædet liste er en lineær datastruktur. Det gemmer ikke dataene i sammenhængende hukommelsesplaceringer som arrays. Og hvert element i linked kaldes en node, og de er forbundet ved hjælp af pointerne. Den første node i den sammenkædede liste kaldes hovedet.
Størrelsen på den linkede liste er dynamisk. Så vi kan have et hvilket som helst antal noder, som vi ønsker, medmindre lageret er tilgængeligt i enheden.
Der er to typer sammenkædede lister. Lad os se den detaljerede tutorial om dem én efter én.
Indholdsfortegnelse
#1. Enkeltforbundet liste
En enkelt linket liste indeholder en enkelt pointer forbundet til den næste node i den linkede liste. Vi er nødt til at gemme data og pointer for hver node i den sammenkædede liste.
Den sidste node i den sammenkædede liste indeholder null som den næste pointer, der repræsenterer slutningen af den sammenkædede liste.
Du kan se illustrationen af en linket nedenfor.
Nu har vi en fuld forståelse af en enkelt-linket liste. Lad os se trinene til at implementere det i Python.
Implementering af enkeltstående liste
1. Det første trin er at oprette noden til den sammenkædede liste.
Hvordan skaber man det?
I Python kan vi nemt oprette noden ved hjælp af klassen. Klassen indeholder data og en pointer til den næste 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 oprette noden med enhver type data ved hjælp af ovenstående klasse. Vi ser det om lidt.
Nu har vi noden med os. Dernæst skal vi oprette en sammenkædet liste med flere noder. Lad os oprette en anden klasse til en sammenkædet liste.
2. Opret en klasse kaldet LinkedList med hoved initialiseret til Ingen. Se koden nedenfor.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Vi har Node og LinkedList klasser med os. Hvordan indsætter vi en ny node i den linkede liste? Et simpelt svar kan være at bruge en metode i klassen LinkedList. Ja, det ville være rart. Lad os skrive en metode til at indsætte en ny node i den sammenkædede liste.
For at indsætte en ny node i den linkede liste, skal vi følge visse trin.
Lad os se dem.
- Tjek om hovedet er tomt eller ej.
- Hvis hovedet er tomt, så tildel den nye node til hovedet.
- Hvis hovedet ikke er tomt, skal du hente den sidste node på den linkede liste.
- Tildel den nye node til den sidste node næste pointer.
Lad os se koden for at indsætte en ny node i den sammenkædede liste.
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 fuldført metoden til at indsætte en ny node i den linkede liste. Hvordan kan vi få adgang til nodedataene fra den sammenkædede liste?
For at få adgang til dataene fra den linkede liste, skal vi iterere gennem de linkede ved hjælp af den næste pointer, som vi gør for at få den sidste node i indsættelsesmetoden. Lad os skrive en metode inde i LinkedList-klassen til at udskrive alle nodedata i den sammenkædede liste.
4. Følg nedenstående trin for at udskrive alle nodedata på den sammenkædede liste.
- Initialiser en variabel med hoved.
- Skriv en løkke, der itererer, indtil vi når slutningen af den linkede liste.
- Udskriv nodedataene.
- Flyt den næste markør
Lad os 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')
Pyha! vi fuldførte oprettelsen af linket med nødvendige metoder. Lad os teste den linkede liste ved at instansiere den med nogle data.
Vi kan oprette noden med Node(1) kode. Lad os se den komplette kode for den linkede listeimplementering sammen med eksempelbrugen.
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()
Kør ovenstående program for at få følgende resultat.
1->2->3->4->5->6->7->Null
Det er det for den linkede liste. Nu ved du, hvordan du implementerer en enkelt-linket liste. Du kan nemt implementere den dobbelt-linkede liste med kendskab til den enkelt-linkede liste. Lad os dykke ned i næste afsnit af selvstudiet.
#2. Dobbeltforbundet liste
En dobbeltkædet liste indeholder to pointere, der er forbundet til den forrige node og den næste node i den sammenkædede liste. Vi skal gemme dataene og to pointere for hver node i den sammenkædede liste.
Den forrige pointer for den første node er nul, og den næste pointer for den sidste node er nul for at repræsentere slutningen af den sammenkædede liste på begge sider.
Du kan se illustrationen af en linket nedenfor.
Den dobbelt-linkede liste har også lignende trin som den enkelt-linkede liste i implementering. Igen at forklare de samme ting vil være kedeligt for dig. Gå gennem koden i hvert trin, og du vil forstå det meget hurtigt. Lad os gå.
Dobbeltforbundet listeimplementering
1. Oprettelse af en node til den dobbeltforbundne liste med den forrige nodemarkør, data og næste nodemarkør.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Dobbeltforbundet listeklasse.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. En metode til at indsætte en ny node i den dobbeltforbundne liste.
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 til at vise de dobbeltforbundne listedata.
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 set koden for den dobbeltforbundne liste. Og der er ingen kode til brugen af den dobbeltlinkede listeklasse. Det er til dig. Brug den dobbeltlinkede listeklasse svarende til den enkeltlinkede liste. God fornøjelse 🙂
Konklusion
Du kan finde mange problemer baseret på linkede lister. Men du skal kende den grundlæggende implementering af det linkede, som du har lært i denne tutorial. Håber du havde en god tid med at lære det nye koncept.
God kodning 🙂