¿Cómo creo una estructura de datos de lista enlazada en Java?

Question

¿Cuál es la mejor manera de hacer una lista vinculada en Java?

Answer 1

La solución obvia a los desarrolladores familiarizados con Java es utilizar el clase LinkedList ya previstos en java.util. Digamos, sin embargo, que quería hacer su propia implementación por alguna razón. Aquí hay un ejemplo rápido de una lista vinculada que inserta un nuevo enlace al principio de la lista, lo elimina del principio de la lista y recorre la lista para imprimir los enlaces que contiene. Mejoras a esta aplicación incluyen lo que es una lista de doble ligado, añadiendo métodos para inserción y eliminar desde el medio o al final, y mediante la adición de obtener y ordenar métodos también.

Nota: En el ejemplo, el objeto Enlace realmente no contiene otro objeto Enlace - nextLink es en realidad sólo una referencia a otro enlace.

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 tiene una implementación LinkedList, que es posible que desee retirar. Puede descargar el JDK y sus fuentes en java.sun.com.

Answer 3

Use java.util.LinkedList. De esta manera:

list = new java.util.LinkedList() 

Answer 4

Es mucho mejor usar java.util.LinkedList, porque es probablemente mucho más optimizado, que el que se va a escribir.

Answer 5

La lista vinculada anterior muestra en dirección opuesta. Creo que la aplicación correcta del método de inserción debe ser

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; 
      } 
     } 
    } 
}