Como faço para criar uma estrutura de dados de linked list em Java?

Qual é a melhor maneira de fazer uma linked list em Java?

A solução óbvia para desenvolvedores familiarizados com o Java é usar a class LinkedList já fornecida em java.util . Digamos, no entanto, que você quisesse fazer sua própria implementação por algum motivo. Aqui está um exemplo rápido de uma lista encadeada que insere um novo link no início da lista, exclui do início da lista e percorre a lista para imprimir os links contidos nela. Os aprimoramentos para essa implementação incluem torná-la uma lista com links duplos , adicionar methods para inserir e excluir do meio ou fim e adicionando também methods get e sort .

Nota : No exemplo, o object Link na verdade não contém outro object Link – nextLink é, na verdade, apenas uma referência a outro link.

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

Java tem uma implementação de LinkedList , que você pode querer verificar. Você pode baixar o JDK e suas fonts em java.sun.com .

Use java.util.LinkedList . Como isso:

 list = new java.util.LinkedList() 

A lista ligada acima é exibida na direção oposta. Eu acho que a implementação correta do método de inserção deve 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; } } 

É muito melhor usar o java.util.LinkedList, porque é provavelmente muito mais otimizado do que o que você irá escrever.

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