Struktura danych listy połączonej w Javie

Różne struktury danych są tworzone w różnych celach. Być może znasz ArrayList (jeśli nadal nie, zalecamy najpierw o tym przeczytać). W tym artykule dowiemy się o LinkedList i zrozumiemy, do czego służy ta kolekcja. Jeśli spojrzysz na LinkedList Java 8 (lub nowszą wersję języka) kod źródłowy klasy (na stronie Oracle lub w swoim IDE, w przypadku IDEA: crtl + B na nazwie klasy) zobaczysz następną deklarację:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

W tej chwili najważniejszą informacją z kodu jest fakt, że LinkedList implementuje interfejsy List i Deque . Interfejs List zachowuje kolejność dodawania elementów i umożliwia dostęp do elementu według indeksu. „Zwykła” kolejka obsługuje dodawanie elementów na końcu i wyodrębnianie ich od początku. Deque jest kolejką dwukierunkową i obsługuje dodawanie i usuwanie elementów z obu stron. Możesz myśleć o tym jako o połączeniu stosu i kolejki. Tak więc LinkedList jest implementacją tych dwóch i pozwala nam stworzyć dwukierunkową kolejkę składającą się z dowolnych obiektów, w tym zerowych. Połączona listajest zbiorem elementów. Widzimy to w źródle kodu klasy, tym razem zwróć uwagę na pola:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Każdy element, zwykle nazywaliśmy go Node , zawiera obiekt i odniesienia do dwóch sąsiednich obiektów — poprzedniego i następnego. Dlatego nie jest zbyt efektywny pod względem wykorzystania pamięci. Ponieważ LinkedList jest w rzeczywistości strukturą dwukierunkową, możemy łatwo dodawać lub usuwać elementy z obu stron.

Konstruktory LinkedList

Wracając do źródła kodu, możemy dowiedzieć się, że LinkedList ma dwa konstruktory

• LinkedList() bez parametrów służy do konstruowania pustej listy.
• >LinkedList(Collection<? extends E> c) służy do tworzenia listy zawierającej elementy określonej kolekcji, w kolejności, w jakiej są zwracane przez iterator kolekcji.

Deklaracja LinkedList

W rzeczywistości połączona lista (Java lub w dowolnym innym języku) składa się z sekwencji węzłów. Każdy węzeł jest przeznaczony do przechowywania obiektu typu zdefiniowanego podczas tworzenia. Aby utworzyć LinkedList , kod Java jest następny:

LinkedList<Integer> myList = new LinkedList<>();

Mamy obiekt do przechowywania sekwencji liczb całkowitych i linków do sąsiadów. W tej chwili jest on jednak pusty.

Główne operacje LinkedList

Jak zwykle w przypadku Collections możesz umieścić elementy w LinkedList (na końcu lub w środku), usunąć stamtąd i pobrać element po indeksie. Oto one:

• add(E element) Dołącza określony element na końcu tej listy;
• add(int index, E element) Wstawia element w podanej pozycji index ;
• get(int index) Zwraca element na podanej pozycji na tej liście;
• remove(int index) Usuwa element znajdujący się na pozycji index;
• remove(Object o) Usuwa pierwsze wystąpienie ? o element z tej listy, jeśli tam jest.
• remove() Pobiera i usuwa pierwszy element listy.

Implementacja list połączonych w Javie, dodawanie i usuwanie elementów. Przykład

Wypróbujmy te operacje w praktyce. Najpierw implementacja Java LinkedList: utworzenie LinkedList of Strings, dodanie tam 3 elementów. Następnie usuń jeden, a następnie dodaj jeden na środku.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Wynik działania tego programu:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList jest częścią frameworka Collection , możesz użyć Iteratora do usuwania elementów, a także specjalnego iteratora do list — ListIterator . Co więcej, operacje z iteratorem zapewniają główne korzyści klasy LinkedList : dobrą wydajność operacji wstawiania/usuwania. Używając Iteratora możesz uzyskać dla nich stały czas. W dalszej części tego artykułu napiszemy przykładowy kod do porównania ArrayList i LinkedList+Iterator

• Iterator.remove() usuwa ostatni element zwrócony przez ten iterator.
• ListIterator.add(element E) wstawia element do listy

Java LinkedList Przykład: jak działa Iterator

Tutaj mamy mały przykładowy kod Java LinkedList , w którym próbujemy dodawać i usuwać za pomocą Iteratora.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);

       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);

   }
}

Wynik działania tego programu:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Więcej operacji Java LinkedList :

• addFirst() , addLast() dodają element na początek/koniec listy
• clear() usuwa wszystkie elementy z listy
• zawiera(Obiekt o) zwraca wartość true, jeśli lista zawiera element o.
• indexOf(Object o) zwraca indeks pierwszego wystąpienia elementu o lub -1, jeśli nie ma go na liście.
• set(int index, element E) zastępuje element na pozycji indeksu elementem
• size()Zwraca liczbę elementów na liście.
• toArray() zwraca tablicę zawierającą wszystkie elementy listy od pierwszego do ostatniego elementu.

BTW będąc kolejką o dwóch rozmiarach, LinkedList w Javie ma operacje specyficzne dla stosu:

• pop() , która zdejmuje element ze stosu (reprezentowany przez listę)
• push(E e) wrzuca element na stos (reprezentowany przez tę listę)

