Java >> Java tutorial >  >> Java

LinkedList intern implementering i Java

Java

I posten ArrayList Internal Implementation i Java har vi allerede set de interne implementeringsdetaljer for en af ​​implementeringerne af List-grænsefladen – ArrayList . I dette indlæg ser vi LinkedList intern implementering i Java som er en anden implementering af List-grænsefladen

Spørgsmål, der kan dukke op til, hvordan LinkedList fungerer internt i Java, er som følger-

  1. Hvordan gemmer klassen LinkedList sit element.
  2. Er LinkedList-klassen i Java implementeret som en enkelt-linket liste eller en dobbelt-linket liste.
  3. Hvad sker der, når element føjes til LinkedList. Da det er en LinkedList, så hvad er implementeringen for at tilføje element på den første position eller på den sidste.
  4. Hvordan virker remove()-metoden i LinkedList.
  5. Hvordan fungerer get()-metoden i LinkedList.

Lad os i dette indlæg prøve at besvare disse spørgsmål ved at se på den interne implementering af LinkedList i Java.

Hvordan gemmer klassen LinkedList sit element

Internt LinkedList-klassen i Java bruger objekter af typen Node for at gemme de tilføjede elementer. Node er implementeret som en statisk klasse med i LinkedList-klassen. Da LinkedList-klassen er implementeret som en dobbelt-linket liste så hver node gemmer reference til den næste såvel som tidligere noder sammen med det tilføjede element.

Nodeklassekode i JDK 10 
private static class Node<E> {
  E item;
  Node<E> next;
  Node<E> prev;

  Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
  }
}

Er det en dobbelt linket liste

Som allerede vist er Java LinkedList-klassen implementeret som en dobbelt linket liste, og hver node gemmer reference til den næste såvel som tidligere noder.

Sådan fungerer add()-metoden i en LinkedList

Da det er en sammenkædet liste, så bortset fra almindelig add() metode til at tilføje sekventielt er der addFirst() og addLast() metoder også i Java LinkedList-klassen.

Der er også separate variabler til at holde referencen til den første og sidste node på den sammenkædede liste.

/**
* Pointer to first node.
*/
transient Node<E> first;

/**
* Pointer to last node.
*/
transient Node<E> last;

Hvis du kalder den almindelige add()-metode eller addLast()-metoden, kaldes linkLast()-metoden internt. I denne metode oprettes en ny node til at gemme det tilføjede element, og variablen sidst begynder at referere til denne node (da denne nye node bliver den sidste node). Der er også en kontrol for at se, om det er den allerførste indsættelse, i så fald er denne node også den første node.

linkLast()-metodeimplementering i LinkedList-klassen 
/**
 * Links e as last element.
 */
void linkLast(E e) {
  final Node<E> l = last;
  final Node<E> newNode = new Node<>(l, e, null);
  last = newNode;
  if (l == null)
    first = newNode;
  else
    l.next = newNode;
  size++;
  modCount++;
}

Hvis du kalder addFirst() metode internt linkFirst() metode kaldes. I denne metode oprettes en ny node til at gemme det tilføjede element, og variablen begynder først at referere til denne node (da denne nye node bliver den første node). Der er også en kontrol for at se, om det er den allerførste indsættelse, i så fald er denne node også den sidste node. Hvis det ikke er den første node, kommer den forrige "første" node nu på den anden position, så dens forrige reference skal referere til den nye node.

LinkFirst()-metodeimplementering i LinkedList-klassen 
/**
 * Links e as first element.
 */
private void linkFirst(E e) {
  final Node<E> f = first;
  final Node<E> newNode = new Node<>(null, e, f);
  first = newNode;
  if (f == null)
    last = newNode;
  else
    f.prev = newNode;
  size++;
  modCount++;
}

Der er også en add() metode til at tilføje element til et specifikt indeks. Hvis denne metode kaldes, skal det allerede eksisterende element ved det beståede indeks flyttes til højre.

Sådan fungerer remove()-metoden i Java LinkedList-klassen

Ligesom add() metode til at fjerne et element fra LinkedList bortset fra almindelig remove() metode (hvor indeks eller element sendes) er der også removeFirst() og removeLast() metoder.

Når metoden remove() kaldes, skal referencen for noderne til venstre og højre for de fjernede noder ændres, så den næste af noden til venstre begynder at referere til noden til højre og den forrige node til højre. begynder at henvise til noden til venstre for noden, der skal fjernes.

Følgende billede hjælper dig med at forstå, hvad der faktisk skal gøres. Her skal den midterste node fjernes.

Sådan fungerer get()-metoden i Java LinkedList-klassen

I tilfælde af get() metode igen er der getFirst() og getLast() metoder også. I tilfælde af get()-metoden skal den hente noden for det beståede indeks og returnere node.item.

public E get(int index) {
  checkElementIndex(index);
  return node(index).item;
}

I tilfælde af getFirst() og getLast() lagres referencen også i den første og sidste variabel, så du skal bare returnere værdien first.item eller last.item.

Relaterede indlæg
  • ArrayList intern implementering i Java
  • ArrayList vs LinkedList i Java
  • HashSet intern implementering i Java
  • HashMap intern implementering i Java
  • Konverter Array til ArrayList i Java
  • Java uforanderlig liste med eksempler
  • isAlive() Og join()-metoder i Java
  • CyclicBarrier i Java med eksempler

Det er alt for emnet LinkedList intern implementering i Java . Hvis der mangler noget, eller du har noget at dele om emnet, så skriv en kommentar.


Java tag