4
votes

Comment supprimer une valeur spécifique d'une liste liée en Java?

Comment supprimer une valeur spécifique d'une liste liée java?
J'ai essayé de le faire dans mon implémentation, mais ce n'était pas facile.

Voici ce que j'essaye de faire:

         
 a b c a b d b abba a z a 
 Remove some of elements.
 a b d b abba a z a

Ce sont les pré- setup:

 public static void main(String[] args) {
    LinkedQueue<String> q = new LinkedQueue<String>();

    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("c");
    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("d");
    q.enqueue("b");
    q.enqueue("abba");
    q.enqueue("a");
    q.enqueue("z");
    q.enqueue("a");
    System.out.println(q);
    System.out.println("Remove some of elements.");

    q.remove("a");
    q.remove("f");
    q.remove("c");
    System.out.println(q);
   }
  }

Et la fonction principale:

 public class LinkedQueue<Item> implements Iterable<Item> {
   private int N;         // number of elements on queue
   private Node first;    // beginning of queue
   private Node last;     // end of queue

  // helper linked list class
 private class Node {
    private Item item;
    private Node next;
}

/**
 * Initializes an empty queue.
 */
public LinkedQueue() {
    first = null;
    last  = null;
    N = 0;
    assert check();
}

  public Item dequeue() {
      if (isEmpty()) throw new NoSuchElementException("Queue 
    underflow");
    Item item = first.item;
    first = first.next;
    N--;
    if (isEmpty()) last = null;   // to avoid loitering
    assert check();
    return item;
   }

Et j'ai un résultat comme celui-ci. Cela ne change pas du tout ..

//How to do this...;<..
int remove(Item item) {
    Node cur = first.next;
    Node prev = first;
    while (cur !=null) {
        if (cur.item.equals(item)) {
            item = dequeue();
        }
        cur = cur.next;

        // TODO 
    }


return 0;

}

Il efface uniquement la valeur c . Je ne sais pas pourquoi.

java algorithm linked-list

0 commentaires

4 Réponses :

0
votes

Dans votre instruction if, vous vérifiez si le cur Node est égal à Item passé: if (cur. est égal à (élément)) .

Je pense que vous devriez vérifier si l ' Item stocké dans le cur Node est égal à l' Item passé dans votre fonction: if (cur.item.equals (item)) .

2 commentaires

prev.next = cur.next; ne me semble pas non plus avoir beaucoup de sens. prev est toujours le dernier dans la boucle while

J'ai changé le problème.

1
votes

En ce qui concerne les détails de la question, je suppose que vous êtes assez nouveau en Java. Ce que vous demandez et les détails que vous montrez sont totalement différents.

LinkedQueue q = new LinkedQueue (); n'est applicable que si LinkedQueue est une classe genre et non un impl spécifique pour la classe de type Item. c'est-à-dire que vous ne créez pas d'objet de la classe LinkedQueue . LinkedQueue et LinkedQueue est différent.
cur.equals (item) manque de connaissance du contrat égal et différence de == vs égal . c'est-à-dire que vous comparez deux objets totalement différents. L'un est un Node et l'autre est un objet de classe Item.

Suggestion: notions de base claires, lire le livre de cathy Sierra.Scjp Sun Certified Programmer pour Java 6

En ce qui concerne la réponse, vous n'appelez littéralement pas remove from main (testez-le via un print instruction dans la méthode remove). C'est pourquoi vous obtenez toujours la même réponse.

Remarque: vous ne pouvez vraiment pas digérer la vraie solution même si nous le disons.

0 commentaires

1
votes

L'extrait de code suivant contient diverses méthodes remove () , tirées de l'une de mes implémentations LinkedList , écrites en Java .

Code

LinkedList.java (partly)

Steps:
* loop to target node,
    * for each step,
        record:
        * previous node,
        * this node,
* get next node, of target node,
* get value of target node,
    as return value later,
* if target is end,
    * if also head,
        head = null;
    * if not head,
        preNode.next = null;
    * end = preNode;
* if targe is not end,
    replace it with its next node,
    logic:
    * node.value = nextNode.value;
    * node.next = nextNode.next;
* return previously tracked value of target node,

LinkedListTest. java (en partie)
(test unitaire, via TestNG)

import org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;

/**
 * LinkedList test.
 *
 * @author eric
 * @date 1/28/19 6:03 PM
 */
public class LinkedListTest {
    private int n = 10;
    private LinkedList<Integer> llist; // linked list,
    private LinkedList<Integer> dupEvenLlist; // linked list, with duplicated even values,

    @BeforeMethod
    public void init() {
        // init llist,
        llist = new LinkedList(); // create linked list,
        Assert.assertTrue(llist.isEmpty());
        LinkedList.appendRangeNum(llist, 0, n); // append range,

        // init dupEvenLlist,
        dupEvenLlist = new LinkedList(); // create linked list,
        LinkedList.appendRangeNum(dupEvenLlist, 0, n); // append range,
        LinkedList.appendRangeNum(dupEvenLlist, 0, n, 2); // append range, again, with step as 2 (only even numbers),
        Assert.assertEquals(dupEvenLlist.size(), n + n / 2);
    }

    // non-remove related test cases ... are deleted,

    // remove(k) - remove by index,
    @Test
    public void testRemoveByIndex() {
        for (int i = 0; i < n; i++) {
            Assert.assertEquals(llist.removeEnd().intValue(), n - 1 - i); // remove by end, in turn it remove by index,
            Assert.assertEquals(llist.size(), n - 1 - i);
        }
        Assert.assertTrue(llist.isEmpty());
    }

    // remove(v) - remove by value,
    @Test
    public void testRemoveByValue() {
        Assert.assertFalse(llist.removeValue(n)); // not exists,

        for (int i = n - 1; i >= 0; i--) {
            Assert.assertTrue(llist.removeValue(i)); // remove by value,
            Assert.assertEquals(llist.size(), i);
        }
        Assert.assertTrue(llist.isEmpty());

        Assert.assertFalse(llist.removeValue(0)); // empty,

        // remove from list with duplicated value,
        for (int i = 0; i < n; i++) {
            Assert.assertTrue(dupEvenLlist.removeValue(i));
        }
        Assert.assertFalse(dupEvenLlist.isEmpty());
        Assert.assertEquals(dupEvenLlist.size(), n / 2);
    }

    // removeAll(v) - remove all occurrences by value,
    @Test
    public void testRemoveAllByValue() {
        Assert.assertEquals(dupEvenLlist.removeAllValue(n), 0); // not exists,

        int remainSize = dupEvenLlist.size();
        for (int i = 0; i < n; i++) {
            int rc = dupEvenLlist.removeAllValue(i); // remove all by value,
            Assert.assertEquals(rc, i % 2 == 0 ? 2 : 1);
            remainSize -= rc;
            Assert.assertEquals(dupEvenLlist.size(), remainSize);
        }
        Assert.assertTrue(dupEvenLlist.isEmpty());

        Assert.assertEquals(dupEvenLlist.removeAllValue(0), 0); // empty,
    }
}

Tous les cas de test réussiraient.

Explication

Méthodes:

T remove (int k) , supprimer par index.

private int size; // node count,
private LinkedListNode<T> head; // first node,
private LinkedListNode<T> end; // last node,

/**
 * Remove by index.
 *
 * @param k index, start from 0,
 * @return value of removed node, or null if not removed,
 */
@Override
public T remove(int k) {
    checkElementIndex(k);

    // find target node, and remember previous node,
    LinkedListNode<T> preNode = null;
    LinkedListNode<T> node = head;
    while (k-- > 0) {
        preNode = node;
        node = node.next;
    }

    T result = (T) node.value; // keep return value,

    removeNode(node, preNode); // remove

    return result;
}

/**
 * Remove by value, only remove the first occurrence, if any.
 *
 * @param v
 * @return whether removed,
 */
@Override
public boolean removeValue(T v) {
    // find target node, and remember previous node,
    LinkedListNode<T> preNode = null;
    LinkedListNode<T> node = head;
    while (true) {
        if (node == null) return false;// not found,
        if (node.getValue().compareTo(v) == 0) break; // value found,

        preNode = node;
        node = node.next;
    }

    removeNode(node, preNode); // remove

    return true;
}

/**
 * Remove by value, remove all occurrences.
 *
 * @param v
 * @return count of nodes removed,
 */
@Override
public int removeAllValue(T v) {
    int rc = 0;

    // find target node, and remember previous node,
    LinkedListNode<T> preNode = null;
    LinkedListNode<T> node = head;
    while (true) {
        if (node == null) return rc; // reach end,
        if (node.getValue().compareTo(v) == 0) { // value found,
            rc++;
            if (removeNode(node, preNode)) break; // remove, break if it's end,
            continue; // recheck this node, since it become the next node,
        }

        preNode = node;
        node = node.next;
    }

    return rc;
}

/**
 * Remove given node, which guarantee to exists. Also reduce the size by 1.
 *
 * @param node    node to delete,
 * @param preNode previous node, could be null,
 * @return indicate whether removed node is end,
 */
protected boolean removeNode(LinkedListNode node, LinkedListNode preNode) {
    LinkedListNode nextNode = node.next; // next node,
    boolean isEnd = (nextNode == null);
    if (isEnd) { // target is end,
        if (preNode == null) { // target is also head,
            head = null;
        } else { // target is not head, thus preNode is not null,
            preNode.next = null;
        }
        end = preNode;

    } else { // target is not end,
        // replace target with next node,
        node.next = nextNode.next;
        node.value = nextNode.value;
    }

    size--; // reduce size by 1,

    return isEnd;
}

/**
 * Remove head node,
 *
 * @return
 */
@Override
public T removeHead() {
    return remove(0);
}

/**
 * Remove end node,
 *
 * @return
 */
@Override
public T removeEnd() {
    return remove(size - 1);
}

boolean removeValue (T v) , supprimer par valeur, supprimer uniquement la première occurrence, le cas échéant.
La logique est similaire à celle de la suppression par index.
Les différences sont:
- Lors de la recherche initiale, comparez l'élément au lieu de la boucle à l'index, pour trouver la cible.
- Renvoie une valeur booléenne indiquant si la valeur est supprimée au lieu de la valeur supprimée
int removeAllValue (T v) , tout supprimer par valeur, supprimer toutes les occurrences.
Ceci est similaire à supprimer par valeur.

Différences:
- [ inside while () ]
- Il recherchera toutes les occurrences jusqu'à la fin.
- Après avoir supprimé une occurrence, il "continue" pour revérifier le nœud actuel. Parce que le nœud actuel a été remplacé par le prochain.
- Si le nœud supprimé est terminé, retournez-le.
  Ce relais sur la valeur de retour de removeNode () .
- Il enregistre le nombre d'occurrences supprimées.
- [ valeur de retour ]
- Il renvoie le nombre d'occurrences supprimées, au lieu d'un booléen.
booléen removeNode (nœud LinkedListNode, LinkedListNode preNode) , supprimer par nœud, avec preNode donné.
Supprimez le nœud donné, dont l'existence est garantie, avec le nœud précédent donné, qui peut être nul.
La valeur de retour indique si le nœud supprimé est end, il est principalement utilisé pour prendre en charge removeAllValue().
T removeHead () , T removeEnd () , supprimez head / end.
Appelle simplement remove by index, avec l'index correspondant 0 et la size - 1 passés.

LinkedList représente la liste liée, avec les champs size , head , end et le type générique T (pour le type de valeur dans le nœud), ce n'est pas thread-safe.
checkElementIndex () , vérifie l'index donné et lance une exception si hors de portée.
LinkedListNode , représente le nœud dans la liste liée. avec les champs valeur , suivant .

Complexité

Supprimer un seul: O(k)
Tout supprimer par valeur: O(n)

Où:

k , est l'index de la cible.
n , est la taille de la liste liée.

0 commentaires

1
votes

Depuis Java 8, il existe la méthode removeIf (Predicate super E> filter) dans laquelle vous pouvez mettre votre propre condition.

list.removeIf(cur -> cur.item.equals(item));

0 commentaires