Chciałem wiedzieć, czy to było możliwe (Powinien być tak, jak robi to program std :: list) do wykonania operacji PopBack () na pojedynczo połączonej liście w stałym czasie i jak?
Zakładam, że przechowujemy głowę i ogonwskaźniki. W takim przypadku PushBack (), PushFront (), PopFront () mogą być łatwo zaimplementowane w stałym czasie. Ale nie można myśleć o sposobie implementacji PopBack () o tym samym czasie działania.
Odpowiedzi:
4 dla odpowiedzi № 1Nie możesz wdrożyć pop_back dla pojedynczej połączonej listy w stałym czasie. Aby to zrobić, musisz znać poprzedni element przed ostatnim, który jest ostatnim elementem, zawiera odniesienie do poprzedniego elementu. Jeśli tak, to będziesz miał podwójnie połączoną listę.
Możesz uzupełnić push_back w stałym czasie. Jedną z moich propozycji dla C ++ Standard było wprowadzenie std::x_forward_list to będzie wspierać push_back funkcja członka. W takim przypadku będziesz mógł użyć takiej pojedynczej połączonej listy do symulacji kolejki.