Kiedy lista podwójnie połączona jest bardziej wydajna niż lista pojedynczo połączona?
W dzisiejszym wywiadzie zadano mi pytanie.
Oprócz odpowiedzi odwracającej listę i zarówno do przodu, jak i do tyłu, było w niej coś "fundamentalnego", co rozmówca podkreślał. Poddałem się i oczywiście po wywiadzie zrobiłem trochę badań. Wydaje się, że wstawianie i usuwanie są bardziej efektywne w liście podwójnie połączonej niż w liście pojedynczo połączonej. Nie jestem do końca pewien, jak to może być bardziej wydajne dla podwójnie połączonej listy, ponieważ jest oczywiste, że więcej referencje są wymagane do zmiany. Czy ktoś może wyjaśnić ukryty sekret? Szczerze mówiąc zrobiłem sporo badań i nie zrozumiałem, ponieważ moim głównym problemem jest fakt, że wyszukiwanie O(n) jest nadal potrzebne dla podwójnie połączonej listy.
5 answers
Wstawianie jest wyraźnie mniej pracy w pojedynczo-linkowane listy, tak długo, jak jesteś zadowolony, aby zawsze wstawić na czele lub po jakimś znanym elemencie. (Oznacza to, że nie można wstawić przed znanym elementem, ale patrz poniżej.)
Usuwanie, z drugiej strony, jest trudniejsze, ponieważ musisz znać element przed elementem do usunięcia.
Jednym ze sposobów jest to, aby API delete działało z poprzednikiem elementu do usunięcia. To odzwierciedla API insert, które zajmuje element, który będzie poprzednikiem nowego elementu, ale nie jest zbyt wygodny i trudno go udokumentować. Zazwyczaj jest to możliwe. Ogólnie rzecz biorąc, docierasz do elementu na liście, przemierzając listę.
Oczywiście możesz po prostu przeszukać Listę od początku, aby znaleźć element do usunięcia, aby wiedzieć, jaki był jego poprzednik. To zakłada, że API delete zawiera nagłówek listy, co jest również niewygodne. Ponadto poszukiwania są głupie powoli.
Sposobem, którego prawie nikt nie używa, ale który jest całkiem skuteczny, jest zdefiniowanie iteratora listy pojedynczo połączonego jako wskaźnika do elementu poprzedzającego bieżący cel iteratora. Jest to proste, tylko jedna indirection wolniejsza niż użycie wskaźnika bezpośrednio do elementu i sprawia, że wstawianie i usuwanie jest szybkie. Minusem jest to, że usunięcie elementu może unieważnić inne Iteratory listy elementów, co jest denerwujące. (Nie unieważnia iteratora do element jest usuwany, co jest dobre dla trawersów, które usuwają niektóre elementy, ale to nie jest duża rekompensata.)
Jeśli usunięcie nie jest ważne, być może dlatego, że struktury danych są niezmienne, pojedynczo połączone listy oferują inną naprawdę użyteczną właściwość: umożliwiają współdzielenie struktur. Lista z pojedynczym linkiem może być na szczęście ogonem wielu głów, co jest niemożliwe dla listy z podwójnym linkiem. Z tego powodu listy pojedynczo połączone tradycyjnie były prostym struktura danych z wyboru dla języków funkcyjnych.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-03-22 05:57:19
Oto jakiś kod, który sprawił, że stało się to dla mnie jaśniejsze... Posiadające:
class Node{
Node next;
Node prev;
}
Usuń węzeł z pojedynczej listy połączonej - O (n) -
Nie wiesz, który jest węzłem poprzedzającym, więc musisz przemierzyć listę, dopóki jej nie znajdziesz:
deleteNode(Node node){
prevNode = tmpNode;
tmpNode = prevNode.next;
while (tmpNode != null) {
if (tmpNode == node) {
prevNode.next = tmpNode.next;
}
prevNode = tmpNode;
tmpNode = prevNode.next;
}
}
Usuwa węzeł z podwójnie połączonej listy - O (1) -
Możesz po prostu zaktualizować linki w następujący sposób:
deleteNode(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-31 06:20:45
Oto moje przemyślenia na temat listy podwójnych linków:
Masz gotowy dostęp\insert na obu końcach.
Może działać jednocześnie jako Kolejka i stos.
Usunięcie węzła nie wymaga dodatkowych wskaźników.
Możesz zastosować Trawers wspinaczkowy, ponieważ masz już dostęp na obu końcach.
Jeśli przechowujesz wartości liczbowe, a Twoja lista jest posortowana, możesz zachować wskaźnik / zmienną dla mediany, a następnie wyszukać operacja może być wysoce optymalna przy użyciu podejścia Statystycznego.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-03-22 05:57:39
Jeśli chcesz usunąć element z połączonej listy, musisz połączyć poprzedni element z następnym elementem. Dzięki podwójnie połączonej liście masz gotowy dostęp do obu elementów, ponieważ masz linki do obu.
Zakłada to, że masz już wskaźnik do elementu, który chcesz usunąć i nie ma potrzeby przeszukiwania.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-03-22 05:04:24
'oprócz odpowiedzi na odwrócenie listy i zarówno do przodu, jak i do tyłu było coś "fundamentalnego"'.
Wygląda na to, że nikt nie wspomniał: na podwójnie połączonej liście możliwe jest ponowne wstawianie usuniętego elementu tylko za pomocą wskaźnika do usuniętego elementu. Zobacz Referat Dancing Links Knutha. Myślę, że to dość fundamentalne.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-04-21 15:40:59