Java >> Java tutorial >  >> Java

LinkedList i Java forklaret med eksempler

Java

LinkedList er en lineær datastruktur, der ligner arrays i Java. LinkedList-elementer, på den anden side, holdes ikke på sammenhængende steder som arrays; i stedet er de knyttet sammen via pointere. Hvert LinkedList-medlem har en reference (adresse/pointer) til det næste LinkedList-element.

Elementerne i Java LinkedList-klassen gemmes som en dobbelt-linket liste. Det bruger en linked-liste datastruktur til at gemme information. Det implementerer List og Deque-grænseflader og arver AbstractList-klassen. Listegrænsefladen er implementeret af klasserne AbstractList, CopyOnWriteArrayList og AbstractSequentialList. Hver af de ovennævnte klausuler har sit eget sæt funktioner. De er som følger:

Abstraktliste :Denne klasse bruges til at implementere en uforanderlig liste, og alt hvad der kræves er at udvide den og kun implementere funktionerne get() og size(). Denne klasse implementerer listegrænsefladen.

CopyOnWriteArrayList :Denne klasse implementerer listegrænsefladen. Det er en forbedret version af ArrayList, hvor alle ændringer (tilføj, sæt, slet og så videre) foretages ved at oprette en ny kopi af listen.

Følgende er nøglefunktionerne i Java LinkedList:

  • Duplikerede elementer er mulige i Java LinkedList-klassen.
  • Klassen LinkedList i Java holder styr på indsættelsesrækkefølgen.
  • Klassen LinkedList i Java er ikke-synkroniseret.
  • Manipulation i Java LinkedList-klassen er hurtig, da der ikke kræves forskydning.
  • Klassen LinkedList i Java bruges til at oprette en liste, en stak eller en kø.

Repræsentation af LinkedList

  • Noden er det navn, der gives til hvert element i LinkedList. LinkedLists noder har hver to elementer:
  • a) Elementets indhold
  • b) Pointer/adresse/reference til den linkede listes næste node.
  • Den linkede listes hoved indeholder kun adressen på listens første element.
  • Fordi det er slutningen af ​​listen, har det sidste element i LinkedList null i pointersektionen af ​​noden, som vist i diagrammet.
  • Standard-linket liste er en enkelt-linket liste.
  • Den dobbeltlinkede liste er en mere kompleks version af LinkedList. Hver node i en dobbelt-linket liste består af tre dele:
  • a) En pegepind til den linkede listes tidligere node.
  • b) Elementets indhold
  • c) En pointer til den linkede listes næste node.

Hvad er formålet med en linket liste?

Du bør være bekendt med arrays, som også er lineære datastrukturer, men de har nogle begrænsninger, såsom:

  • Størrelsen af ​​et array er fast, og det er svært at forudsige antallet af elementer på forhånd. Hvis den angivne størrelse kommer til kort, kan vi ikke øge en matrixs størrelse; hvis vi erklærer en stor matrix og ikke behøver at gemme så mange elementer, er det spild af hukommelse.
  • For at gemme deres værdier kræver matrixelementer sammenhængende hukommelsesområder.
  • Indsættelse af et element i et array er langsomt, da det kræver at flytte andre elementer for at skabe plads til det nye element. Lad os forestille os, at vi har en matrix med følgende elementer:40, 42, 55, 60, 74, 95, 109. Hvis vi vil tilføje et nyt element 58 efter elementet med værdien 42, skal vi først flytte alle elementerne efter 42 til højre for at give plads til det nye element.

Tilsvarende er sletning af et element fra et array en tidskrævende operation, da alle elementer efter det slettede element skal flyttes til venstre. Den linkede liste overvinder disse begrænsninger ved at give følgende funktioner:

  • Linkede lister understøtter dynamisk hukommelsesallokering, hvilket betyder, at compileren allokerer hukommelse ved kørsel, og vi behøver ikke at angive listestørrelsen, når vi erklærer den linkede liste.
  • Fordi elementer er forbundet med hinanden ved hjælp af referencekomponenten i noden, som angiver adressen på den næste node på listen, kræver linkede listeelementer ikke sammenhængende hukommelsesplaceringer.
  • Indsættelse og sletning af linkede lister er ikke præstationskrævende. Tilføjelse og sletning af et element fra den linkede liste kræver ikke elementskift. I stedet skal markøren til den forrige og næste node ændres.

