LinkedListin sisäinen rakenne
Tutustu LinkedListin kaksisuuntaisesti linkitettyyn solmurakenteeseen ja sen aikavaativuuteen.
LinkedListin sisäinen rakenne on ilmainen Java Academy-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Java Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Java Academy-kurssilla on yhteensä 4 oppituntia.
LinkedListin sisäinen rakenne
Javan LinkedList on kaksisuuntaisesti linkitetty lista: jokainen solmu sisältää viitteen edelliseen ja seuraavaan solmuun sekä alkion arvon. Toisin kuin ArrayList-luokassa, taustalla ei ole taulukkoa — muisti varataan solmukohtaisesti.
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) { this.data = data; }
}Aikavaativuuden profiili
LinkedListin suorituskykyominaisuudet eroavat merkittävästi ArrayLististä:
- addFirst / addLast: O(1)
- get(index): O(n) — on kuljettava pään tai hännän suunnasta
- remove(index): O(n) alkion löytämiseen, sitten O(1) irrottamiseen
- Iterator traversal: O(n)
LinkedList kannattaa valita, kun tarvitaan usein lisäyksiä listan alkuun tai loppuun, ei satunnaista indeksikäyttöä.
LinkedListin luominen ja läpikäynti
LinkedList-rakenteen luominen ja läpikäynti noudattavat samaa List-rajapintaa, jonka tunnette jo ennestään. Ero on sisäisessä rakenteessa.
import java.util.LinkedList;
LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");
for (String name : list) {
System.out.println(name);
}
System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: " + list.getLast()); // CaroladdFirst, addLast, removeFirst, removeLast
LinkedList tarjoaa alku- ja loppupään toimintoja, joita ArrayList ei tarjoa yhtä tehokkaasti:
LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10); // [10]
nums.addLast(20); // [10, 20]
nums.addFirst(5); // [5, 10, 20]
System.out.println(nums.removeFirst()); // 5 → [10, 20]
System.out.println(nums.removeLast()); // 20 → [10]Solmun irrottaminen: O(1)-poisto solmun löytämisen jälkeen
Kun käytettävissä on viite solmuun (iteraattorin kautta), poisto on O(1), koska vain next- ja prev-viitteitä tarvitsee päivittää — alkioita ei tarvitse siirtää kuten ArrayListissä.
import java.util.*;
LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
String t = it.next();
if (t.equals("B") || t.equals("D")) {
it.remove(); // O(1) unlink
}
}
System.out.println(tasks); // [A, C]Muistinkulutus verrattuna ArrayListiin
Jokaisessa LinkedList-solmussa on kaksi ylimääräistä viitettä (prev, next) sekä viite alkioon — 64-bittisessä JVM:ssä noin 48 tavua alkiota kohti. ArrayList tallentaa vain alkion viitteen (8 tavua) yhtenäiseen taulukkoon.
Suurissa, paljon lukemista sisältävissä aineistoissa ArrayList on yleensä välimuistin kannalta tehokkaampi ja käyttää vähemmän muistia.
Deque-toiminnot: pino ja jono
LinkedList toteuttaa Deque-rajapinnan, joten sitä voidaan käyttää sekä pinona että jonona.
import java.util.LinkedList;
import java.util.Deque;
// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first
// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // topPriorityQueue yleiskatsaus
PriorityQueue on keon varaan perustuva jono, josta pienin alkio (luontaisen järjestyksen tai vertailijan mukaan) poistetaan aina ensin. Se EI perustu linkitettyyn listaan — se käyttää binäärikekoa taulukkona.
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);
System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40PriorityQueue mukautetulla Comparatorilla
Järjestyksen kääntämiseen tai mukautetun kentän mukaan lajitteluun voidaan antaa Comparator:
import java.util.*;
record Task(String name, int priority) {}
PriorityQueue<Task> tasks = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));
while (!tasks.isEmpty()) {
System.out.println(tasks.poll().name());
}
// High, Med, LowLinkedListin ja ArrayListin valinta
Nyrkkisääntö:
- Käyttäkää ArrayList-rakennetta satunnaiskäyttöön, läpikäyntiin ja useimpiin tilanteisiin.
- Käyttäkää LinkedList-rakennetta, kun molempiin päihin tarvitaan usein O(1)-aikaisia lisäyksiä ja poistoja eikä indeksikäyttöä tarvita.
- Käyttäkää PriorityQueue-rakennetta, kun tarvitaan järjestyksessä käsittelyä, kuten tehtävien ajoituksessa tai Dijkstran algoritmissa.
Yleiset sudenkuopat
Välttäkää get(i)-kutsua silmukassa LinkedList-rakenteelle — kokonaiskustannus on O(n²):
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);
// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
int val = list.get(i); // slow!
}
// GOOD: O(n) — use iterator
for (int val : list) {
// process val
}Pikatarkistus
Mikä LinkedList-toiminto on O(1) listan koosta riippumatta?
Kertaus: LinkedList ja Deque
Tärkeimmät asiat:
- LinkedList on kaksisuuntaisesti linkitetty lista, jonka alku- ja loppupään toiminnot ovat O(1)
- Satunnaiskäyttö (get/set indeksin perusteella) on O(n)
- Toteuttaa Deque-rajapinnan — sitä voidaan käyttää pinona tai jonona
- PriorityQueue mahdollistaa kekojärjestykseen perustuvan käsittelyn
- Suosikaa useimmissa käyttötapauksissa ArrayList-rakennetta; LinkedList sopii erityisesti usein toistuviin muutoksiin listan alussa tai lopussa
Opi Java tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 104
- Oppitunnit
- 374
Usein kysytyt kysymykset
Onko oppitunti ”LinkedListin sisäinen rakenne” ilmainen?
Kyllä – oppitunnin ”LinkedListin sisäinen rakenne” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Java Academy-kurssin, päivitä CoddyKit PROhon. Java Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”LinkedListin sisäinen rakenne”?
Tutustu LinkedListin kaksisuuntaisesti linkitettyyn solmurakenteeseen ja sen aikavaativuuteen. Harjoittelet Java Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Java Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Java Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”LinkedListin sisäinen rakenne”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Java Academy-oppitunnilla?
Kyllä. Jokainen Java Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- LinkedListin sisäinen rakenne
- Deque-toiminnot: pino ja jono
- LinkedListin ja ArrayListin kompromissit
- PriorityQueue järjestettyyn käsittelyyn