Wie erstelle ich eine Linked-List-Datenstruktur in Java?

Question

Was ist der beste Weg, um eine verknüpfte Liste in Java zu erstellen?

Answer 1

Die offensichtliche Lösung für Entwickler vertraut Java ist die LinkedList Klasse bereits in java.util zu nutzen. Angenommen, Sie wollten aus irgendeinem Grund Ihre eigene Implementierung durchführen. Hier ist ein kurzes Beispiel einer verketteten Liste, die einen neuen Link am Anfang der Liste einfügt, vom Anfang der Liste löscht und die Liste durchläuft, um die darin enthaltenen Links zu drucken. Erweiterungen diese Implementierung gehören so dass es eine doppelt verknüpften Liste, Hinzufügen von Methoden zu Einsatz und aus der Mitte oder am Ende löschen, und durch Zugabe von erhalten und Art Methoden als auch.

Hinweis: Im Beispiel wird der Link-Objekt tatsächlich nicht einen anderen Link-Objekt enthalten - Nextlink ist eigentlich nur ein Verweis auf eine andere Verbindung.

class Link { 
    public int data1; 
    public double data2; 
    public Link nextLink; 

    //Link constructor 
    public Link(int d1, double d2) { 
     data1 = d1; 
     data2 = d2; 
    } 

    //Print Link data 
    public void printLink() { 
     System.out.print("{" + data1 + ", " + data2 + "} "); 
    } 
} 

class LinkList { 
    private Link first; 

    //LinkList constructor 
    public LinkList() { 
     first = null; 
    } 

    //Returns true if list is empty 
    public boolean isEmpty() { 
     return first == null; 
    } 

    //Inserts a new Link at the first of the list 
    public void insert(int d1, double d2) { 
     Link link = new Link(d1, d2); 
     link.nextLink = first; 
     first = link; 
    } 

    //Deletes the link at the first of the list 
    public Link delete() { 
     Link temp = first; 
     if(first == null){ 
     return null; 
     //throw new NoSuchElementException(); // this is the better way. 
     } 
     first = first.nextLink; 
     return temp; 
    } 

    //Prints list data 
    public void printList() { 
     Link currentLink = first; 
     System.out.print("List: "); 
     while(currentLink != null) { 
      currentLink.printLink(); 
      currentLink = currentLink.nextLink; 
     } 
     System.out.println(""); 
    } 
} 

class LinkListTest { 
    public static void main(String[] args) { 
     LinkList list = new LinkList(); 

     list.insert(1, 1.01); 
     list.insert(2, 2.02); 
     list.insert(3, 3.03); 
     list.insert(4, 4.04); 
     list.insert(5, 5.05); 

     list.printList(); 

     while(!list.isEmpty()) { 
      Link deletedLink = list.delete(); 
      System.out.print("deleted: "); 
      deletedLink.printLink(); 
      System.out.println(""); 
     } 
     list.printList(); 
    } 
} 

Answer 2

Java hat eine LinkedList Implementierung, die Sie vielleicht ausprobieren möchten. Sie können das JDK und seine Quellen unter java.sun.com herunterladen.

Answer 3

Verwenden Sie java.util.LinkedList. Wie folgt aus:

list = new java.util.LinkedList() 

Answer 4

Es ist viel besser zu nutzen java.util.LinkedList, weil es wahrscheinlich viel mehr optimiert ist, als die, die Sie schreiben.

Answer 5

Die oben verlinkte Liste wird in entgegengesetzter Richtung angezeigt. Ich denke, die korrekte Umsetzung der insert-Methode

public void insert(int d1, double d2) { 
    Link link = new Link(d1, d2); 

    if(first==null){ 
     link.nextLink = null; 
     first = link; 
     last=link; 
    } 
    else{ 
     last.nextLink=link; 
     link.nextLink=null; 
     last=link; 
    } 
} 

Answer 6

//slightly improved code without using collection framework 

package com.test; 

public class TestClass { 

    private static Link last; 
    private static Link first; 

    public static void main(String[] args) { 

     //Inserting 
     for(int i=0;i<5;i++){ 
      Link.insert(i+5); 
     } 
     Link.printList(); 

     //Deleting 
     Link.deletefromFirst(); 
     Link.printList(); 
    } 


    protected static class Link { 
     private int data; 
     private Link nextlink; 

     public Link(int d1) { 
      this.data = d1; 
     } 

     public static void insert(int d1) { 
      Link a = new Link(d1); 
      a.nextlink = null; 
      if (first != null) { 
       last.nextlink = a; 
       last = a; 
      } else { 
       first = a; 
       last = a; 
      } 
      System.out.println("Inserted -:"+d1); 
     } 

     public static void deletefromFirst() { 
      if(null!=first) 
      { 
       System.out.println("Deleting -:"+first.data); 
       first = first.nextlink; 
      } 
      else{ 
       System.out.println("No elements in Linked List"); 
      } 
     } 

     public static void printList() { 
      System.out.println("Elements in the list are"); 
      System.out.println("-------------------------"); 
      Link temp = first; 
      while (temp != null) { 
       System.out.println(temp.data); 
       temp = temp.nextlink; 
      } 
     } 
    } 
}