Python – Linked Lists
Lista połączona to sekwencja elementów danych, które są ze sobą połączone za pomocą odnośników. Każdy element danych zawiera połączenie z innym elementem danych w postaci wskaźnika. Python nie posiada list połączonych w swojej standardowej bibliotece. Koncepcję list połączonych implementujemy za pomocą koncepcji węzłów, omówionej w poprzednim rozdziale. Widzieliśmy już, jak tworzymy klasę węzłów i jak przemierzać elementy węzła.W tym rozdziale zajmiemy się typami list połączonych znanymi jako listy pojedynczo połączone. W tego typu strukturze danych istnieje tylko jedno połączenie pomiędzy dwoma dowolnymi elementami danych. Utworzymy taką listę i stworzymy dodatkowe metody do wstawiania, aktualizowania i usuwania elementów z listy.
Tworzenie listy połączonej
Listę połączoną tworzy się za pomocą klasy Node, którą studiowaliśmy w poprzednim rozdziale. Tworzymy obiekt Node i tworzymy kolejną klasę, która będzie korzystać z tego obiektu ody. Przekazujemy odpowiednie wartości przez obiekt Node, aby wskazać kolejne elementy danych. Poniższy program tworzy listę połączoną z trzema elementami danych. W następnej części zobaczymy jak przemierzać listę połączoną.
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
Przemierzanie listy połączonej
Listy połączone pozornie mogą być przemierzane tylko w kierunku forwrad, zaczynając od pierwszego elementu danych. Po prostu wypisujemy wartość następnego elementu danych poprzez przypisanie wskaźnika następnego węzła do bieżącego elementu danych.
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()
Po wykonaniu powyższego kodu otrzymamy następujący wynik:
MonTueWed
Insertion in a Linked List
Wstawienie elementu do listy połączonej wiąże się z ponownym przypisaniem wskaźników z istniejących węzłów do nowo wstawionego węzła. W zależności od tego, czy nowy element danych jest wstawiany na początku, w środku czy na końcu listy połączonej, mamy poniższe scenariusze.
Wstawianie na początku listy połączonej
Wiąże się to ze wskazaniem następnego wskaźnika nowego węzła danych do bieżącej głowy listy połączonej. Tak więc aktualny nagłówek listy połączonej staje się drugim elementem danych, a nowy węzeł staje się nagłówkiem listy połączonej.
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()
Gdy powyższy kod jest wykonywany, daje następujący wynik:
SunMonTueWed
Inserting at the End of the Linked List
Polega to na wskazaniu wskaźnika next aktualnego ostatniego węzła listy połączonej na nowy węzeł danych. Tak więc bieżący ostatni węzeł listy połączonej staje się drugim ostatnim węzłem danych, a nowy węzeł staje się ostatnim węzłem listy połączonej.
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()
Gdy powyższy kod jest wykonywany, daje następujący wynik:
MonTueWedThu
Wstawianie pomiędzy dwa węzły danych
Polega to na chaging’owaniu wskaźnika danego węzła tak, aby wskazywał na nowy węzeł. Jest to możliwe poprzez przekazanie zarówno nowego węzła jak i istniejącego węzła, po którym nowy węzeł zostanie wstawiony.Zdefiniujemy więc dodatkową klasę, która zmieni następny wskaźnik nowego węzła na następny wskaźnik węzła środkowego. Następnie przypisujemy nowy węzeł do następnego wskaźnika węzła środkowego.
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()
Po wykonaniu powyższego kodu otrzymujemy następujący wynik:
MonTueFriThu
Removing an Item form a Liked List
Istniejący węzeł możemy usunąć używając klucza dla tego węzła. W poniższym programie lokalizujemy poprzedni węzeł węzła, który ma zostać usunięty, a następnie wskazujemy następny wskaźnik tego węzła na następny węzeł węzła, który ma zostać usunięty.
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()
Po wykonaniu powyższego kodu otrzymujemy następujący wynik:
ThuWedMon