Comment mettre en œuvre une liste chaînée en Java ?

Question

Quelle est la meilleure façon de faire une liste chaînée en Java ?

Answer 1

La solution évidente pour les développeurs habitués à Java est d'utiliser la LinkedList classe déjà dans java.util. Dire, cependant, vous voulez faire votre propre mise en œuvre, pour une raison quelconque. Voici un exemple rapide d'une liste chaînée qui insère un lien au début de la liste, supprime à partir du début de la liste et parcourt la liste à imprimer les liens contenus dans. Les améliorations de cette mise en œuvre est de faire un double-liste liée, ajouter des méthodes à insérer et supprimer à partir du milieu ou de la fin, et par l'ajout d' obtenir et de tri des méthodes.

Remarque: Dans l'exemple, le Lien de l'objet ne contient pas réellement un autre Lien objet - nextLink est en fait seulement une référence à un autre lien.

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;
	    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 a une implémentation LinkedList , que vous pourriez vouloir vérifier. Vous pouvez télécharger le JDK et c’est des sources à java.sun.com.

Answer 3

Utilisez java.util.LinkedList. Comme ça :

Answer 4

La liste chaînée ci-dessus s’affichent dans la direction opposée. Je pense que la mise en œuvre correcte de la méthode insert doit être

Answer 5

Beaucoup mieux d’utiliser java.util.LinkedList, parce qu’il est optimisé sans doute beaucoup plus, que celui que vous écrirez.