Zad 5. Skonstruuj listę dwukierunkową dla następującego zestawu kluczy {5, 24, 7, 16} za pomocą tablic, przy założeniu, że język programowania nie dysponuje wskaźnikami. Pokaż wersję dla wielu oraz pojedynczej tablicy. Jakie są złożoności obliczeniowe dodawania i eliminowania elementu z tablicy?
Rozwiązanie:
W przypadku listy dwukierunkowej, dodawanie i usuwanie elementu ma złożoność O(1), jeśli znamy wskaźnik do miejsca, w którym chcemy dodać lub usunąć element. Jeśli jednak musimy najpierw znaleźć to miejsce, złożoność wynosi O(n).
Tablica dwukierunkowa:
1.Z wieloma tablicami wersja:
keys = [5, 24, 7, 16]
next = [1, 2, 3, None]
prev = [None, 0, 1, 2]
2.Z pojedyńczą tablicą wersja:
pierwotna tablica = [5, None, None]
po dodaniu elementu 24 = [5, 24, None]
po dodaniu elementu 7 = [5, 24, 7]
po dodaniu elementu 16 = [5, 24, 7, 16]