¿Cómo creo una estructura de datos de lista enlazada en Java?[cerrado]
-
08-06-2019 - |
Pregunta
¿Cuál es la mejor manera de hacer una lista vinculada en Java?
Solución
La solución obvia para los desarrolladores familiarizados con Java es utilizar el Lista enlazada clase ya proporcionada en java.util.Sin embargo, supongamos que desea realizar su propia implementación por algún motivo.A continuación se muestra un ejemplo rápido de una lista vinculada que inserta un nuevo vínculo al principio de la lista, lo elimina desde el principio y recorre la lista para imprimir los vínculos que contiene. Mejoras a esta implementación incluyen convertirlo en un lista doblemente enlazada, agregando métodos a insertar y borrar desde el medio o el final, y añadiendo conseguir y clasificar métodos también.
Nota:En el ejemplo, el objeto Link en realidad no contiene otro objeto Link. siguienteEnlace En realidad, es solo 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();
}
}
Otros consejos
Java tiene un Lista enlazada implementación, que tal vez quieras revisar.Puede descargar el JDK y sus fuentes en java.sun.com.
Usar java.util.ListaEnlazada.Como esto:
list = new java.util.LinkedList()
La lista enlazada de arriba se muestra en dirección opuesta.Creo que la implementación correcta del método de inserción debería 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;
}
}
Es mucho mejor usar java.util.LinkedList, porque probablemente esté mucho más optimizado que el que escribirás.
//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;
}
}
}
}