Python – Gekoppelde Lijsten
Een gekoppelde lijst is een opeenvolging van data-elementen, die via links met elkaar verbonden zijn. Elk data element bevat een verbinding met een ander data element in de vorm van een pointer. Python heeft geen gelinkte lijsten in zijn standaard bibliotheek. We implementeren het concept van gelinkte lijsten met behulp van het concept van nodes zoals besproken in het vorige hoofdstuk. We hebben reeds gezien hoe we een node klasse creëren en hoe we de elementen van een node kunnen traceren. In dit hoofdstuk gaan we de types van gelinkte lijsten bestuderen die bekend staan als singly linked lists. In dit type datastructuur is er slechts één link tussen twee data elementen. We maken zo’n lijst en maken aanvullende methoden om elementen in de lijst in te voegen, bij te werken en te verwijderen.
Creatie van gekoppelde lijst
Een gekoppelde lijst wordt gemaakt met behulp van de node-klasse die we in het vorige hoofdstuk hebben bestudeerd. We maken een Node object en maken een andere klasse om dit ode object te gebruiken. We geven de juiste waarden door aan het node object om naar de volgende data elementen te wijzen. Het onderstaande programma maakt een gelinkte lijst met drie data elementen. In de volgende sectie zullen we zien hoe we de gelinkte lijst kunnen doorkruisen.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = Nonelist1 = SLinkedList()list1.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")# Link first Node to second nodelist1.headval.nextval = e2# Link second Node to third nodee2.nextval = e3
Een gelinkte lijst doorkruisen
Singly gelinkte lijsten kunnen alleen in voorwaartse richting worden doorkruist, beginnend bij het eerste data-element. We drukken gewoon de waarde van het volgende data-element af door de pointer van het volgende knooppunt aan het huidige data-element te koppelen.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")# Link first Node to second nodelist.headval.nextval = e2# Link second Node to third nodee2.nextval = e3list.listprint()
Wanneer de bovenstaande code wordt uitgevoerd, levert dat het volgende resultaat op:
MonTueWed
Insertie in een gekoppelde lijst
Het invoegen van een element in de gekoppelde lijst houdt in dat de pointers van de bestaande nodes opnieuw worden toegewezen aan het nieuw ingevoegde node. Afhankelijk van of het nieuwe data element aan het begin, in het midden of aan het eind van de gelinkte lijst wordt ingevoegd, hebben we de volgende scenario’s.
Invoegen aan het begin van de gelinkte lijst
Dit houdt in dat de volgende pointer van de nieuwe data node naar de huidige head van de gelinkte lijst wordt gewezen. Dus de huidige head van de gelinkte lijst wordt het tweede data element en de nieuwe node wordt de head van de gelinkte lijst.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None# Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextval def AtBegining(self,newdata): NewNode = Node(newdata)# Update the new nodes next val to existing node NewNode.nextval = self.headval self.headval = NewNodelist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")list.headval.nextval = e2e2.nextval = e3list.AtBegining("Sun")list.listprint()
Wanneer de bovenstaande code wordt uitgevoerd, levert dat het volgende resultaat op:
SunMonTueWed
Invoegen aan het einde van de gekoppelde lijst
Dit houdt in dat de volgende pointer van de huidige laatste node van de gekoppelde lijst naar de nieuwe data node wordt gewezen. Dus de huidige laatste node van de gelinkte lijst wordt de op een na laatste data node en de nieuwe node wordt de laatste node van de gelinkte lijst.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None# Function to add newnode def AtEnd(self, newdata): NewNode = Node(newdata) if self.headval is None: self.headval = NewNode return laste = self.headval while(laste.nextval): laste = laste.nextval laste.nextval=NewNode# Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")list.headval.nextval = e2e2.nextval = e3list.AtEnd("Thu")list.listprint()
Wanneer de bovenstaande code wordt uitgevoerd, levert dat het volgende resultaat op:
MonTueWedThu
Invoegen tussen twee Data Nodes
Hierbij wordt de pointer van een specifieke node veranderd om naar de nieuwe node te wijzen. Dat is mogelijk door zowel de nieuwe node als de bestaande node door te geven waarna de nieuwe node wordt ingevoegd.Dus definiëren we een extra klasse die de volgende pointer van de nieuwe node zal veranderen in de volgende pointer van de middelste node. Vervolgens wijzen we de nieuwe node toe aan de volgende pointer van de middelste node.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None# Function to add node def Inbetween(self,middle_node,newdata): if middle_node is None: print("The mentioned node is absent") return NewNode = Node(newdata) NewNode.nextval = middle_node.nextval middle_node.nextval = NewNode# Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Thu")list.headval.nextval = e2e2.nextval = e3list.Inbetween(list.headval.nextval,"Fri")list.listprint()
Wanneer de bovenstaande code wordt uitgevoerd, levert dat het volgende resultaat op:
MonTueFriThu
Een item uit een gelikete lijst verwijderen
We kunnen een bestaande node verwijderen met behulp van de sleutel voor die node. In het onderstaande programma lokaliseren we de vorige node van de node die verwijderd moet worden. Vervolgens wijzen we de volgende pointer van deze node naar de volgende node van de node die verwijderd moet worden.
class Node: def __init__(self, data=None): self.data = data self.next = Noneclass SLinkedList: def __init__(self): self.head = None def Atbegining(self, data_in): NewNode = Node(data_in) NewNode.next = self.head self.head = NewNode# Function to remove node def RemoveNode(self, Removekey): HeadVal = self.head if (HeadVal is not None): if (HeadVal.data == Removekey): self.head = HeadVal.next HeadVal = None return while (HeadVal is not None): if HeadVal.data == Removekey: break prev = HeadVal HeadVal = HeadVal.next if (HeadVal == None): return prev.next = HeadVal.next HeadVal = None def LListprint(self): printval = self.head while (printval): print(printval.data), printval = printval.nextllist = SLinkedList()llist.Atbegining("Mon")llist.Atbegining("Tue")llist.Atbegining("Wed")llist.Atbegining("Thu")llist.RemoveNode("Tue")llist.LListprint()
Wanneer de bovenstaande code wordt uitgevoerd, levert dat het volgende resultaat op:
ThuWedMon