I programmeringens verden spiller datastrukturer en avgjørende rolle. De hjelper oss å organisere informasjonen vår på en måte som muliggjør effektiv bruk og manipulering.
I denne veiledningen skal vi utforske to viktige datastrukturer: den enkeltlenkede listen og den dobbeltlenkede listen.
En lenket liste er en type lineær datastruktur. I motsetning til matriser, lagrer den ikke dataene i sammenhengende minneområder. Hvert element i en lenket liste, kalt en node, er koblet til det neste elementet ved hjelp av pekere. Den første noden i listen kalles hodet.
En viktig egenskap ved lenkede lister er deres dynamiske størrelse. Dette betyr at vi kan legge til eller fjerne noder etter behov, så lenge det er ledig minne i enheten.
Det finnes primært to typer lenkede lister. La oss se nærmere på hver av dem.
#1. Enkeltlenket liste
En enkeltlenket liste er kjennetegnet ved at hver node inneholder en enkelt peker, som refererer til neste node i listen. Hver node lagrer sin egen data samt denne pekeren til neste node.
Den siste noden i en enkeltlenket liste har en null-peker som sin neste peker, noe som signaliserer slutten på listen.
Nedenfor ser du en illustrasjon av en typisk enkeltlenket liste.
Nå som vi har en grunnleggende forståelse av enkeltlenkede lister, la oss se på hvordan vi kan implementere dem i Python.
Implementasjon av enkeltlenket liste
1. Det første steget er å definere hvordan en node i den lenkede listen skal se ut.
Hvordan gjør vi det?
I Python kan vi enkelt lage en node ved hjelp av en klasse. Denne klassen vil inneholde dataene noden holder, i tillegg til en peker til neste node.
Her er koden for en node:
class Node:
def __init__(self, data):
## data for noden
self.data = data
## peker til neste node
self.next = None
Vi kan opprette noder med alle typer data ved å bruke denne klassen. Vi skal se et eksempel på det om litt.
Nå som vi har en node, må vi lage en lenket liste som består av flere noder. La oss definere en ny klasse for en lenket liste.
2. Lag en klasse kalt LinkedList, hvor hodet er initialisert til None. Se koden nedenfor:
class LinkedList:
def __init__(self):
## initialiserer hodet med None
self.head = None
3. Vi har nå både Node- og LinkedList-klassene. Men hvordan legger vi til nye noder i den lenkede listen? Et enkelt svar er å bruke en metode i LinkedList-klassen. La oss lage en metode for å legge til nye noder.
For å legge til en ny node i listen, må vi følge noen trinn.
La oss gå gjennom dem:
- Sjekk om hodet er tomt eller ikke.
- Hvis hodet er tomt, setter vi den nye noden som hodet.
- Hvis hodet ikke er tomt, finner vi den siste noden i listen.
- Vi tilordner den nye noden til den siste nodens «neste»-peker.
Her er koden for å legge til en ny node i den lenkede listen:
class LinkedList:
####
def insert(self, new_node):
## sjekker om hodet er tomt
if self.head:
## henter den siste noden
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## tilordner den nye noden til den siste nodens neste-peker
last_node.next = new_node
else:
## hodet er tomt
## tilordner den nye noden til hodet
self.head = new_node
Flott! Vi har fullført metoden for å legge til noder i den lenkede listen. Men hvordan får vi tilgang til dataene i nodene?
For å få tilgang til dataene i den lenkede listen, må vi iterere gjennom listen ved å følge «neste»-pekeren, på samme måte som vi fant den siste noden i innsettingsmetoden. La oss skrive en metode i LinkedList-klassen for å skrive ut alle nodenes data.
4. Følg trinnene nedenfor for å skrive ut dataene i alle nodene:
- Initialiser en variabel med hodet.
- Skriv en løkke som itererer til vi når slutten av den lenkede listen.
- Skriv ut nodens data.
- Flytt til neste peker.
Her er koden:
class LinkedList:
####
def display(self):
## variabel for iterasjon
temp_node = self.head
## itererer til vi når slutten av den lenkede listen
while temp_node != None:
## skriver ut nodens data
print(temp_node.data, end='->')
## beveger oss til neste node
temp_node = temp_node.next
print('Null')
Puh! Vi har fullført opprettelsen av den lenkede listen med de nødvendige metodene. La oss teste den ved å instansiere den med noen data.
Vi kan lage noder med koden Node(1). La oss se den fullstendige koden for implementasjonen av den lenkede listen, sammen med et eksempel på bruk:
class Node:
def __init__(self, data):
## data for noden
self.data = data
## peker til neste node
self.next = None
class LinkedList:
def __init__(self):
## initialiserer hodet med None
self.head = None
def insert(self, new_node):
## sjekker om hodet er tomt
if self.head:
## henter den siste noden
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## tilordner den nye noden til den siste nodens neste-peker
last_node.next = new_node
else:
## hodet er tomt
## tilordner den nye noden til hodet
self.head = new_node
def display(self):
## variabel for iterasjon
temp_node = self.head
## itererer til vi når slutten av den lenkede listen
while temp_node != None:
## skriver ut nodens data
print(temp_node.data, end='->')
## beveger oss til neste node
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## instansierer den lenkede listen
linked_list = LinkedList()
## legger til data i den lenkede listen
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))
## skriver ut den lenkede listen
linked_list.display()
Kjør programmet ovenfor for å få følgende resultat:
1->2->3->4->5->6->7->Null
Det var alt om den enkeltlenkede listen. Nå vet du hvordan du implementerer den. Du kan enkelt implementere den dobbeltlenkede listen med kunnskapen du har fått om enkeltlenkede lister. La oss fortsette til neste del av veiledningen.
#2. Dobbeltlenket liste
En dobbeltlenket liste skiller seg fra en enkeltlenket ved at hver node har to pekere: en til forrige node og en til neste node i listen. Hver node lagrer dermed sine egne data samt disse to pekerne.
Den forrige pekeren til den første noden er null, og den neste pekeren til den siste noden er null. Dette markerer begynnelsen og slutten av listen fra begge sider.
Nedenfor er en illustrasjon av en dobbeltlenket liste:
Implementeringen av en dobbeltlenket liste følger lignende prinsipper som en enkeltlenket liste. Istedenfor å gjenta de samme forklaringene, går vi gjennom koden trinn for trinn. Vi er sikre på at du vil forstå den raskt.
Implementering av dobbeltlenket liste
1. Opprett en node for den dobbeltlenkede listen, som inkluderer en peker til forrige node, data, og en peker til neste node:
class Node:
def __init__(self, data):
## peker til forrige node
self.prev = None
## data for noden
self.data = data
## peker til neste node
self.next = None
2. Klassen for den dobbeltlenkede listen:
class LinkedList:
def __init__(self):
## initialiserer hodet med None
self.head = None
3. En metode for å legge til en ny node i den dobbeltlenkede listen:
class LinkedList:
####
def insert(self, new_node):
## sjekker om hodet er tomt
if self.head:
## henter den siste noden
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## tilordner den siste noden til den nye nodens forrige-peker
new_node.prev = last_node
## tilordner den nye noden til den siste nodens neste-peker
last_node.next = new_node
4. En metode for å vise dataene i den dobbeltlenkede listen:
class LinkedList:
####
def display(self):
## skriver ut dataene i normal rekkefølge
print("Normal rekkefølge: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## skriver ut dataene i omvendt rekkefølge ved hjelp av forrige-pekeren
print("Omvendt rekkefølge: ", end='')
## henter den siste noden
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 nå sett koden for den dobbeltlenkede listen. Det er ikke gitt kode for å bruke denne klassen, men vi overlater det til deg å prøve den, på samme måte som med den enkeltlenkede listen. Ha det gøy! 🙂
Konklusjon
Det finnes mange programmeringsoppgaver som kan løses ved hjelp av lenkede lister. Det er viktig å forstå det grunnleggende i implementasjonen, noe vi har dekket i denne veiledningen. Vi håper at du har hatt en fin opplevelse med å lære dette nye konseptet.
Lykke til med kodingen! 🙂