Erstellen Sie eine generische LinkedList in Java

  2. How-To's
  3. Java-Howtos
  4. Erstellen Sie eine generische LinkedList …
Suraj P 12 Oktober 2023
Java Java LinkedList
  1. eine kurze Einführung in LinkedList in Java
  2. eine generische Implementierung von Single LinkedList in Java
Erstellen Sie eine generische LinkedList in Java

Dieser Artikel wird uns beibringen, wie man eine generische singly LinkedList in Java erstellt.

eine kurze Einführung in LinkedList in Java

LinkedLists sind lineare Datenstrukturen, die Daten in Knoten an zufälligen Adressen und Mittel an nicht zusammenhängenden Stellen speichern.

Jeder Knoten besteht aus zwei Teilen: Daten und Referenz (Adresse). Das Feld Daten/Wert speichert den Wert, und das Feld Referenz speichert die Adresse des nächsten Knotens der verknüpften Liste.

Einige der üblichen Operationen dieser Datenstruktur, die als Elementfunktionen implementiert werden, sind wie folgt.

  1. addNode() - Diese Methode wird verwendet, um ein neues Element am Ende der LinkedList hinzuzufügen.
  2. removeNode(value) – Diese Methode entfernt den Knoten mit dem angegebenen Wert.
  3. addNode(position,value) - Diese Methode wird verwendet, um den Wert an einer bestimmten Position hinzuzufügen.
  4. clear() - Diese Methode löscht die gesamte LinkedList.
  5. isEmpty() - Mit dieser Methode wird überprüft, ob die LinkedList leer ist oder nicht.
  6. length() - Diese Methode liefert uns die Länge der LinkedList.

eine generische Implementierung von Single LinkedList in Java

Eine normale LinkedList kann nur einen Werttyp speichern: Integer, String, Boolean, Float usw. Also müssen wir den Typ zum Zeitpunkt der Erstellung angeben, aber was ist, wenn wir die LinkedList erstellen wollen, die das kann Daten eines beliebigen Datentyps speichern; Dafür verwenden wir in Java das Konzept der Generika.

Erstellen einer generischen Knotenklasse:

Im folgenden Code bezeichnet T den Datentyp, der auf LinkedList gespeichert ist.

class Node<T> {
  T value;
  Node<T> nextPtr;

  Node(T value) {
    this.value = value;
    this.nextPtr = null;
  }
}

Lassen Sie uns nun die generischen Methoden zum Erstellen der Klasse LinkedList erstellen.

  1. Funktion add():

    void add(T value) {
  Node<T> temp = new Node<>(value); // creating a new node

  if (this.head == null) // checking if the list is empty
    head = temp;

  else // if the list is not empty, we go till the end and add the node
  {
    Node<T> tr = head;
    while (tr.nextPtr != null) {
      tr = tr.nextPtr;
    }

    tr.nextPtr = temp;
  }

  length = length + 1; // increasing the length of list
}

  2. Funktion remove():

    void remove(T key) {
  Node<T> prev = new Node<>(null);
  prev.nextPtr = head;
  Node<T> next = head.nextPtr;
  Node<T> tr = head;

  boolean isNodepresent = false; // to check if node is present

  if (head.value == key) {
    head = head.nextPtr;
    isNodepresent = true;
  }

  while (tr.nextPtr != null) {
    if (String.valueOf(tr.value).equals(
            String.valueOf(key))) { // if the node is present, we break the loop
      prev.nextPtr = next; // we assign previous node's nextPtr to next node
      isNodepresent = true;
      break;
    }

    prev = tr; // updating the previous and next pointers
    tr = tr.nextPtr;
    next = tr.nextPtr;
  }

  if (isNodepresent == false && String.valueOf(tr.value).equals(String.valueOf(key))) {
    prev.nextPtr = null;
    isNodepresent = true;
  }

  if (isNodepresent) {
    length--; // if the node is present, we reduce the length
  }

  else {
    System.out.println("The value is not present inside the LinkedList");
  }
}

  3. Funktion add(position,value):

    void add(int position, T value) {
  if (position > length + 1) // if the position entered is more than the list length
  {
    System.out.println("Position out of bound");
    return;
  }

  if (position == 1) { // if the position is one we'll just
    Node<T> temp = head;
    head = new Node<T>(value);
    head.nextPtr = temp;
    return;
  }

  Node<T> tr = head;
  Node<T> prev = new Node<T>(null); // creating a new node prev

  while (position - 1 > 0) // we find the position in the list
  {
    prev = tr;
    tr = tr.nextPtr;
    position--;
  }

  prev.nextPtr = new Node<T>(value); // update the next pointer of previous node
  prev.nextPtr.nextPtr = tr;
}

  4. Funktion getLength():

    int getLength() {
  return this.length; // returns the length of the list
}

  5. Funktion isEmpty():

    boolean isEmpty() {
  if (head == null) // if the list is empty we return true
    return true;

  else
    return false;
}

  6. clear()-Funktion:

    void clear() {
  head = null; // make head as null and length as zero
  length = 0;
}

  7. Funktion toString():

    Im folgenden Code haben wir die Methode toString hinzugefügt und überschrieben, um den Inhalt der LinkedList zu drucken.

    @Override