Jak odwrócić LinkedList: przykład

Oto mały przykład, popularne, ale łatwe zadanie dla początkujących. Mamy LinkedList i powinniśmy to odwrócić. Najprostszym algorytmem jest przejście przez LinkedList w odwrotnej kolejności i umieszczenie każdego elementu w nowym. Może jednak znajdziesz lepszy sposób? Oto kod programu java z listą wstecznie połączoną:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

Wynik:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: kiedy użyć pierwszego

Zarówno LinkedList, jak i ArrayList są implementacjami interfejsu List . LinkedList implementuje to z podwójnie połączoną listą. ArrayList implementuje to przy użyciu dynamicznie zmieniającej się tablicy. Jak już wiesz, każdy węzeł LinkedList zawiera obiekty i dwa odniesienia do sąsiadów. Oznacza to dodatkowe koszty pamięci do przechowywania odniesień między elementami w przypadku Java LinkedList . ArrayList implementuje to za pomocą dynamicznie zmieniającej się tablicy. Niektóre operacje LinkedList i ArrayList wyglądają tak samo, ale działają w inny sposób. W tablicy ArrayListprzypadku manipulujesz wewnętrznymi tablicami, w LinkedList — referencjami. ArrayList to najpopularniejsza implementacja listy . Zdecydowanie powinieneś używać ArrayList , gdy dostęp do indeksu jest priorytetem, ponieważ operacje te są wykonywane w stałym czasie. Dodawanie na koniec listy średnio również odbywa się w stałym czasie. Co więcej, ArrayList nie wiąże się z dodatkowymi kosztami przechowywania wielu elementów. Jako minusy można zaliczyć szybkość operacji wstawiania i usuwania, gdy nie jest ona wykonywana na końcu listy. Połączona listajest bardziej przydatny w przypadku wykonywania operacji wstawiania i usuwania w pewien sposób: jeśli używasz iteratorów, dzieje się to w stałym czasie. Operacje dostępu według indeksu są wykonywane przez wyszukiwanie od początku końca (w zależności od tego, co jest bliższe) do żądanego elementu. Nie zapomnij jednak o dodatkowych kosztach przechowywania referencji pomiędzy elementami. Więc tutaj standardowe operacje LinkedList i ArrayList z algorytmicznymi środowiskami wykonawczymi. N odnosi się do liczby pozycji, które już znajdują się na liście. O(N) oznacza, że ​​w najgorszym przypadku powinniśmy „przejść” całą listę aż do znalezienia potrzebnej pozycji, np. do wstawienia nowego elementu do listy. O(1)oznacza, że ​​operacja odbywa się w stałym czasie, niezależnie od liczby elementów.

Złożoność czasowa LinkedList

Złożoność czasowa ArrayList

Kiedy używać LinkedList: Przykład

Zdecydowanie ArrayList jest najpopularniejszą implementacją List . Możesz jednak spotkać się z sytuacjami, w których operacje dodawania/usuwania będą potrzebne zbyt często. W takim przypadku LinkedList razem z Iteratorem może być korzystne. Oto przykład. Mamy długą listę i powinniśmy usunąć z niej każdy element. Zróbmy to zadanie za pomocą ArrayList i LinkedList + Iterator . Porównujemy czas każdej operacji i drukujemy go w konsoli. Tutaj kod:

import java.util.*;
import java.util.function.BiPredicate;

public class ListTest2 {

   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());

       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }

   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);

           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }

   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }

   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Wynik dla listy tablic:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Wynik dla LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Jak widać w tym przypadku LinkedList jest o wiele bardziej efektywny. Bądźmy szczerzy. W prawdziwym tworzeniu oprogramowania użycie LinkedList jest rodzajem rzadkiego zdarzenia. Niemniej jednak profesjonalista powinien wiedzieć o istnieniu tej struktury danych i jej zaletach. O ile w prawdziwym kodzie LinkedList jest rzadkim gościem, o tyle na wywiadach Java Junior jest bardzo popularny. A jednak oto, co Joshua Bloch napisał o LinkedList :

AddOn: pojedynczo połączona lista Java

Wśród klasycznej kolekcji w Javie nie ma listy pojedynczo połączonej , pojedynczo połączona lista to struktura, w której każdy węzeł zawiera obiekt i odniesienie do następnego węzła, ale nie do poprzedniego. Java LinkedList jest podwójnie połączona, ale nikt nie przeszkadza ci w tworzeniu własnej struktury danych, takiej jak Single ,code>Linked List. Oto kilka kroków, aby rozwiązać te zadania:

1. Utwórz klasę Node z dwoma atrybutami, data i next. Następny jest odniesieniem do następnego węzła.
2. Utwórz klasę FirstLast z dwoma atrybutami, głową i ogonem.
3. Utwórz metodę add() , aby dodać nowy węzeł do listy. Najpierw sprawdź, czy lista jest pusta ( head == null ). Jeśli tak, głowa i ogon odnoszą się do nowego węzła. Jeśli lista nie jest pusta, nowy węzeł zostanie dodany na końcu, więc następny atrybut ogona odnosi się do dodanego węzła, a nowy węzeł staje się ogonem listy.

Nawiasem mówiąc, możesz również spróbować stworzyć własną LinkedList jako ćwiczenie. Powodzenia w nauce.