Удалить все вхождения товара из связанного списка

Question

Я работаю над этим заданием лаборатории в течение нескольких часов и не могу понять, почему этот код не работает. Вопрос заключается в том, чтобы добавить метод int removeEvery(T item), который удаляет все вхождения элемента и возвращает количество удаленных элементов в класс списка ссылок, который реализует интерфейс списка ссылок.

Это мой код: Он удаляет некоторые вхождения элемента, но не все из них.

public int removeEvery(T item){ 
int index = 0; 
Node currentNode = firstNode; 
for(int i = 1; i <= numberOfEntries; i++) 
    { 
    System.out.println(currentNode.getData()); 
     if (item.equals(currentNode.getData())){ 
      index++; 
      remove(i);} 
     else{ 
      currentNode = currentNode.getNextNode();} 
    } 
     if(index != 0) 
     return index; 
    return -1; 
} 

Вот метод удалить, который был включен в класс LinkList:

public T remove(int givenPosition) 
{ 
    T result = null;     // return value 

    if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) 
    { 
    assert !isEmpty(); 
    if (givenPosition == 1)  // case 1: remove first entry 
    { 
     result = firstNode.getData();  // save entry to be removed 
     firstNode = firstNode.getNextNode(); 
     if (numberOfEntries == 1) 
      lastNode = null; // solitary entry was removed 
     } 
     else       // case 2: givenPosition > 1 
     { 
      Node nodeBefore = getNodeAt(givenPosition - 1); 
      Node nodeToRemove = nodeBefore.getNextNode(); 
      Node nodeAfter = nodeToRemove.getNextNode(); 
      nodeBefore.setNextNode(nodeAfter); // disconnect the node to be removed 
      result = nodeToRemove.getData(); // save entry to be removed 

      if (givenPosition == numberOfEntries) 
       lastNode = nodeBefore; // last node was removed 
    } // end if 

    numberOfEntries--; 
    } // end if 

    return result;     // return removed entry, or 
            // null if operation fails 
} // end remove 

Answer 1

В вашем связанном списке есть что-то особенное, вы можете получить доступ к следующему элементу с current.getNextNode, но вы удаляете его с помощью индекса элемента. Вы должны посмотреть в остальной части своей реализации, как управлять этим индексом. Первый элемент имеет индекс 0 или 1 (вы начинаете свой цикл с 1). Что происходит с индексами всех элементов при его удалении. Знают ли элементы свой индекс?

Вы можете использовать что-то вроде

int deletedNodes = 0; 
    int currentIndex = 0; // check if 1 or 0 
    currentNode = fist; 
    while(currentNode != null){ // I guess lastNode.getNextNode() is null 
    if(//should remove){ 
     remove(currentIndex); 
     deletedNodes++ 
     // probably no need to change the index as all element should have been shifted back one index 
    } else { 
     currentIndex++; // index changes only if no node was deleted 
    } 
    currentNode = currentNode.getNextNode(); // will work even if it was deleted 
    } 
return deletedNodes; 

Answer 2

Я думаю, что проблема у вас есть происходит от remove(i).

При удалении элемента i-th элемент i+1-th становится i-th и т. Д.: Каждый элемент сдвинут. Поэтому, если вам нужно удалить 2 элемента в вашем списке, которые указаны в индексе j и j+1, удаление элемента j-th с вызовом remove(j) приведет к смещению элемента по индексу j. Следовательно, удаление этого второго элемента требует вызова remove(j), а не remove(j+1).

Таким образом, вам необходимо уменьшить i после удаления.

Поскольку ваш метод remove фактически уменьшает numberOfEntries, условие на вашем while циклах правильно обновляется. Так что все, что вам нужно сделать, это заменить

if (item.equals(currentNode.getData())) { 
    index++; 
    remove(i); 
} 
else { 
    currentNode = currentNode.getNextNode(); 
} 

по

if (item.equals(currentNode.getData())) { 
    index++; 
    remove(i--); 
} 
// update the current node, whether removing it or not 
currentNode = currentNode.getNextNode(); 

---

Iterator.remove()

Эта проблема, которую вы описываете, показывает полезность Iterator.remove() при использовании данных структуры из JDK для прохождения итерируемой коллекции и удаления элементов при прохождении через нее.

Answer 3

После удаления узла, как это было предложено @Vakimshaar, необходимо уменьшать i, потому что узел в этом индексе был удален и есть новый узел в то же индекс. В дополнение к этому вам также необходимо обновить ссылку currentNode, поскольку она все равно будет указывать на удаленный вами узел, но он должен действительно указывать на новый узел, который переместился в этот индекс.

Таким образом, в if (item.equals(currentNode.getData())){ блоке вам нужно сделать следующее:

Node nextNode = currentNode.getNextNode(); 
index++; 
remove(i--); 
currentNode = nextNode; 

С этим, ваш код должен правильно удалить все вхождения.

Answer 4

Вот кода Java, чтобы удалить все вхождения элемента из связанного списка:

public class LinkedList{ 
    Node head; 
    class Node{ 
     int data; 
     Node next; 
     Node(int d){data =d; next = null;} 
    } 

    public void push(int new_data){ 
     Node new_node = new Node(new_data); 
     new_node.next = head; 
     head = new_node; 
    } 

    public void insertAfter(Node givenNode, int new_data){ 
     if(givenNode == null) 
      System.out.println("Given node cannot be empty"); 

     Node new_node = new Node(new_data); 
     new_node.next = givenNode.next; 
     givenNode.next = new_node; 
    } 

    public void append(int new_data){ 
     Node new_node = new Node(new_data); 
     if(head == null) 
      head = new_node; 

     else{ 
     Node last = head; 

     while(last.next != null) 
      last = last.next; 

     last.next = new_node; 
    } 
    } 

    public void printList(){ 
     Node temp = head; 

     while(temp != null){ 
      System.out.println(temp.data + " "); 
      temp = temp.next; 
     } 
    } 

    void deleteNode(int key){ 
     // Store head node 
     Node temp = head, prev=null; 
     // If head node itself holds the key or multiple occurrences of key 
     while(temp != null && temp.data == key){ 
      head = temp.next; 
      temp = head; 
     } 
     // Delete occurrences other than head 
     while(temp != null){ 
      // Search for the key to be deleted, keep track of the 
      // previous node as we need to change 'prev.next' 
      while(temp != null && temp.data != key){ 
       prev = temp; 
       temp = temp.next; 
      } 
      // If key was not present in linked list 
      if(temp == null) return; 
      // Unlink the node from linked list 
      prev.next = temp.next; 
      //Update Temp for next iteration of outer loop 
      temp = prev.next; 
     } 
    } 

    public static void main(String[] args){ 
     LinkedList llist = new LinkedList(); 

     llist.push(6); 
     llist.append(7); 
     llist.append(7); 
     llist.append(7); 
     llist.append(9); 
     llist.push(10); 
     llist.deleteNode(7); 
     llist.printList(); 
    } 
} 

Выход: