ajouter et supprimer d'une liste unidirectionnelle

Question

Je pensais avoir compris cela dans ma précédente question sur les listes chaînées, mais je me suis terriblement trompé, je suis aussi perdu que lorsque j'étais posté.

Je me rends compte que techniquement, je pose deux questions, mais j'espère que l'obtention d'au moins une devrait rendre l'autre facile (en supposant qu'elles soient juste inverses).

J'ai 3 classes déjà donnés à moi, ils sont:

SLinkedList.java

package chapter3.linkedList; 

    public class SLinkedList<V> { 
     // instance variables. Add the tail reference. 
     protected Node<V> head, tail; 
     protected long size; 

     // methods, empty list constructor first 
     public SLinkedList() { 
      head = null; 
      tail = null; 
      size = 0; 
     } // end constructor of a SLinkedList 

     // method to add nodes to the list. Storage space for the node 
     // is already allocated in the calling method 
     public void addFirst (Node<V> node) { 
      // set the tail only if this is the very first node 
      if (tail == null) 
       tail = node; 
      node.setNext (head); // make next of the new node refer to the head 
      head = node;   // give head a new value 

      // change our size 
      size++; 
     } // end method addFirst 

     // addAfter - add new node after current node, checking to see if we are at the tail 
     public void addAfter (Node<V>currentNode, Node<V>newNode) { 
      if (currentNode == tail) 
       tail = newNode; 
      newNode.setNext (currentNode.getNext()); 
      currentNode.setNext (newNode); 

      // change our size 
      size++; 
     } // end method addAfter 

     // addLast - add new node after the tail node. Adapted from Code Fragment 3.15, p. 118. 
     // Mike Qualls 
     public void addLast (Node<V> node) { 
      node.setNext (null); 
      tail.setNext (node); 
      tail = node; 
      size++;  
     } // end method addLast 

     // methods to remove nodes from the list. (Unfortunately, with a single linked list 
     // there is no way to remove last. Need a previous reference to do that. (See 
     // Double Linked Lists and the code below.) 
     public Node<V> removeFirst() { 
      if (head == null) 
       System.err.println("Error: Attempt to remove from an empty list"); 

      // save the one to return 
      Node<V> temp = head; 

      // do reference manipulation 
      head = head.getNext(); 
      temp.setNext(null); 
      size--; 

      return temp; 

     } // end method removeFirst 

     // remove the node at the end of the list. tail refers to this node, but 
     // since the list is single linked, there is no way to refer to the node 
     // before the tail node. Need to traverse the list. 
     public Node<V> removeLast() { 
      // // declare local variables/objects 
      Node<V> nodeBefore; 
      Node<V> nodeToRemove; 

      // make sure we have something to remove 
      if (size == 0) 
       System.err.println("Error: Attempt to remove fron an empty list"); 

      // traverse through the list, getting a reference to the node before 
      // the trailer. Since there is no previous reference. 
      nodeBefore = getFirst(); 

      // potential error ?? See an analysis and drawing that indicates the number of iterations 
      // 9/21/10. size - 2 to account for the head and tail nodes. We want to refer to the one before the 
      // tail. 
      for (int count = 0; count < size - 2; count++) 
       nodeBefore = nodeBefore.getNext(); 

      // save the last node 
      nodeToRemove = tail; 

      // now, do the pointer manipulation 
      nodeBefore.setNext (null); 
      tail = nodeBefore; 
      size--; 

      return nodeToRemove; 

     } // end method removeLast 

     // method remove. Remove a known node from the list. No need to search or return a value. This method 
     // makes use of a 'before' reference in order to allow list manipulation. 
     public void remove (Node<V> nodeToRemove) { 
      // declare local variables/references 
      Node<V> nodeBefore, currentNode; 

      // make sure we have something to remove 
      if (size == 0) 
       System.err.println("Error: Attempt to remove fron an empty list"); 

      // starting at the beginning check for removal 
      currentNode = getFirst(); 
      if (currentNode == nodeToRemove) 
       removeFirst(); 
      currentNode = getLast(); 
      if (currentNode == nodeToRemove) 
       removeLast(); 

      // we've already check two nodes, check the rest 
      if (size - 2 > 0) { 
       nodeBefore = getFirst(); 
       currentNode = getFirst().getNext(); 
       for (int count = 0; count < size - 2; count++) { 
        if (currentNode == nodeToRemove) { 
         // remove current node 
         nodeBefore.setNext (currentNode.getNext()); 
         size--; 
         break; 
        } // end if node found 

        // change references 
        nodeBefore = currentNode; 
        currentNode = currentNode.getNext(); 
       } // end loop to process elements 
      } // end if size - 2 > 0 

     } // end method remove 

     // the gets to return the head and/or tail nodes and size of the list 
     public Node<V> getFirst() { return head; } 
     public Node<V> getLast() { return tail; } 
     public long getSize() { return size; } 

    } // end class SLinkedList 

Il y a aussi Node.java

package chapter3.linkedList; 

public class Node<V> 
{ 
    // instance variables 
    private V element; 
    private Node<V> next; 

    // methods, constructor first 
    public Node() 
    { 
     this (null, null);  // call the constructor with two args 
    } // end no argument constructor 
    public Node (V element, Node<V> next) 
    { 
     this.element = element; 
     this.next = next; 
    } // end constructor with arguments 

    // set/get methods 
    public V getElement() 
    { 
     return element; 
    } 
    public Node<V> getNext() 
    { 
     return next; 
    } 
    public void setElement (V element) 
    { 
     this.element = element; 
    } 
    public void setNext (Node<V> next) 
    { 
     this.next = next; 
    } 

} // end class Node 

et enfin GameEntry.java

package Project_1; 

public class GameEntry 
{ 
    protected String name; // name of the person earning this score 
    protected int score; // the score value 
    /** Constructor to create a game entry */ 
    public GameEntry(String name, int score) 
    { 
     this.name = name; 
     this.score = score; 
    } 
    /** Retrieves the name field */ 
    public String getName() 
    { 
     return name; 
    } 
    /** Retrieves the score field */ 
    public int getScore() 
    { 
     return score; 
    } 
    /** Returns a string representation of this entry */ 
    public String toString() 
    { 
     return name + ", " + score + "\n"; 
    } 

} 

EDIT POINT J'ai créé un pilote appelé Scores.java, en elle jusqu'à présent est tout ce que j'ai ** J'ai ajouté ce que j'ai besoin pour les classes, je suis probablement mal que:

package Project_1; 

import chapter3.linkedList.*; 

import java.util.*; 


/** Class for storing high scores in an array in non-decreasing order. */ 
public class Scores 
{ 

    //add function 
    public SLinkedList<GameEntry> add(GameEntry rank, SLinkedList<GameEntry> scores) 
    { 
     Node<GameEntry> currentNode = scores.getFirst(); 
     Node<GameEntry> nextNode = null; 
     Node<GameEntry> previousNode = null; 
     Node<GameEntry> newNode = new Node<GameEntry>(); 
     newNode.setElement(rank); 

     if(scores.getSize() == 0) 
     { 
      scores.addFirst(newNode); 
     } 
     else 
     { 
      while(currentNode != null) 
      {    
       nextNode = currentNode.getNext(); 
       if(nextNode == null) 
       { 
        scores.addLast(newNode); 
       } 
       else 
       { 
        scores.addAfter(currentNode, newNode); 
        break; 
       }    
      previousNode = currentNode; 
      currentNode = currentNode.getNext(); 
      } 
     } 
     return scores; 
    } 

    //remove function 
    public void remove(int i) 
    { 

    } 

    //print function 
    /*gameenter printing; 
printing=node.Getelement;   //pseudo code for making it work right 
print(printing.getscore) 
print(print.getname) 
*/ 
    public void print(SLinkedList<GameEntry> scores) 
    { 
     Node<GameEntry> currentNode = scores.getFirst();   
     GameEntry currentEntry = currentNode.getElement();  
     System.out.printf("["); 
     for(int i = 0; i < scores.getSize(); i++) 
     { 
       System.out.printf(", %s", currentEntry.toString()); 
       currentNode = currentNode.getNext(); 
       currentEntry = currentNode.getElement(); 
     } 
     System.out.println("]"); 
    } 
} 

J'ai mon pilote de test appelé ScoresTest.java, que j'ai à peu près rempli:

package Project_1;

import chapter3.linkedList.SLinkedList;

public class ScoresTest { 
    /** 
    * @param args 
    */ 

    public static void main(String[] args) 
    { 
     SLinkedList<GameEntry> highScores = new SLinkedList<GameEntry>(); //Linked List for Game Entry 
     GameEntry entry; 
     Scores rank = new Scores();  
     entry = new GameEntry("Flanders", 681);  
     highScores = rank.add(entry, highScores); 
     entry = new GameEntry("Krusty", 324); 
     highScores = rank.add(entry, highScores); 
     entry = new GameEntry("Otto", 438); 
     highScores = rank.add(entry, highScores); 
     entry = new GameEntry("Bart", 875); 
     highScores = rank.add(entry, highScores); 
     entry = new GameEntry("Homer", 12); 
     highScores = rank.add(entry, highScores); 
     entry = new GameEntry("Lisa", 506); 
     highScores = rank.add(entry, highScores); 
     entry = new GameEntry("Maggie", 980); 
     highScores = rank.add(entry, highScores); 
     entry = new GameEntry("Apoo", 648); 
     highScores = rank.add(entry, highScores); 
     entry = new GameEntry("Smithers", 150); 
     highScores = rank.add(entry, highScores); 
     entry = new GameEntry("Burns", 152); 
     highScores = rank.add(entry, highScores); 
     System.out.println("The Original High Scores"); 
     rank.print(highScores); 

     entry = new GameEntry("Moe", 895); 
     highScores = rank.add(entry, highScores); 
     System.out.println("Scores after adding Moe"); 
     rank.print(highScores); 

     //highScores = rank.remove(4); 
     System.out.println("Scores after removing Apoo"); 
     rank.print(highScores); 
    } 
} 

Tout est terminé, à peu près certain que je n'ai plus rien à ajouter.

Je ne cherche pas quelqu'un pour répondre pour moi, mais je n'ai aucune idée par où commencer ou comment faire la fonction d'ajout ou de suppression, de quelque façon que ce soit. Ceci est un cours intermédiaire, le livre ne fait rien pour expliquer les listes liées (allez-y et cherchez vous-même si vous ne me croyez pas, le texte s'appelle Datastructures et Algorithmes en Java, 5ème édition). Il montre comment le faire avec un tableau assez facilement ... ce qui fonctionne parfaitement pour une liste chaînée, mais apparemment le professeur ne veut pas que nous le fassions de cette façon, donc malheureusement je suis maintenant complètement perdu sur la façon de le faire. J'ai essayé de regarder les réponses d'autres personnes ici et google, et jusqu'à présent, rien n'a cliqué ou n'a eu aucun sens, je ne peux pas comprendre comment cela fonctionne, et l'explication et l'exemple de l'enseignant étaient seulement pour dessiner des boîtes sur le tableau, je n'ai jamais vu de tri, d'ajout ou de suppression de fonction codée pour une liste chaînée ... je ne peux pas savoir ce qu'on ne m'a pas enseigné ou que je ne peux pas localiser.

