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;
}
}
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) {
// 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);
}
}
}
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:
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.
Lead Software Architect w Tribunal de Justiça da Paraíba
Jesse a passionate Software Engineer for discovering solutions that help people to get better lives. He has been working with tech ...
[Przeczytaj pełną biografię]
GO TO FULL VERSION