Comment créer une structure de données de liste liée en Java? [fermé]

135

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

Lance Fisher
la source
33
La meilleure façon de créer une liste liée est d'utiliser la liste liée intégrée. Ne réécrivez pas les classes intégrées.
Peter Lawrey
21
cette question est légitime et très constructive pour la discussion des programmeurs
anshulkatta

Réponses:

220

La solution évidente pour les développeurs familiers avec Java est d'utiliser la classe LinkedList déjà fournie dans java.util . Supposons cependant que vous vouliez créer votre propre implémentation pour une raison quelconque. Voici un exemple rapide de liste chaînée qui insère un nouveau lien au début de la liste, supprime depuis le début de la liste et parcourt la liste pour imprimer les liens qu'elle contient. Les améliorations apportées à cette implémentation incluent la création d'une liste à double lien , l'ajout de méthodes pour insérer et supprimer à partir du milieu ou de la fin, ainsi que l'ajout de méthodes get et sort .

Remarque : Dans l'exemple, l'objet Link ne contient pas en fait 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();
    }
}
Aaron
la source
7
vous pouvez également améliorer assez facilement ce code pour utiliser des génériques pour le type de données plutôt que de stocker un int et un double.
shsteimer
51
@shsteimer: tout à fait définitivement, mais comme la seule bonne utilisation de ce code est de démontrer la technique, cela n'aiderait personne. Cela ne ferait que diffuser l'idée de base.
Joachim Sauer
8
Ce n'est pas une bonne approche OO de l'avoir public Link nextLinket de l'utiliser en dehors de la classe. Il pourrait être respectable quand Linkserait une classe interne de LinkList. C'est un autre paquet de code écrit car Java n'était qu'une autre version de c.
Bart
1
Lorsque vous insérez, votre premier élément n'obtiendra jamais un nextLink - sauf si je manque quelque chose avec des références Java
Chris S
Comment puis-je implémenter la méthode de suppression (index)?
JohnDow
55

Java a une implémentation LinkedList , que vous voudrez peut-être vérifier. Vous pouvez télécharger le JDK et ses sources sur java.sun.com .

dlinsin
la source
La Linkedlist de Java ne vous permet pas d'insérer et de supprimer des éléments à des positions arbitraires?
Seun Osewa
10
N'est-ce pas là tout l'intérêt d'une liste chaînée?
jrockway
2
@Seun Osewa si vous voulez ajouter à une position arbitraire, veuillez utiliser une ArrayList :)
headgrowe
3
Au lieu de télécharger le JDK pour voir son implémentation LinkedList, vous pouvez simplement le voir en LinkedList.javaligne ici . Cette page met même en évidence la syntaxe du code et rend les commentaires Javadoc en ligne.
Rory O'Kane
17

La liste liée ci-dessus s'affiche dans la direction opposée. Je pense que la mise en œuvre correcte de la méthode d'insertion devrait être

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;
    }
} 
Arnab Sarkar
la source
1
Ajouter nouveau à la fin, sauf indication contraire. :-)
9

Il est préférable d'utiliser java.util.LinkedList, car il est probablement beaucoup plus optimisé que celui que vous allez écrire.

Jakub Arnold
la source
15
Et cela fonctionnera la première fois.
Peter Lawrey
7
//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;
            }
        }
    }
}
Anitha A
la source