Lista: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Sid~plwiki (dyskusja | edycje) m Dodano odnośnik do dokumentu opisującego prostą implementację listy w C. |
m →Wskaźnikowa: xor linked list |
||
Linia 41:
Powyższe cechy można prawie dowolnie łączyć, co daje możliwość stworzenia wielu różnych implementacji listy, zależnie od potrzeb.
====Lista dwukierunkowa z jednym wskaźnikiem====
Istnieje możliwość realizacji takiej listy, wtedy gdy:
# wskaźnik można utożsamiać z liczbą i wykonywać na nim działania bitowe,
# wskaźnik pusty ma wartość liczbową 0.
Wówczas pojedynczy wskaźnik zawiera [[xor|różnicę symetryczną (xor)]] wartości liczbowej wskaźników na poprzedni i następny element listy. Podczas przechodzenia listy pamiętany jest rzeczywisty wskaźnik uprzednio odwiedzonego elementu i dzięki własności <math>X \oplus (X \oplus Y) = Y</math> można z zakodowanej liczby odtworzyć albo poprzedni albo następny element, w zależności od kierunku przeglądania listy. Warunek 2. gwarantuje, że wskaźniki na pierwszej i ostatniej pozycji można odkodować natychmiast.
Zaletą takiej reprezentacji jest oszczędność pamięci (jeden wskaźnik, zamiast dwóch), wadą natomiast utrudnione przeglądanie - jeśli nie rozpoczyna się od pierwszego lub ostatniego elementu, potrzeba znać co najmniej dwa wskaźniki w celu odkodowania rzeczywistych wartości.
== Zobacz też ==
| |||