Internt, hvordan fungerer LinkedList?

Fordi en LinkedList fungerer som en dynamisk matrix, og vi ikke behøver at definere størrelsen, når vi opretter den, vokser listens størrelse, efterhånden som vi tilføjer og sletter elementer dynamisk. Desuden holdes elementerne ikke i en kontinuerlig tilstand. Som et resultat er der ingen grund til at udvide størrelsen.

Den dobbelt linkede listedatastruktur bruges til at implementere LinkedList internt. Den grundlæggende forskel mellem en standard-linket liste og en dobbelt-linket liste er, at sidstnævnte har en ekstra pointer, sædvanligvis omtalt som den forrige pointer, ud over den næste pointer og data, der findes i den enkelt linkede liste.

Java LinkedList-metoder

LinkedList har flere metoder, der udfører forskellige handlinger på linkede lister. I denne artikel vil vi se på fire ofte brugte LinkedList-operatører:

  • Tilføjelse af elementer
  • Elementadgang
  • Ændring af elementer
  • Fjernelse af elementer

Tilføjelse af elementer til en LinkedList

Add() metoden bruges til at tilføje et element (node) til slutningen af ​​en LinkedList. Som et eksempel,

import java.util.LinkedList;

class CodeMain {

  public static void main(String[] args){
    // creation of a citiesList linkedlist
    LinkedList<String> citiesList = new LinkedList<>();

    // add() method without the index parameter
    citiesList.add("New York");
    citiesList.add("Los Angeles");
    citiesList.add("Manchester");
    System.out.println("LinkedList: " + citiesList);

    // add() method with the index parameter
    citiesList.add(1, "Paris");
    System.out.println("Updated LinkedList: " + citiesList);
  }
}

Vi etablerede en LinkedList navngivne byer i det foregående eksempel. I dette eksempel har vi brugt add()-metoden til at tilføje komponenter til byer.

citiesList.add(1, "Paris");

Vi har brugt indeksnummerparameteren i dette tilfælde. Det er et valgfrit argument, der bestemmer, hvor det nye element skal placeres.

Adgang til LinkedList-elementer

For at få adgang til et LinkedList-element skal du bruge funktionen get() i klassen LinkedList. Som et eksempel,

import java.util.LinkedList;

class CodeMain {
  public static void main(String[] args) {
    LinkedList<String> compCompanies = new LinkedList<>();

    // add elements in the linked list
    compCompanies.add("Microsoft");
    compCompanies.add("Apple");
    compCompanies.add("Google");
    System.out.println("LinkedList: " + compCompanies);

    // get the element from the linked list
    String strVal = compCompanies.get(1);
    System.out.print(" The Item at index 1: " + strVal);
  }
}

Vi brugte get()-metoden med parameter 1 i det foregående eksempel. Proceduren returnerer elementet ved indeks 1 i dette tilfælde.

Ændring af en LinkedLists elementer

Set()-funktionen i LinkedList-klassen bruges til at ændre LinkedLists elementer. Som et eksempel,

import java.util.LinkedList;

class CodeMain {
  public static void main(String[] args) {

    LinkedList<String> clubList = new LinkedList<>();

    // add elements in the linked list
    clubList.add("Chelsea");
    clubList.add("Manchester City");
    clubList.add("Liverpool");
    languages.add("Manchester United");
    System.out.println("The original club LinkedList is: " + clubList);

    // changing the elements at the third index
    languages.set(3, "Aston Villa");
    System.out.println("The updated club LinkedList is : " + clubList);
  }
}

Slet et element fra en LinkedList

LinkedList-klassens remove()-metode bruges til at slette et element fra LinkedList. Som et eksempel,

import java.util.LinkedList;

class CodeMain {
  public static void main(String[] args) {
    LinkedList<String> fruitList = new LinkedList<>();

    // add elements in LinkedList
    fruitList.add("Java");
    fruitList.add("Python");
    fruitList.add("JavaScript");
    fruitList.add("Kotlin");
    System.out.println("LinkedList: " + fruitList);

    // remove elements from index 1
    String str = fruitList.remove(1);
    System.out.println("Removed Element: " + str);

    System.out.println("Updated LinkedList: " + fruitList);
  }
}