Toute aide est grandement appréciée, et merci d'avance!

EDIT

Je regardais les import java.util. *; et les commandes à l'intérieur de celui-ci pour les listes liées, elles semblent douloureusement faciles. pour supprimer je voudrais juste utiliser list.sublist (i, i) .clear(); et la valeur que je souhaite supprimer est supprimée, super facile, il semble juste essayer d'utiliser le slinkedlist.java et le node.java, je n'arrive juste pas à les suivre de quelque manière que ce soit. Je crois que le professeur les a effectivement écrites, et j'ai essayé de lui demander de l'aide, je suis resté 2 heures après la classe à essayer de comprendre quelque chose, et comme vous pouvez le voir, cela n'a pas beaucoup aidé. Merci encore pour l'aide!

EDIT

Je présente également mes excuses si cela semble qu'elle est vague, mais je ne dispose pas d'un point précis où ma confusion semble liée, je comprends les listes chaînées si nous parlons de la java. util.linkedList ;, mais en ce qui concerne l'utilisation de ce qui m'a été donné dans cette circonstance, je ne peux pas suivre la logique du tout, me laissant tout à fait perdu et incertain de l'endroit où commencer.

Answer 1

En pseudo-code (s'il vous plaît noter que je ne suis pas, y compris lié vérification etc, simplement la logique)

Pour ajouter un nœud à l'avant de la liste:

newNode->nextNode = startNode 
startNode = newNode 

Pour ajouter à un particulier indice

index = 0 
currentNode = startNode 

// find the node in the list. here you will need to do all kinds of bound checking 
while index is less than position 
    currentNode = currentNode.nextNode // move your node pointer to the position 
    increment index 

// so here we basically insert the new node into the list. what needs to happen is 
// to NOT break the list by forgetting the node after the current node. this is why 
// we first set the new nodes' next one, to the current nodes' (the one already in 
// the list) next node. this way, we still have all the information we need. then, 
// when we set the current nodes' next node to the new node, we essentially "break" 
// the link and "repair" it by adding the new link. 

newNode.nextNode = currentNode.nextNode // some more bound checking required 
currentNode.nextNode = newNode 

Pour retirer d'un index spécifique:

index = 0 
delNode = startNode 

// find the node in the list. here you will need to do all kinds of bound checking 
while index is less than (position - 1) 
    delNode = delNode.nextNode // move your node pointer to the position 
    increment index 

delNode.nextNode = delNode.nextNode.nextNode 

// that's it. by setting the node's (before the one you whish to delete) 
// next node to the node AFTER the one you want to delete, you basically 
// "skip" over that node. since it is no longer referenced, the garbage 
// collector will take care of the rest. if you wish to return that node 
// you can do it quite easily by remembering it. 

storeNode = delNode.nextNode     // some more bound checking required 
delNode.nextNode = delNode.nextNode.nextNode // some more bound checking required 

// now you still have a reference to the deleted node in storeNode 

---

MISE À JOUR

OK, donc si je comprends bien, vous devez créer une liste chaînée qui stocke les scores dans un ordre croissant. Autant que je peux voir, la liste entière liée a été mise en application pour vous, vous devez simplement utiliser les classes fournies, et ajouter la logique dans Scores.java pour garder la liste triée.

Tout d'abord, je vois que vos nœuds ne sont pas comparables. Si vous êtes autorisé à changer la source qui vous est donnée, je vous suggère de les implémenter Comparable<Node> et de surcharger le equals(Object o) pour que vous ayez la logique de les comparer. Deux nœuds peuvent contenir le même élément, mais cela ne signifie pas qu'ils sont égaux.

Veuillez noter la modification des signatures de méthode!

//add function 
public void add(Node<GameEntry> score) { 
    // adding is where you now want to keep everything sorted. so I highly 
    // recommend that you implement `Comparable` as I mentioned above. if not, 
    // you have to put the logic in here. 

    Node<GameEntry> currentNode = highScored.getFirst(); 
    Node<GameEntry> prevNode = null; 

    // if the list is empty, or the new node must go in before the head, 
    // simply add it as the head. 
    if (highScores.size() == 0 || score.compareTo(currentNode) < 0) { 
     highScores.addFirst(score); 
    } 

    // search for the position of the new node. while the node has a higher score 
    // than the current node, we need to continue on so we can place it in the 
    // correct place. 
    while (currentNode != null && currentNode.compareTo(score) > 0) { 
     prevNode = currentNode; 
     currentNode = currentNode.getNext(); 
    } 

    // if the currentNode is null, it means it is the highest score, so 
    // we can simply add it to the end 
    if (currentNode == null) { 
     highScores.addLast(score); 
    } else { 
     // otherwise just add it after the correct node 
     highScores.addAfter(prevNode, score); 
    } 
} 


//remove function 
public void remove(Node<GameEntry> score) { 
    // removing an element should be as described above. if you keep 
    // your list sorted during the ADD method, removing any element 
    // should not break the order. 

    // find the element - removal from a linked list is O(n), 
    // since we need to know what the element BEFORE the one 
    // is that you want to remove. assuming you have implemented 
    // the equals method to check equality of nodes: 

    Node<GameEntry> currentNode = highScores.getFirst(); 
    Node<GameEntry> prevNode = null; 
    while (currentNode != null && !currentNode.equals(score)) { 
     prevNode = currentNode; 
     currentNode = currentNode.getNext(); 
    } 

    // if currentNode is null, the node we wanted to remove was not 
    // in the list. 
    if (currentNode == null) { 
     System.out.println("Node not found"); 
     return; 
    } 

    // now, we need to check if there is a node after the one we want 
    // to remove. 
    if (prevNode.getNext().getNext() != null) { 
     // if there is, we follow the logic from the pseudo code 
     prevNode.setNext(prev.getNext().getNext()); 
    } else { 
     // if not, we only need to remove the last entry (since the 
     // one we want to remove is the last one) 
     highScores.removeLast(); 
    } 
} 

IMPORTANT

S'il vous plaît vérifier que la logique ici. Je l'ai fait très rapidement sans IDE car je ne suis pas sur mon ordinateur de développement pour le moment. Si quelqu'un trouve des problèmes, s'il vous plaît laissez un commentaire et je vais le réparer.

Si ce n'est pas exactement ce que vous avez demandé (votre question est un peu vague), faites le moi savoir.

---

MISE A JOUR 2

Lire sur Comparator s here, here et here.