Listy powiązane

Jedną z podstawowych struktur wykorzystywanych do przechowywania danych są listy powiązane. Ich dużą zaletą (przewagą np. nad tablicami) jest fakt, że na etapie ich tworzenia nie ma potrzeby definiowania ich docelowego rozmiaru. Jest tak dlatego, ponieważ kolejne elementy nie są przechowywane w pamięci jeden obok drugiego, ale wszędzie tam, gdzie jest wolne miejsce. Każdy element posiada adres następnego elementu na liście: pierwszy drugiego, drugi trzeciego itd. Dlatego jeśli tylko jest dostępne miejsce w pamięci komputera, możemy utworzyć nowy wpis.

Aditya Y. Bhargava w swojej książce “Algorytmy, ilustrowany przewodnik” napisał: “Trochę przypomina to szukanie skarbu. Idziemy pod pierwszy adres i dowiadujemy się tam, np. że: “Następny element znajduje się pod adresem 123“. Idziemy więc pod adres 123, a tam widnieje informacja: “Następny element znajduje się pod adresem 847” itd.”

Oczywiście implementacja listy powiązanej jest dostępna w składni języka i nie trzeba jej pisać samemu, ale dla celów treningu możemy to zrobić.

Jak to działa?

Na potrzeby naszego ćwiczenia zakładamy, że w liście będziemy przechowywać tylko liczby. Funkcja insertion() prosi użytkownika o podanie liczby lub litery. Jeśli podana jest litera to wyświetlana jest zawartość listy LL i program się kończy. Jeśli użytkownik poda liczbę, jest ona przekazywana do funkcji insert() wewnątrz instancji LL klasy LinkedList.

Funkcja insertion() tworzy zmienną newNode i przypisuje do niej instancję klasy Node, która jako argument przyjmuje liczbę podaną przez użytkownika. To jest newNode:

Jeśli zmienna self.head klasy LinkedList nie wskazuje na nic, 

to zaczyna wskazywać na Node pod zmienną newNode. 

Wtedy też do zmiennej self.previous przypisujemy ten sam newNode.

Użytkownik podaje kolejną liczbę. Tworzony jest nowy Node.

Zmienna self.head wskazuje już na nasz pierwszy Node. Do zmiennej current przypisujemy nowo utworzony Node – newNode. 

Do argumentu next naszego poprzedniego Node (previous.next) przypisujemy current node, 

czyli najnowszy Node – newNode. 

Dzięki temu mamy relację między Nodami. Teraz na zmienną self.previous nadpisujemy zmienną current, 

czyli najnowszy Node – newNode.

użytkownik podaje kolejną liczbę. Tworzony jest nowy Node.

self.head pozostaje bez zmian i wskazuje pierwszy Node. Zmienna current wskazuje na świeży newNode. 

Argumentowi next naszego poprzedniego Noda (previous.next) przypisujemy najnowszy newNode i w ten sposób tworzymy relację międzu drugim a trzecim Nodem.

Kolejne kroki są już powtórzeniem dotychczasowych działań.

Poniżej zamieszczam kod naszego programu:

Tworzymy klasę Node

Klasa posiada funkcję __init__(self), która przyjmuje argumenty: data, next, previous.

Argumenty next i previous są z początku równe None

class Node:

   def __init__(self, data, next=None, previous=None):

       self.data = data

       self.next = next

       self.previous = previous

Tworzymy klasę LinkedList

Klasa LinkedList posiada funkcję inicjującą

__init__(self) i w tej funkcji znajduje się argument self.head = None

class LinkedList:

   def __init__(self):

       self.head = None

       self.previous = None

W klasie LinkedList tworzymy funkcję do wstawiania nowych argumentów do listy

   def insert(self, data):

       newNode = Node(data)

       if self.head:

           current = newNode

           self.previous.next = current

           self.previous = current

       else:

           self.head = newNode

           self.previous = newNode

W klasie LinkedList tworzymy funkcję do wyświetlania zawartości listy

   def printLL(self):

       current = self.head

       while(current):

         print(current.data)

         current = current.next

Tworzymy instancję klasy LinkedList

LL = LinkedList()

Tworzymy funkcję która będzie pobierała dane od użytkownika i przekazywała je do naszej listy LL oraz modyfikowała listę.

def insertion():

   print("give number, type R to replace, D to delete, P to print or other letter exit")

   number = input()

   if number.isdigit():

       LL.insert(number)

       insertion()

   elif number == "R" or number == "r":

       number = input("enter number to be replaced")

       LL.replace(number)

       insertion()

   elif number == "D" or number == "d":

       number = input("enter number to be deleted")

       LL.delete(number)

       insertion()

   elif number == "P" or number == "p":

       LL.printLL()

       insertion()

   elif number == "E" or number == "e":

       return None

   else:

       print("No such command. Try again")

       insertion()

Na koniec wywołujemy funkcję

insertion()

To wszystko.

Podsumowanie

Listy powiązane są jedną z podstawowych struktur danych. Cechują się tym, że możemy do nich swobodnie dodawać kolejne elementy – jedynym warunkiem jest posiadanie wolnego miejsca na nowy element w pamięci. Nie musimy z góry rezerwować określonej ilości miejsca na dane. Natomiast, aby dostać się do konkretnego elementu w liście trzeba przejść przez wszystkie poprzedzające go elementy, ponieważ tylko w ten sposób uzyskamy adres, pod którym przechowywany jest nasz element.

Właściwości te sprawiają, że listy powiązane są odpowiednim wyborem, kiedy nie wiemy ile elementów będziemy finalnie przechowywać oraz jeśli nie przeszkadza nam to, że przy odczycie i zapisie danych musimy przeglądnąć całą listę.