Yderligere metoder

  • contains() – bestemmer om elementet er til stede i LinkedList
  • indexOf() – returnerer indekset for elementets første optræden.
  • LastIndexOf() – giver indekset for elementets seneste forekomst
  • clear() – fjerner alle LinkedLists elementer
  • iterator() -leverer en iterator, der bruges til at sløjfe over LinkedList.

Deque og kø for LinkedList

Fordi LinkedList-klassen implementerer både Queue- og Deque-grænsefladen, kan den gennemtvinge funktioner fra begge. Her er et par af de mest populære metoder:

  • addFirst() – tilføjer det angivne element til den linkede listes begyndelse.
  • addLast() - tilføjer den leverede post til slutningen af ​​den linkede liste
  • getFirst() – ansvarlig for at returnere det første element
  • getLast() – ansvarlig for at returnere det sidste element
  • removeFirst() – har til opgave at fjerne det første element
  • removeLast() – har til opgave at fjerne det sidste element
  • peek() – giver den linkede listes første medlem (hoved).
  • poll() – henter den første post på den linkede liste og fjerner den
  • offer() – tilføjer den medfølgende post til slutningen af ​​den linkede liste

Eksempel:Tilføjelse af elementer til en Java Linked List

Metoderne add(), addFirst() og addLast() bruges i følgende eksempel til at tilføje medlemmer til LinkedList på de korrekte positioner. Der er flere andre nyttige metoder i LinkedList-klassen, som jeg vil beskrive i slutningen af ​​denne artikel.

package com.codeunderscored;
import java.util.*;

public class CodeExampleJava{

   public static void main(String args[]){

     LinkedList<String> strList=new LinkedList<String>();

     //Linked list components are being added.
     strList.add("Green");
     strList.add("White");
     strList.add("Brown");

     //Adding a second element to the first
     strList.addFirst("Monroe");

     //Incorporating a new element into the final position
     strList.addLast("Spider");

     //Incorporating an element into the third position
     strList.add(2, "James");

     //LinkedList Iteration
     Iterator<String> newIterator=list.iterator();
     while(newIterator.hasNext()){
       System.out.println(newIterator.next());
     }
   }
}

Eksempel:LinkedList som Deque

import java.util.LinkedList;
import java.util.Deque;

class CodeMain {
  public static void main(String[] args){

    Deque<String> citiesList = new LinkedList<>();

    // adding a new item to citiesList's beginning
    citiesList.add("Manchester");
    System.out.println("LinkedList: " + citiesList);

    citiesList.addFirst("London");
    System.out.println("LinkedList after addFirst(): " + citiesList);

    // adding a new element to citiesList's end
    citiesList.addLast("New York");
    System.out.println("LinkedList after addLast(): " + citiesList);

    // removing the first element from  citiesList
    citiesList.removeFirst();
    System.out.println("LinkedList after removeFirst(): " + citiesList);

    // removal of the last element from  citiesList
    citiesList.removeLast();
    System.out.println("LinkedList after removeLast(): " + citiesList);
  }
}

Eksempel:Fjernelse af elementer fra en LinkedList

I det følgende eksempel vil vi se på nogle få typiske fjernelsesmetoder i LinkedList, der bruges til at fjerne elementer fra specifikke punkter i LinkedList. De separate selvstudier giver en detaljeret beskrivelse af disse strategier og eksempler.

package com.codeunderscored;
import java.util.*;

public class CodeExampleJava{
   public static void main(String args[]){

      LinkedList<String> nameList=new LinkedList<String>();

      //Linked list components are being added.
      nameList.add("Mike");
      nameList.add("Joy");
      nameList.add("White");
      nameList.add("Monroe");
      nameList.add("James");

      //Getting rid of the first element
      //Same as list.remove(0);
      nameList.removeFirst();

      //Removing the final component
      nameList.removeLast();

      //LinkedList Iteration
      Iterator<String> newIterator=nameList .iterator();
      while(newIterator .hasNext()){
         System.out.print(newIterator .next()+" ");
      }

      //When the second element is removed, the index is reset to zero.
      nameList.remove(1);

      System.out.print("\nAfter removing second element: ");

      //Re-iterating the LinkedList
      Iterator<String> secondIterator=nameList .iterator();
      while(secondIterator .hasNext()){
         System.out.print(secondIterator .next()+" ");
      }
   }
}

