Być może najprostszą trwałą strukturą danych jest lista jednokierunkowa, w którym każdy obiekt (ogniwo tej listy) posiada wskaźnik do następnego obiektu listy. Jest to struktura trwała, ponieważ możemy wziąć ogon listy, tzn. ostatnie k obiektów i dodawać nowe obiekty na przodzie tego ogona. Wtedy ten ogon nie będzie powielony; będzie współdzielony pomiędzy starą i nową listą. Dopóki zawartość ogona pozostanie niezmienna, to współdzielenie będzie niewidoczne dla programu.
Wiele często używanych struktur danych bazujących na wskaźnikach, takich jak drzewa czerwono-czarne i kolejki, mogą być łatwo zmienionych na wersje trwałe. Na przykład, odpowiednikiem tablicy może być VLista, struktura danych stworzona w 2002 przez Phila Bagwella.
Bibliografia
Linki zewnętrzne Making Data Structures Persistent (or Author's version) Persistent Data Structures (survey) Fully persistent arrays for efficient incremental updates and voluminous reads Real-Time Deques, Multihead Turing Machines, and Purely Functional Programming
Kategoria:Struktury danych