Linked List – #PytaniaRekrutacyjne

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 NodenewNode

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

czyli najnowszy NodenewNode

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

czyli najnowszy NodenewNode.

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

 

Tworzymy klasę LinkedList

Klasa LinkedList posiada funkcję inicjującą

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

 

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

 

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

 

Tworzymy instancję klasy 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ę.

 

Na koniec wywołujemy funkcję

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ę.

ZOSTAW ODPOWIEDŹ

Please enter your comment!
Please enter your name here

Loading Facebook Comments ...