Aide à faire une liste de liens simples en Java

Question

Ceci est pour les devoirs, mais sachez que j'ai regardé en ligne pour obtenir de l'aide (comme http://www.sethi.org/classes/class_stuff/cis435/others/notes-java/data/collections/lists/simple-linked-list.html) et mon manuel mais j'ai encore quelques problèmes.

Toute aide serait appréciée ...

En ce moment je suis en train d'insérer juste valeurs, mais rien ne fonctionne. Que ce soit le premier élément, qu'il soit ajouté en dernier ou entre les deux.

Node header = null; // First element of list. 
Node back = null; // Last element of list. 

public void insert(int i, double value){ //insert value before i-th element 
    Node e = new Node(); 
    e.num = value; 
    Node curr = header; 
    for(int x=0;x<i;x++) { 
    if (i == 1) { //we want to insert as first thing 
    if (size == 0) { //its the FIRST time we add something 
    header.next = e; 
    e.next = back; 
    break; 
    } else if (size == 1){ 
    e.next = header.next; //i.e. the second thing in the list 
    header.next = e; 
    break; 
    } else { 
    e.next = header.next.next; //i.e. the second thing in the list 
    header.next = e; 
    break; 
    } 
    } 
    else if (x == (i-1)) { 
    e.next = curr.next; 
    curr.next = e; 
    break; 
    } 
    curr = curr.next; 
    } 
    size = size+1; 
} 

Je ne sais pas vraiment pourquoi cela ne fonctionne pas.

Merci!

Answer 1

Pour une raison quelconque, les personnes qui apprennent encore à programmer rendent les choses beaucoup plus compliquées qu'elles ne le devraient. Je l'ai fait quand j'apprenais le java, je le fais quand je suis en train d'entrer dans une nouvelle langue, et les étudiants que j'ai marqués trouvent des façons nouvelles et étonnantes de le faire. Vous avez plus de choses dans votre insertion alors il doit y avoir, par exemple, une méthode qui insère une valeur à un index spécifique ne devrait pas vérifier si c'est le premier élément à insérer (ne pas dire qu'il ne devrait pas vérifier les limites). Voici le pseudo code de ce que je ferais.

insert(index, value) 
    if index>size 
     throw null pointer 
    traverse to index -1 //lets call this nodeI 
    create newnode and set value 
    set newnode.next to nodeI.next 
    set nodeI.next to newnode 
    increase size. 

quelques conseils pratiques pour vous, vous devriez avoir une fonction pour obtenir un élément de la liste de liens, quelque chose qui retourne un nœud? noeud public elementAt (index int) par exemple? utilisez-le pour parcourir la liste chaînée. Si vous voulez ajouter à la liste chaînée, essayez cette

append(value) 
    insert(size-1,value) 

et si vous souhaitez insérer au début? même idée

insert(value) 
    insert(0,value) 

Answer 2

Quelques suggestions:

1. implémentent java.util.List
2. Pensez génériques
3. Lire this.

Commencez par «insérer à la fin» avant de penser à «insérer à i».

Answer 3

1. Dans la ligne e.next = header.next.next que se passerait-il si header.next pointe vers un 'null'? Est-il possible d'y arriver?
2. Quels sont les cas d'angle que vous avez à traiter et avez-vous tous pris en compte?
3. Pouvez-vous commencer par le cas le plus simple d'abord, en ajoutant soit un élément à l'avant ou un élément à l'arrière? Ensuite, utilisez ces fonctions pour implémenter l'insertion?

Answer 4

J'ai essayé un programme simple, qui sera utile pour vous les gars, je suis aussi apprendre Java, s'il vous plaît garder avec moi des erreurs, mais ce programme fonctionne très bien.

Je poste un très simple programme de liste simple lié en Java, que j'ai essayé aujourd'hui. J'espère que cela aidera tout le monde.

Liste de liens.java

class LinkList 
{ 
public static void main(String args[]) 
{ 
    Node node = new Node(1); 
    node.addAtLast(2); 
    node.addAtLast(3); 
    node.addAtLast(4); 
    node.addAtLast(5); 
    node.printList(); 
} 

} 

Node.java

class Node 
{ 
private int data; 
private Node link; 

public Node(int mydata) 
{ 
    data = mydata; 
    link = null; 
} 

public void printList() 
{ 
System.out.print("|"+data+"|"+"->"); 
if(link != null) 
{ 
//recursive call 
link.printList(); 

} 
else 
{ 
//marking end of list as NULL 
System.out.print("|NULL|"); 
} 
} 

public void addAtLast(int mydata) 
{ 
if(link == null) 
{ 

    link = new Node(mydata); 
} 
else 
{ 
    link.addAtLast(mydata); 
} 

} 

} 

SORTIE:

Le dessous est notre sortie

| 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | NULL |