Microsoft pyta: Lista pojedyncza lub podwójna? Jakie są plusy i minusy używania każdego z nich?

Question

Pytam o to pytanie i mam własne zdanie, ale nie jestem do końca pewien, co powiedzieć na temat wad i zalet? Microsoft zadał to pytanie jednemu ze swoich kandydatów.

Pojedynczo połączona lista umożliwia przejście w jedną stronę. Natomiast lista podwójnie związana ma kierunek dwukierunkowy następny i poprzedni.

Oto dobre zdjęcie, które rysuje pojedynczo i podwójnie połączone listy.

Jednak, jak można wyjaśnić zalety i wady tych elementów w bardziej uporządkowany sposób?

Answer 1

Pytam o to pytanie i mam własne zdanie, ale nie jestem do końca pewien, co powiedzieć na temat wad i zalet?

Wszystko sprowadza się do użycia. Tutaj jest kompromis.

Pojedynczo połączona lista jest prostsza pod względem implementacji i zazwyczaj ma mniejsze wymagania dotyczące pamięci, ponieważ musi tylko utrzymywać odniesienia do przodu użytkownika w miejscu.

Lista podwójnie połączona ma bardziej wydajną iterację, szczególnie jeśli trzeba ją powtarzać w odwrotnej kolejności (co jest strasznie nieefektywne z jedną połączoną listą) i bardziej wydajne usuwanie określonych węzłów.

W związku z tym - skoro masz tę oznaczoną .NET, podwójnie połączone listy mają tę zaletę, że są bezpośrednio w strukturze w postaci klasy LinkedList<T>. Zapewnia to ogromną zaletę, ponieważ nie trzeba implementować, testować i utrzymywać własnej klasy kolekcji.

Answer 2

Advantage podwójnej listy połączonej: Może przechodzić w obu kierunkach

Zaletą jednej listy połączonej: Mniej pracy w domu do zrobienia na aktualizacji/insert/delete, mniejszym zużyciu pamięci.

Answer 3

Cóż, to zależy od sytuacji. Jeśli chcesz szybko uzyskać zarówno poprzedni, jak i następny element z danego elementu, najlepiej jest wybrać listę podwójnie powiązaną.

Jeśli potrzebujesz tylko następnego elementu z danego elementu, pojedynczo połączona lista jest wystarczająco dobra.

Answer 4

Podczas gdy pojedynczo połączona lista zużywa mniej pamięci na węzeł (jeden wskaźnik w porównaniu do dwóch wskaźników), jego operacja usuwania to O(N), jeśli wszystko, co masz, jest wskaźnikiem do węzła, który chcesz usunąć, a podwójnie połączone usuwanie to O(1). Istnieje mało znana sztuczka, która pozwala usunąć z pojedynczo połączonej listy w O(1), ale lista musi być okrągła, aby działała (przenieś zawartość next do bieżącego i usuń next).

Podwójnie połączone listy mogą być używane w miejscach, w których pojedynczo połączone listy nie działałyby (kolejka podwójnie zakończona), ale wymagają nieco więcej "sprzątania" i są nieco mniej wydajne przy wstawianiu w wyniku.

Answer 5

Chociaż ta kwestia została już odpowiedział, nie jestem jakoś zadowolony z odpowiedzi (bez obrazy oznaczało), więc oto jak chciałbym odpowiedzieć:

Czego używać - pojedynczo lub podwójnie związany lista zależy co zamierzasz osiągnąć i ograniczeń systemu, jeśli takie istnieją.

Pojedynczo-linked lista:

Plusy: prosty w realizacji, wymaga stosunkowo mniejszą pamięć do przechowywania, zakładając, że trzeba usunąć/insert (at) następny węzeł - usunięcie/wstawiania jest szybciej.

Wady: Nie można wykonać iteracji wstecznej, należy zachować uchwyt do węzła głównego listy, lista zostanie utracona w pamięci. Jeśli usuwasz poprzedni węzeł lub wstawiasz w poprzednim węźle, będziesz musiał przejść przez listę od głowy do poprzedniego węzła, aby móc wykonać te operacje - czas O (N).

- To powinno być używane, gdy masz mniejszą pamięć, a twoim głównym celem jest wstawianie/usuwanie i nie szukanie elementów.

podwójnie połączonej listy:

Plusy: można powtórzyć w przód jak i tył. W przypadku konieczności usunięcia poprzedniego węzła, nie ma potrzeby przechodzenia z węzła głównego, ponieważ węzeł, który ma zostać usunięty, można znaleźć na podstawie wskaźnika ".previous".

Wady: Stosunkowo skomplikowane do wdrożenia, wymaga więcej pamięci do przechowywania (1 "poprzedni" wskaźnik na węzeł). Insercji i delecji są stosunkowo bardziej czasochłonne (przypisywanie/realokacja”.previous' wskaźnik dla węzłów sąsiednich)

--This powinny być stosowane, gdy nie masz lub minimalne ograniczenia dotyczące pamięci, a głównym celem jest, aby szukać elementów .

Jeśli jest więcej plusów i minusów, prosimy dodać, odpowiedzieć w komentarzach. Dzięki!