public String toString() {
  Node<T> temp = head;
  String str = "{ ";
  if (temp == null) // if the list is empty
  {
    System.out.println("list is empty");
  }

  while (temp.nextPtr != null) // we keep appending data to string till the list is empty
  {
    str += String.valueOf(temp.value) + "->";
    temp = temp.nextPtr;
  }

  str += String.valueOf(temp.value);
  return str + "}"; // we finally return the string
}

Vollständiger Arbeitscode mit der Klasse Haupt:

class Node<T> {
  T value;
  Node<T> nextPtr;

  Node(T value) {
    this.value = value;
    this.nextPtr = null;
  }
}

class LinkedList<T>
{
    Node<T> head;
    private int length = 0;

    LinkedList()
    {
        this.head = null;
    }

    void add(T value)
    {
        Node<T> temp = new Node<>(value);

        if(this.head == null)
            head = temp;
        else
        {
            Node<T> tr = head;
            while(tr.nextPtr!=null){
                tr = tr.nextPtr;
            }

            tr.nextPtr = temp;
        }
        length = length + 1;
    }

    void remove(T key)
    {
        Node<T> prev = new Node<>(null);
        prev.nextPtr = head;
        Node<T> next = head.nextPtr;
        Node<T> tr = head;

        boolean isNodepresent = false;

        if(head.value == key ){
            head = head.nextPtr;
            isNodepresent =true;
        }

        while(tr.nextPtr!=null)
        {
            if(String.valueOf(tr.value).equals(String.valueOf(key))){
                prev.nextPtr = next;
                isNodepresent = true;
                break;
            }

            prev = tr;
            tr = tr.nextPtr;
            next = tr.nextPtr;

        }

        if(isNodepresent==false && String.valueOf(tr.value).equals(String.valueOf(key))){
            prev.nextPtr = null;
            isNodepresent = true;
        }

        if(isNodepresent)
        {
            length--;
        }

        else
        {
            System.out.println("The value is not present inside the LinkedList");
        }
    }

    void add(int position,T value)
    {
        if(position>length+1)
        {
            System.out.println("Position out of bound");
            return;
        }

        if(position==1){
            Node<T> temp = head;
            head = new Node<T>(value);
            head.nextPtr = temp;
            return;
        }

        Node<T> tr = head;
        Node<T> prev = new Node<T>(null);

        while(position-1>0)
        {
            prev = tr;
            tr = tr.nextPtr;
            position--;
        }

        prev.nextPtr = new Node<T>(value);
        prev.nextPtr.nextPtr = tr;
    }

    int getLength()
    {
        return this.length;
    }

    boolean isEmpty()
    {
        if(head == null)
            return true;

        else
            return   false;
    }

    void clear()
    {
        head = null;
        length = 0;
    }

    @Override
     public String toString()
    {
      Node<T> temp = head;
      String str = "{ ";
      if(temp == null)
      {
          System.out.println( "list is empty");
      }

      while(temp.nextPtr!=null)
      {
          str += String.valueOf(temp.value) +"->";
          temp = temp.nextPtr;
      }

      str += String.valueOf(temp.value);
      return str+"}";
    }
}


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

       LinkedList<Integer> ll = new LinkedList<>();
       ll.add(1);
       ll.add(2);
       ll.add(3);

       System.out.println(ll);

       ll.remove(3);
       System.out.println(ll);

       ll.add(2,800);
       System.out.println(ll);
    }
}

Ausgang:

{ 1->2->3}
{ 1->2}
{ 1->800->2}
Autor: Suraj P
Suraj P avatar Suraj P avatar

A technophile and a Big Data developer by passion. Loves developing advance C++ and Java applications in free time works as SME at Chegg where I help students with there doubts and assignments in the field of Computer Science.

LinkedIn GitHub

Verwandter Artikel - Java LinkedList