Czy mógłby ktoś mi wytłumaczyć sens implementacji listy na tablicy jednowymiarowej? Bo nie bardzo to rozumiem.
Listy na tablicach są często wybierane przez uczestników olimpiad informatycznych. Pojawiające się tam zadania dokładnie precyzują rozmiar maksymalnych danych oraz dostępną do wykorzystania pamięć.
No okej, ale po co przechowywać wskaźniki do poprzednich i kolejnych elementów w postaci indeksów jeśli wiadomo, że każdy następuje po sobie? Proszę o wytłumaczenie
ahaaaa więc to o to chodzi. dzięki :)
No okej, ale po co przechowywać wskaźniki do poprzednich i kolejnych elementów w postaci indeksów
To jest też kwestia nazewnictwa, co rozumiemy pod nazwą „lista”.
Na przykład w C# typ List to jest raczej odpowiednik vectora z C++ — dynamicznie alokowana tablica o zmiennym rozmiarze, bez przechowywania wskaźników na kolejny element.
Jakiś czas temu potrzebowałem napisać kontener coś w ten deseń.
vector jest fajną rzeczą, ale jego natura powoduje pewien problem, oto on:
std::vector<OBIEKT> obiekty; // tytułowy bohater
// dodajmy 3 obiekty
obiekty.push_back(OBIEKT(...));
obiekty.push_back(OBIEKT(...));
obiekty.push_back(OBIEKT(...));
// teraz załóżmy, że trzeba gdzieś na zewnątrz zwrócić wskaźniki do tych obiektów
OBIEKT* ptr0 = &obiekty[0];
OBIEKT* ptr1 = &obiekty[1];
OBIEKT* ptr2 = &obiekty[2];
// i wszystko jest ok dopóki nie usuwamy naszych obiektów
obiekty.erase(obiekty.begin()); // usuwamy pierwszy obiekt
I po erasie następuje przesunięcie wszystkich obiektów, a więc rzecz która powoduje, że nasze wskaźniki nie pokazują już na te prawidłowe obiekty.
W takim przypadku trzeba zrezygnować z vectora i trzeba użyć czegoś jak lista, w której nie ma przesunięć obiektów. Ale znowu lista z definicji nie mówi nic o miejscu w którym alokowane są obiekty i tak - jeśli zrobimy sobie listę w której, alokujemy kolejne elementy operatorem new, może się zdarzyć, że te elementy będą fizycznie znajdować się daleko od siebie, a to powoduje zwiększenie wymiany pamięci cache, więc znacznie zwalnia wykonanie programu (w grach ma to spore znaczenie).
Oczywiście w jakimś tam testowym programie gdzie wykonamy kilka new'ów obok siebie w praktyce new najpewniej zwróci fragmenty sterty obok siebie, ale załóżmy, że jednak nasz program działa trochę dłużej, obiekty dodajemy w różnych etapach czasowych działania naszego programu, a w między czasie new wywoływany jest jest wielokrotnie do innych celów (dane na stercie są wymieszane), wtedy faktycznie nasza lista najpewniej będzie zawierała obiekty przydzielone na zupełnie innych fragmentach sterty - co jest niepożądane wydajnościowo.
W takim wypadku właśnie trzeba zrobić sobie taką listę, ale działającą jako tablica. Czyli implementujesz faktycznie listą, w której zapamiętujesz adresy kolejnych obiektów, ale wszystkie te obiekty fizycznie alokujesz na tablicy/wektorze/liniowej przestrzeni pamięci.
Czyli technicznie rzecz biorąc robisz tablicę, w której mogą występować puste miejsca (w sensie że logicznie nie istnieje tam obiekt, bo pamięć wiadomo istnieje/jest przydzielona :>), oraz kolejność logiczna elementów nie jest zgodna z kolejnością w tablicy, np. element pierwszy może zawierać adres, który mówi, że następny element jest tym piątym w tablicy :> a następny tym trzecim, a na indeksach drugim i czwartym nie ma "zaalokowanych/utworzonych" obiektów.
Uproszczony schemat:
struct ListItem {
OBIEKT object; // zaalokowane dane obiektu
LitsItem* next; // tylko jedno kierunkowa..
ListItem* prev; // ...albo i dwu :>
};
ListItem list[5]; // wektor/tablica 5 elementów
list[0].next = &list[4]; // pierwszy mówi, że następnym jest ten piąty
list[4].next = &list[2]; // piąty w tablicy, a loigicznie(według listy) drugi, mówi, że trzecim w liście(logicznie), jest ten trzeci w tablicy
list[2].next = NULL; // a ten trzeci jest już ostatnim, więc logicznie na indeksie 1(drugim w tablicy), oraz 3(czwartym binarnie) nie istnieją obiekty, oczywiście logicznie w liście
Jak dla mnie lista na tablicy traci sens głównie dlatego że z góry trzeba wiedzieć ile pamięci trzeba zarezerwować
Jeśli chodzi o pamięć to lista tablicowa nieefektywnie ją wykorzystuje bo jak już wspomniał trzynasty smok
na liście tablicowej kolejna komórka tablicy nie musi być kolejnym elementem listy więc też przydałaby się jakaś zmienna np całkowitoliczbowa
która symulowałaby działanie wskaźnika
Wobec powyższego ja też zastanawiam się nad sensem listy tablicowej