Datastrukturer spelar en nyckelroll i programmeringsvärlden. De hjälper oss att organisera vår data på ett sätt som kan användas effektivt.
I den här handledningen kommer vi att lära oss om den enkellänkade listan och den dubbellänkade listan.
En länkad lista är en linjär datastruktur. Den lagrar inte data i angränsande minnesplatser som arrayer. Och varje element i länkad kallas en nod och de är anslutna med hjälp av pekarna. Den första noden i den länkade listan kallas huvudet.
Storleken på den länkade listan är dynamisk. Så vi kan ha valfritt antal noder som vi vill om inte lagringen är tillgänglig i enheten.
Det finns två typer av länkade listor. Låt oss se den detaljerade handledningen om dem en efter en.
Innehållsförteckning
#1. Enkelt länkad lista
En enkellänkad lista innehåller en enda pekare kopplad till nästa nod i den länkade listan. Vi måste lagra data och pekare för varje nod i den länkade listan.
Den sista noden i den länkade listan innehåller null som nästa pekare för att representera slutet på den länkade listan.
Du kan se illustrationen av en länk nedan.
Nu har vi en fullständig förståelse för en enkellänkad lista. Låt oss se stegen för att implementera det i Python.
Implementering av en enda länkad lista
1. Det första steget är att skapa noden för den länkade listan.
Hur skapar man det?
I Python kan vi enkelt skapa noden med hjälp av klassen. Klassen innehåller data och en pekare för nästa nod.
Titta på koden för noden.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Vi kan skapa noden med vilken typ av data som helst med hjälp av ovanstående klass. Vi får se det om ett tag.
Nu har vi noden med oss. Därefter måste vi skapa en länkad lista med flera noder. Låt oss skapa en annan klass för en länkad lista.
2. Skapa en klass som heter LinkedList med huvudet initialiserat till None. Se koden nedan.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Vi har Node- och LinkedList-klasser med oss. Hur infogar vi en ny nod i den länkade listan? Ett enkelt svar kan vara att använda en metod i klassen LinkedList. Ja, det vore trevligt. Låt oss skriva en metod för att infoga en ny nod i den länkade listan.
För att infoga en ny nod i den länkade listan måste vi följa vissa steg.
Låt oss se dem.
- Kontrollera om huvudet är tomt eller inte.
- Om huvudet är tomt, tilldela sedan den nya noden till huvudet.
- Om huvudet inte är tomt, hämta den sista noden i den länkade listan.
- Tilldela den nya noden till den sista noden nästa pekare.
Låt oss se koden för att infoga en ny nod i den länkade listan.
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 slutfört metoden för att infoga en ny nod i den länkade listan. Hur kan vi komma åt noddata från den länkade listan?
För att komma åt data från den länkade listan måste vi iterera genom den länkade med nästa pekare som vi gör för att få den sista noden i insättningsmetoden. Låt oss skriva en metod i klassen LinkedList för att skriva ut alla noddata i den länkade listan.
4. Följ stegen nedan för att skriva ut alla noddata i den länkade listan.
- Initiera en variabel med huvud.
- Skriv en slinga som itererar tills vi når slutet av den länkade listan.
- Skriv ut noddata.
- Flytta nästa pekare
Låt 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 slutförde att skapa länken med nödvändiga metoder. Låt oss testa den länkade listan genom att instansiera den med lite data.
Vi kan skapa noden med Node(1)-kod. Låt oss se den fullständiga koden för den länkade listans implementering tillsammans med exempelanvändningen.
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 programmet ovan för att få följande resultat.
1->2->3->4->5->6->7->Null
Det var allt för den länkade listan. Nu vet du hur man implementerar en enkellänkad lista. Du kan enkelt implementera den dubbellänkade listan med kunskapen om den enkellänkade listan. Låt oss dyka in i nästa avsnitt av handledningen.
#2. Dubbelt länkad lista
En dubbellänkad lista innehåller två pekare kopplade till föregående nod och nästa nod i den länkade listan. Vi måste lagra data och två pekare för varje nod i den länkade listan.
Den föregående pekaren för den första noden är noll och nästa pekare för den sista noden är noll för att representera slutet av den länkade listan på båda sidor.
Du kan se illustrationen av en länk nedan.
Den dubbellänkade listan har också liknande steg som den enkellänkade listan i implementering. Att återigen förklara samma saker kommer att vara tråkigt för dig. Gå igenom koden i varje steg så förstår du den väldigt snabbt. Nu går vi.
Dubbelt länkad listimplementering
1. Skapa en nod för den dubbellänkade listan med föregående nodpekare, data och nästa nodpekare.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Dubbelt länkad listklass.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. En metod för att infoga en ny nod i den dubbellänkade listan.
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 metod för att visa dubbellänkade listdata.
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 för den dubbellänkade listan. Och det finns ingen kod för användningen av den dubbellänkade listklassen. Det är till dig. Använd den dubbellänkade listklassen som liknar den enkellänkade listan. Ha kul 🙂
Slutsats
Du kan hitta många problem baserat på länkade listor. Men du måste känna till den grundläggande implementeringen av de länkade som du har lärt dig i den här handledningen. Hoppas du hade en bra tid att lära dig det nya konceptet.
Glad kodning 🙂