Ulike datastrukturer lages for ulike formål. Du kjenner kanskje til
ArrayList (hvis fortsatt ikke, anbefaler vi deg å lese om det først). I denne artikkelen skal vi lære om
LinkedList og innse hva denne samlingen er god for. Hvis du ser på LinkedList Java 8 (eller nyere versjon av språket) klassekodekilde (på Oracle-nettstedet eller i IDE-en din, i tilfelle IDEA: crtl+B på klassenavnet) vil du se neste erklæring:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
For øyeblikket er den viktigste informasjonen fra koden det faktum at
LinkedList implementerer
List og
Deque -grensesnitt. Liste-grensesnittet beholder sekvensen for å legge til elementer og gir tilgang til elementet etter indeks. Den "vanlige"
køen støtter å legge til elementer til slutten og trekke dem ut fra begynnelsen. Deque er en toveiskø, og den støtter å legge til og fjerne elementer fra begge sider. Du kan tenke på det som en kombinasjon av stabel og kø.
![LinkedList Java-datastruktur - 2]()
Så, LinkedList er en implementering av disse to, og den lar oss lage en toveis kø bestående av alle objekter inkludert null.
LinkedLister en samling av elementer. Vi kan se det i kodekilden til klassen, denne gangen ta hensyn til feltene:
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
Hvert element, vanligvis kalte vi det
Node , inneholder et objekt og referanser til to naboobjekter - det forrige og det neste. Derfor er det ikke veldig effektivt når det gjelder bruk av minne.
![LinkedList Java-datastruktur - 3]()
Siden
LinkedList faktisk er en toveis struktur, kan vi enkelt legge til eller fjerne elementer fra begge sider.
LinkedList-konstruktører
Tilbake til kodekilden kan vi finne ut at
LinkedList har to konstruktører
- LinkedList() uten parametere brukes til å konstruere en tom liste.
- >LinkedList(Collection<? utvider E> c) er for å lage en liste som inneholder elementene i den spesifiserte samlingen, i rekkefølge at de returneres av samlingens iterator.
LinkedList-erklæring
Faktisk består en koblet liste (Java eller på et annet språk) av en sekvens av noder. Hver node er designet for å lagre et objekt av en type som er definert når du oppretter. Så for å lage
LinkedList er Java-kode den neste:
LinkedList<Integer> myList = new LinkedList<>();
Vi har et formål å holde en sekvens av heltall og lenker til naboene. Det er imidlertid tomt for øyeblikket.
LinkedList Hovedoperasjoner
Som vanlig, når det gjelder samlinger, kan du legge elementer inn i
LinkedList (til slutten av den eller i midten), fjerne derfra og få et element etter indeks. Så her er de:
- add(E element) Legger til det spesifiserte elementet på slutten av denne listen;
- add(int index, E element) Setter inn elementet på den angitte posisjonsindeksen ;
- get(int index) Returnerer elementet på den angitte posisjonen i denne listen;
- remove(int index) Fjerner elementet som er på posisjonsindeks;
- remove(Object o) Fjerner den første forekomsten av ? o element fra denne listen hvis det er der.
- remove() Henter og fjerner det første elementet i listen.
Koblet listeimplementering i Java, legge til og fjerne elementer. Eksempel
La oss prøve disse operasjonene i praksis. Først, Java LinkedList-implementering: lage en LinkedList of Strings, og legge til 3 elementer. Fjern deretter en, og legg deretter til en i midten.
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);
}
Resultatet av å kjøre dette programmet:
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]
En
LinkedList er en del av
samlingsrammeverket , du kan bruke Iterator for å fjerne elementer, samt en spesiell iterator for lister —
ListIterator . Enda mer, operasjoner med iterator gir hovedfordelene med
LinkedList- klassen: god ytelse av inn-/slettoperasjoner. Ved å bruke Iterator kan du få en konstant tid for dem. Senere i denne artikkelen vil vi skrive et kodeeksempel for å sammenligne
ArrayList og
LinkedList+Iterator
- Iterator.remove() fjerner det siste elementet returnert av denne iteratoren.
- ListIterator.add(E-element) setter inn et element i listen
Java LinkedList Eksempel: hvordan Iterator fungerer
Her har vi en liten Java
LinkedList Eksempel-kode, hvor vi prøver å legge til og slette via Iterator.
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);
}
}
Resultatet av å kjøre dette programmet:
linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]
Flere Java
LinkedList- operasjoner:
- addFirst() , addLast() legger til et element i begynnelsen/slutten av en liste
- clear() fjerner alle elementer fra listen
- inneholder(Objekt o) returnerer sann hvis listen inneholder o-elementet.
- indeksOf(Objekt o) returnerer indeksen for den første forekomsten av o-elementet, eller -1 hvis det ikke er i listen.
- set(int index, E element) erstatter elementet i indeksposisjon med elementet
- size()Returnerer antallet elementer i listen.
- toArray() returnerer en matrise som inneholder alle listens elementer fra første til siste element.
Forresten, som en kø i to størrelser, har
LinkedList i Java stabelspesifikke operasjoner:
- pop() som spretter et element fra stabelen (representert av listen)
- push(E e) som skyver et element inn på stabelen (representert av denne listen)
Hvordan reversere LinkedList: eksempel
Her er et lite eksempel, en populær, men likevel enkel oppgave for nybegynnere. Vi har en
LinkedList og bør reversere den. Den enkleste algoritmen er å gå gjennom
LinkedList i omvendt rekkefølge og legge hvert element inn i det nye. Men kanskje du finner en bedre måte? Her er koden til java-programmet med omvendt lenket liste:
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;
}
}
Resultatet:
[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]
LinkedList vs ArrayList: når du skal bruke den første
Både
LinkedList og
ArrayList er implementeringer av
List- grensesnittet.
LinkedList implementerer det med en dobbeltlenket liste.
ArrayList implementerer det ved å bruke en dynamisk størrelsesrekke. Som du allerede vet, inneholder hver node i
LinkedList objekter og to referanser til naboene. Det betyr ekstra minnekostnader for lagring av referanser mellom elementer i tilfellet med Java
LinkedList .
ArrayList implementerer det med en dynamisk størrelsesreduksjon. Noen av
LinkedList- og
ArrayList -operasjonene ser like ut, men de fungerer på en annen måte. I
ArrayListtilfelle, du manipulerer med interne arrays, i
LinkedList - med referanser.
ArrayList er den mest populære
listeimplementeringen . Du bør definitivt bruke
ArrayList når indekstilgang er en prioritet siden disse operasjonene utføres i konstant tid. Legging til slutten av listen i gjennomsnitt gjøres også i konstant tid. Enda mer,
ArrayList har ikke ekstra kostnader for å lagre en haug med elementer. Du kan telle som negativ hastigheten på innsetting og fjerning når det ikke er gjort på slutten av listen.
LinkedLister mer nyttig i tilfelle av innsetting og sletting operasjoner ytelse på noen måter: hvis du bruker iteratorer det skjer i konstant tid. Tilgangsoperasjoner etter indeks utføres ved å søke fra begynnelsen av slutten (det som er nærmest) til ønsket element. Men ikke glem ekstra kostnader for lagring av referanser mellom elementer. Så her standard
LinkedList og
ArrayList operasjoner med algoritmiske kjøretider. N refererer til antall elementer som allerede er på listen.
O(N) betyr at vi i verste fall bør "gå" gjennom hele listen til den nødvendige posisjonen er funnet, for eksempel for innsetting av det nye elementet i listen.
O(1)betyr at operasjonen skjer i konstant tid, uavhengig av antall varer.
LinkedList-tidskompleksitet
LinkedList Java-operasjon |
Algoritmisk effektivitet |
get (int indeks) |
O(n) , i gjennomsnitt — n/4 trinn, der n er en LinkedList -størrelse |
add(E element) |
O(1) |
add(int indeks, E-element) |
O(n) , i gjennomsnitt — n/4 trinn; hvis indeks = 0 så O(1) , så hvis du trenger å legge til noe i begynnelsen av listen, kan LinkedList<E> være et godt valg |
remove(int index) |
O(n) , i gjennomsnitt — n/4 trinn |
Iterator.remove() |
O(1) Dette er hovedgrunnen til å bruke LinkedList<E> |
ArrayList Tidskompleksitet
LinkedList-operasjon |
Algoritmisk effektivitet |
get (int indeks) |
O(1) , en av hovedgrunnene til å bruke ArrayList<E> |
add(E element) |
O(n) er det verste tilfellet siden matrisen må endres størrelse og kopieres, men i praksis er det ikke så ille |
add(int indeks, E-element) |
O(n) , n/2 trinn i gjennomsnitt |
remove(int index) |
O(n) , n/2 trinn i gjennomsnitt |
Iterator.remove() |
O(n) , n/2 trinn i gjennomsnitt |
ListIterator.add(E-element) |
O(n) , n/2 trinn i gjennomsnitt |
Når du skal bruke LinkedList: Eksempel
ArrayList er definitivt den mest populære
listeimplementeringen . Du kan imidlertid møte situasjoner når legg til/fjern-operasjoner er nødvendig for ofte. I så fall kan
LinkedList sammen med Iterator være fordelaktig. Her er et eksempel. Vi har en lang liste, og vi bør slette hvert element fra denne listen. La oss gjøre denne oppgaven med
ArrayList og
LinkedList +
Iterator . Vi sammenligner tidspunktet for hver operasjon og skriver det ut i konsollen. Her er koden:
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);
}
}
}
Resultat for ArrayList:
start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414
Resultat for LinkedList:
start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458
Som du kan se i dette tilfellet er LinkedList mye mer effektivt. La oss være ærlige. I ekte programvareutvikling er
LinkedList- bruk en slags sjelden hendelse. Likevel bør en profesjonell vite om denne datastrukturens eksistens og dens fordeler.
Hvis LinkedList i ekte kode er en sjelden gjest, er det veldig populært på Java Junior-intervjuer. Og likevel, her er hva Joshua Bloch skrev om
LinkedList :
AddOn: Enkeltkoblet liste Java
Det er ingen Singly
Linked List blant klassisk
samling i Java, Singly
Linked List er en struktur der hver node inneholder et objekt og en referanse til neste node, men ikke for den forrige. Java
LinkedList er to-lenket, men ingen forstyrrer deg for å lage din egen datastruktur, for eksempel en Singly ,code>Linked List. Her er noen trinn for å løse disse oppgavene:
- Lag en nodeklasse med to attributter, data og neste. Neste er en referanse til neste node.
- Lag FirstLast- klassen med to attributter, hode og hale.
- Opprett en add()- metode for å legge til en ny node i listen. Sjekk om listen er tom først ( head == null ). I så fall refererer hode og hale til den nye noden. Hvis listen ikke er tom, vil den nye noden legges til på slutten, så neste attributt til halen refererer til den lagte noden og den nye noden blir halen på listen.
Du kan forresten prøve å lage din egen
LinkedList som en øvelse også. Lykke til i læringen.
GO TO FULL VERSION