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.
![Struktura danych LinkedList Java — 2]()
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;
transient Node<E> first;
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.
![Struktura danych LinkedList Java — 3]()
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<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
Operacja Java LinkedList |
Efektywność algorytmiczna |
get(indeks int) |
O(n) , średnio — n/4 kroków, gdzie n to rozmiar LinkedList |
dodaj(element E) |
O(1) |
dodaj(indeks int, element E) |
O(n) , średnio — n/4 kroków; jeśli index = 0 to O(1) , więc jeśli chcesz dodać coś na początku listy, LinkedList<E> może być dobrym wyborem |
usuń (indeks int) |
O(n) , średnio — n/4 kroków |
Iterator.usuń() |
O(1) To jest główny powód używania LinkedList<E> |
Złożoność czasowa ArrayList
Operacja LinkedList |
Efektywność algorytmiczna |
get(indeks int) |
O(1) , jeden z głównych powodów używania ArrayList<E> |
dodaj(element E) |
O(n) to najgorszy przypadek, ponieważ tablicę należy zmienić i skopiować, jednak w praktyce nie jest tak źle |
dodaj(indeks int, element E) |
O(n) , średnio n/2 kroków |
usuń (indeks int) |
O(n) , średnio n/2 kroków |
Iterator.usuń() |
O(n) , średnio n/2 kroków |
ListIterator.add(element E) |
O(n) , średnio n/2 kroków |
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) {
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));
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));
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();
System.out.println("testedList.size after removeElements(..): " + testedList.size());
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();
System.out.println("testedList.size after removeElements(..): " + testedList.size());
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 :
![Struktura danych LinkedList Java — 4]()
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:
- Utwórz klasę Node z dwoma atrybutami, data i next. Następny jest odniesieniem do następnego węzła.
- Utwórz klasę FirstLast z dwoma atrybutami, głową i ogonem.
- 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.
GO TO FULL VERSION