Comment créer une structure de données de type liste chaînée en Java ?

La solution évidente pour les développeurs familiers de Java est d'utiliser la classe LinkedList déjà fournie dans java.util. Supposons toutefois que vous souhaitiez créer votre propre implémentation pour une raison quelconque. Voici un exemple rapide d'une liste liée qui insère un nouveau lien au début de la liste, supprime à partir du début de la liste et boucle à travers la liste pour imprimer les liens qu'elle contient. Les améliorations de cette implémentation consistent à en faire une liste doublement liée, à ajouter des méthodes pour insérer et supprimer à partir du milieu ou de la fin, et à ajouter également des méthodes get et sort.

Note : Dans l'exemple, l'objet Link ne contient pas réellement un autre objet Link - nextLink n'est en fait qu'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;
        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();
    }
}