Struktury danych i algorytmy w Javie, Część 5: Listy podwójnie połączone

Listy z pojedynczym łączem mają wiele zastosowań, ale wiążą się z pewnymi ograniczeniami. Po pierwsze, listy połączone pojedynczo ograniczają przechodzenie przez węzły w jednym kierunku: nie możesz przechodzić wstecz po liście pojedynczo połączonej, chyba że najpierw odwrócisz jej łącza węzłów, co zajmuje trochę czasu. Jeśli wykonujesz odwrotne przemierzanie i chcesz przywrócić przechodzenie węzłów do pierwotnego kierunku, będziesz musiał powtórzyć odwrócenie, co zajmie więcej czasu. Listy połączone pojedynczo również ograniczają usuwanie węzłów. Na liście tego typu nie można usunąć dowolnego węzła bez dostępu do poprzednika węzła.

Na szczęście Java oferuje kilka typów list, których można używać do wyszukiwania i sortowania danych przechowywanych w programach Java. Ten ostatni samouczek z serii Struktury danych i algorytmy przedstawia wyszukiwanie i sortowanie za pomocą list podwójnie połączonych i list połączonych cyklicznie. Jak zobaczysz, te dwie kategorie struktury danych opierają się na listach połączonych pojedynczo, oferując szerszy zakres wyszukiwania i sortowania w programach Java.

Listy podwójnie połączone

Lista podwójnie połączona to połączona lista węzłów, w której każdy węzeł ma parę pól połączeń. Jedno pole łącza umożliwia przechodzenie po liście w kierunku do przodu, podczas gdy drugi węzeł umożliwia przechodzenie po liście w kierunku wstecz. W kierunku do przodu zmienna odniesienia zawiera odniesienie do pierwszego węzła. Każdy węzeł łączy się z następnym węzłem za pośrednictwem pola łącza „next”, z wyjątkiem ostatniego węzła, którego pole łącza „next” zawiera odniesienie zerowe oznaczające koniec listy (w kierunku do przodu). Kierunek do tyłu działa podobnie. Zmienna odniesienia zawiera odniesienie do ostatniego węzła w kierunku do przodu, który należy interpretować jako pierwszy węzeł. Każdy węzeł łączy się z poprzednim węzłem za pośrednictwem pola łącza „previous”. „Poprzedni” pierwszy węzełpole łącza zawiera wartość null, która oznacza koniec listy.

Spróbuj pomyśleć o podwójnie połączonej liście jako o parze list połączonych pojedynczo, z których każda łączy te same węzły. Diagram na rysunku 1 przedstawia topForwardlisty z odniesieniami i topBackwardpojedynczymi połączeniami.

Operacje CRUD na podwójnie połączonych listach

Tworzenie, wstawianie i usuwanie węzłów to typowe operacje na podwójnie połączonej liście. Są podobne do operacji, których nauczyłeś się dla list połączonych pojedynczo. (Pamiętaj, że lista podwójnie połączona to po prostu para list połączonych pojedynczo, które łączą te same węzły.) Poniższy pseudokod demonstruje tworzenie i wstawianie węzłów do listy podwójnie połączonej pokazanej na rysunku 1. Pseudokod demonstruje również węzeł usunięcie:

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward.name = "C" // Create forward singly-linked list topForward.next = temp temp.next = topBackward topBackward.next = NULL // Create backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Delete Node B. temp.prev.next = temp.next; // Bypass Node B in the forward singly-linked list. temp.next.prev = temp.prev; // Bypass Node B in the backward singly-linked list. END 

Przykład zastosowania: CRUD na liście podwójnie połączonej

Przykładowa aplikacja Java DLLDemopokazuje, jak tworzyć, wstawiać i usuwać węzły na podwójnie połączonej liście. Kod źródłowy aplikacji jest pokazany na Listingu 1.