Eksempel:Iteration gennem LinkedList 

import java.util.LinkedList;

class CodeMain {
    public static void main(String[] args) {

        // Creating a new linked list
        LinkedList<String> flowerList = new LinkedList<>();
        flowerList.add("Rose");
        flowerList.add("Aster");
        flowerList.add("Azalea");
        System.out.println("The flowerList LinkedList is: " + flowerList);

        // Using the forEach loop
        System.out.println("Accessing the flowerList list elements:");
        for(String fl: flowerList) {
            System.out.print(fl);
            System.out.print(", ");
        }
    }
}

Eksempel:LinkedList i Java

import java.util.*;

public class CodeLinkedList {

     public static void main(String args[]) {

       /* Declaration of a Linked List */
       LinkedList<String> strLinkedList = new LinkedList<String>();

       /*
* The function add(String Element) adds elements to the linked list.
*/

       strLinkedList.add("IBM");
       strLinkedList.add("Lenovo");
       strLinkedList.add("Toshiba");
       strLinkedList.add("Apple");
       strLinkedList.add("Microsoft");

       /*Display Linked List Content*/
       System.out.println("The contents of the Linked List comprise of: " +strLinkedList);

       /*Add First and Last Element*/
       strLinkedList.addFirst("First Item");
       strLinkedList.addLast("Last Item");
       System.out.println("Content of the LinkedList once it has been added : " +strLinkedList);

       /* This is how you get values and change them.  */
       Object firstvar = linkedlist.get(0);
       System.out.println("The First element is: " +firstvar);
       linkedlist.set(0, "The first point has been modified.  ");

       Object secondVar = linkedlist.get(0);
       System.out.println("First element after update by set method: " +secondVar);

       /*Remove first and last element*/
       strLinkedList.removeFirst();
       strLinkedList.removeLast();
       System.out.println("LinkedList with the first and last elements removed : " +strLinkedList);

       /* Toggle between adding and removing items from a place. */
       strLinkedList.add(0, "Item that has recently been added ");
       strLinkedList.remove(2);
       System.out.println("The comprehensive Content is: " +strLinkedList);
     }
}

Eksempel:Java LinkedList som kø

import java.util.LinkedList;
import java.util.Queue;

class CodeMain {
  public static void main(String[] args) {

    Queue<String> fruitsList = new LinkedList<>();

    // add elements
    fruitsList.add("Mango");
    fruitsList.add("Quava");
    fruitsList.add("Apple");
    System.out.println("LinkedList: " + fruitsList);

    // accessing the fruitsList's first element
    String str_one = fruitsList.peek();
    System.out.println("Accessed Element: " + str_one);

    // accessing and removing the fruitsList's first element
    String second_string = fruitsList.poll();
    System.out.println("Removed Element: " + second_string);
    System.out.println("LinkedList after poll(): " + fruitsList);

    // add a new fruits at the end of  fruitsList
    languages.offer("Banana");
    System.out.println("LinkedList after offer(): " + fruitsList);
  }
}

Konklusion

Denne artikel har forklaret, hvad en linket listedatastruktur er i Java, og hvordan man opretter, initialiserer, implementerer, gennemløber, vender tilbage og sorterer en.

En LinkedList er en datastruktur i Java, der indeholder elementer på en ikke-sammenhængende måde. Det er en datastruktur, der er lineær. Hvert dataelement omtales som en 'Node', og hver node har to dele:data og adresse. Adressekomponenten i LinkedList gemmer linket til den næste node.

Samlingsrammen i java.util-pakken inkluderer en linket liste. Denne klasse implementerer LinkedList-datastrukturen, en lineær datastruktur, hvor komponenterne ikke holdes i sekventiel rækkefølge. Hvert element er et separat objekt med en data- og adressedel. Pointere og adresser bruges til at forbinde elementerne. Hvert element omtales som en node.

De er at foretrække frem for arrays på grund af deres dynamiske natur og lette indsættelser og fjernelser. Det har også nogle ulemper, såsom uopnåelige noder med det samme; i stedet skal vi starte øverst og følge linket til den ønskede node.


Java tag