W każdym razie sądziłem, że listy dwukierunkowe to coś stosownego na czasy, kiedy nie było jeszcze tablic dynamicznych, ale tym artykułem zmieniło mi optykę.
To zależy – w TP co prawda nie było typowych macierzy dynamicznych, ale i tak były funkcje umożliwiające dynamiczną alokację pamięci. Mowa oczywiście o GetMem
, AllocMem
, ReallocMem
i FreeMem
. Tyle że aby móc z nich wygodnie korzystać, należało je sobie w ”coś” opakować (np. w object
, czyli w odpowiednik dzisiejszych zaawansowanych rekordów, bo klas jeszcze nie było).
Chętnie się w to zagłębię, skoro jest sygnał, że ma to sens […]
Listy dwukierunkowe mają sens, przede wszystkim wtedy, gdy dużo i często dodajemy do kontenera lub z niego usuwamy. Brak realokacji dużych bloków pamięci znacznie skraca operacje modyfikacji listy.
Napisałeś, że listy dwukierunkowe nie potrzebują ciągłego bloku pamięci i dlatego mogą zawierać dowolną ilość węzłów.
Tak, macierze zawsze alokowane są jako jeden ciągły blok pamięci, natomiast w przypadku list nie ma takiego ograniczenia. To sprawia, że dodanie węzła do listy oznacza jedynie alokację pamięci dla nowego węzła – nic więcej.
Lista, którą opracowałem i przedstawiłem w artykule, bazuje na konstrukcji standardowej listy dwukierunkowej. Dodawanie i usuwanie węzłów jest szybkie – to dla list standard. Natomiast słabym punktem jest iterowanie po kolejnych węzłach – edycja tego konkretnego oznacza jego uprzednie odszukanie, czyli przeiterowanie po wszystkich węzłach, od głowy lub ogona. Dlatego też swoją listę podrasowałem pod tym kątem, dodając węzeł-znacznik – ten zawsze zawiera wskaźnik ostatnio użytego węzła. To znacznie skraca czas przeszukiwania listy.
Oczywiście konstrukcja listy dwukierunkowej opakowana jest w wygodną klasę, dzięki czemu nie trzeba się samemu babrać wskaźnikami i dbać o jej poprawną budowę. Używa się jej identycznie jak TObjectList
– w środku dzieje się magia ze wskaźnikami, a na wierzchu operuje się na indeksach. Choć przydałoby się ją przerobić na generyczną…
Czy to jedna z różnic pomiędzy nimi a arrays of string i dlatego tak łatwo pakowałem się na OutOfMemory?
Na pewno ma to wpływ. Zwróć uwagę na to, że im większa macierz, tym większy blok pamięci trzeba zarezerwować w całości. Menedżer pamięci nie działa jak defragmentator – alokuje pamięć tam gdzie mu wygodnie, a nie po kolei. To sprawia, że pamięć jest poszatkowana – trochę zajętej, trochę wolnej, znów trochę zajętej i znów wolna dziura. W tak podziurawionej pamięci w pewnym momencie nie da się zaalokować wystarczająco dużego bloku – pomimo tego, że łącznie może być tej wolnej o wiele więcej, niż to wymagane.
Listy dają tu przewagę – każda najmniejsza wolna przestrzeń może być zagospodarowana. Czyli każdy blok o rozmiarze większym lub równym rozmiarowi pojedynczego węzła (dwa wskaźniki plus dane). Dzięki temu da się stworzyć o wiele więcej węzłów, bo można je poupychać w każdą wolną lukę w pamięci.
Oczywiście listy mają też swoje wady, jednak coś za coś.