Listing 1. Aplikacja Java prezentująca CRUD na podwójnie połączonej liście

 public final class DLLDemo { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Reference node B. temp = topForward.next; // Delete node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump forward singly-linked list. System.out.print("Forward singly-linked list (after deletion): "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list (after deletion): "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } } 

Skompiluj Listing 4 w następujący sposób:

 javac DLLDemo.java 

Uruchom wynikową aplikację w następujący sposób:

 java DLLDemo 

Należy zwrócić uwagę na następujące dane wyjściowe:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA 

Tasowanie w podwójnie połączonych listach

Java Collections Framework zawiera Collectionsklasę metod narzędziowych, która jest częścią java.utilpakietu. Ta klasa zawiera void shuffle(List list)metodę, która „ losowo permutuje określoną listę przy użyciu domyślnego źródła losowości ”. Na przykład możesz użyć tej metody, aby przetasować talię kart wyrażoną jako lista podwójnie połączona ( java.util.LinkedListklasa jest przykładem). W poniższym pseudokodzie możesz zobaczyć, jak algorytm Shuffle może tasować listę podwójnie połączoną:

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap(topForward, i - 1, rnd.nextInt(i)) END FOR FUNCTION swap(Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Locate ith node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Locate jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Perform the swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END 

Algorytm Shuffle uzyskuje źródło losowości, a następnie przechodzi przez listę wstecz, od ostatniego węzła do drugiego. Wielokrotnie zamienia losowo wybrany węzeł (który w rzeczywistości jest tylko polem nazwy) na „bieżącą pozycję”. Węzły są wybierane losowo z części listy, która biegnie od pierwszego węzła do aktualnej pozycji włącznie. Zauważ, że ten algorytm jest z grubsza zaczerpnięty z void shuffle(List list)kodu źródłowego.

Pseudokod algorytmu Shuffle jest leniwy, ponieważ skupia się tylko na liście pojedynczo połączonej z ruchem do przodu. To rozsądna decyzja projektowa, ale płacimy za to cenę w złożoności czasowej. Złożoność czasowa wynosi O ( n 2). Najpierw mamy pętlę O ( n ), która wywołuje swap(). Po drugie, wewnątrz swap()mamy dwie sekwencyjne pętle O ( n ). Przypomnij sobie następującą zasadę z części 1:

 If f1(n) = O(g(n)) and f2(n) = O(h(n)) then (a) f1(n)+f2(n) = max(O(g(n)), O(h(n))) (b) f1(n)*f2(n) = O(g(n)*h(n)). 

Część (a) dotyczy algorytmów sekwencyjnych. Tutaj mamy dwie pętle O ( n ). Zgodnie z regułą wynikowa złożoność czasowa wynosiłaby O ( n ). Część (b) dotyczy zagnieżdżonych algorytmów. W tym przypadku mamy O ( n ) pomnożone przez O ( n ), co daje O ( n 2).

Zwróć uwagę, że złożoność przestrzeni Shuffle to O (1), wynikająca z zadeklarowanych zmiennych pomocniczych.

Przykład zastosowania: tasowanie na liście z podwójnymi linkami

ShuffleAplikacja na listingu 2 jest wykazanie algorytmu shuffle.

Listing 2. Algorytm Shuffle w Javie

 import java.util.Random; public final class Shuffle { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Shuffle list. Random rnd = new Random(); for (int i = 3; i > 1; i--) swap(topForward, i - 1, rnd.nextInt(i)); // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } public static void swap(Node top, int i, int j) { // Locate ith node. Node nodei = top; for (int k = 0; k < i; k++) nodei = nodei.next; // Locate jth node. Node nodej = top; for (int k = 0; k < j; k++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; } } 

Skompiluj Listing 5 w następujący sposób:

 javac Shuffle.java 

Uruchom wynikową aplikację w następujący sposób:

 java Shuffle 

Powinieneś obserwować następujące dane wyjściowe z jednego przebiegu:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list: BAC Backward singly-linked list: CAB 

Listy połączone cyklicznie

Pole łącza w ostatnim węźle listy połączonej pojedynczo zawiera łącze puste. Dotyczy to również listy podwójnie połączonej, która zawiera pola łączy w ostatnich węzłach list połączonych pojedynczo do przodu i do tyłu. Załóżmy zamiast tego, że ostatnie węzły zawierały łącza do pierwszych węzłów. W takiej sytuacji otrzymasz listę z linkami cyklicznymi , która jest pokazana na rysunku 2.

Listy połączone cyklicznie , nazywane także buforami cyklicznymi lub kolejkami cyklicznymi , mają wiele zastosowań. Na przykład są używane przez programy obsługi przerwań systemu operacyjnego do buforowania naciśnięć klawiszy. Aplikacje multimedialne używają list połączonych cyklicznie do buforowania danych (na przykład buforowania danych zapisywanych na karcie dźwiękowej). Technika ta jest również wykorzystywana przez rodzinę algorytmów bezstratnej kompresji danych LZ77.

Połączone listy a tablice

W całej tej serii dotyczącej struktur danych i algorytmów rozważaliśmy mocne i słabe strony różnych struktur danych. Ponieważ skupiliśmy się na tablicach i połączonych listach, możesz mieć pytania dotyczące tych typów. Jakie zalety i wady oferują połączone listy i tablice? Kiedy używasz listy połączonej, a kiedy tablicy? Czy struktury danych z obu kategorii można zintegrować w użyteczną hybrydową strukturę danych? Spróbuję odpowiedzieć na poniższe pytania poniżej.

Listy połączone mają następujące zalety w porównaniu z tablicami:

  • Nie wymagają dodatkowej pamięci do obsługi rozszerzeń. Z kolei tablice wymagają dodatkowej pamięci, gdy konieczne jest rozszerzenie. (Gdy wszystkie elementy zawierają elementy danych, żadne nowe elementy danych nie mogą być dołączane do tablicy).
  • Oferują szybsze wstawianie / usuwanie węzłów niż równoważne operacje oparte na tablicach. Jedynie linki wymagają aktualizacji po zidentyfikowaniu pozycji wstawiania / usuwania. Z perspektywy tablicy wstawianie elementów danych wymaga przesunięcia wszystkich innych elementów danych w celu utworzenia pustego elementu. Podobnie, usunięcie istniejącego elementu danych wymaga przeniesienia wszystkich innych elementów danych w celu usunięcia pustego elementu. Wszelkie ruchy elementów danych wymagają czasu.

Z kolei tablice mają następujące zalety w porównaniu z listami połączonymi:

  • Elementy tablicy zajmują mniej pamięci niż węzły, ponieważ elementy nie wymagają pól łączących.
  • Tablice zapewniają szybszy dostęp do elementów danych dzięki indeksom opartym na liczbach całkowitych.