Удалите второе появление определенного объекта в одиночном списке

Question

Я пытаюсь удалить второе появление определенного объекта в одиночном списке.

У меня этот код для моего узла:

public class Node { 
    Node next; 

    Object data; 

    public Node(Object _data) 
    { 
     next = null; 
     data = _data; 
    } 

    public Node(Object _data, Node _next) 
    { 
     next = _next; 
     data = _data; 
    } 

    public Object getData() 
    { 
     return data; 
    } 

    public void setData(Object _data) 
    { 
     data = _data; 
    } 

    public Node getNext() 
    { 
     return next; 
    } 

    public void setNext(Node _next) 
    { 
     next = _next; 
    } 
} 

И это моя функция для удаления:

public void removeSecondAppear(Object data) 
{ 
    Node temp = new Node(data); 
    Node current = head; 

    boolean found = false; 

    for(int i = 1; i < size(); i++) 
    { 
     current = current.getNext(); 

     if(current.getData().equals(temp.getData())) 
     { 
      if(found == true) 
      { 
       // remove element 
       current.setNext(current.getNext().getNext()); 
       listCount--; 
       break; 
      } 
      else if(found == false) 
      { 
       found = true; 
      } 

     } 
    } 

} 

По какой-то причине он не удалит элемент. Метод найти его отлично работает, но я не знаю, почему он не удалит элемент. У меня есть аналогичные функции, чтобы удалить элемент определенного индекса, который работает отлично:

public boolean remove(int index) 
{ 
    if(index < 1 || index > size()) 
    { 
     return false; 
    } 

    Node current = head; 

    for(int i = 1; i < index; i++) 
    { 
     if(current.getNext() == null) 
     { 
      return false; 
     } 
     current = current.getNext(); 
    } 

    current.setNext(current.getNext().getNext()); 

    listCount--; 

    return true; 
} 

Я использую тот же methood, но он не будет работать в моем методе, чтобы удалить второй вид. Любая помощь, что я делаю wron ??

public int indexOf(Object data) 
{ 
    Node temp = new Node(data); 
    Node current = head.getNext(); 

    for(int i = 0; i < size(); i++) 
    { 
     if(current.getData().equals(temp.getData())) 
     { 
      return i; 
     } 
     current = current.getNext(); 
    } 

    return -1; 
} 

Моя реализация:

LinkedList LL = new LinkedList(); 

LL.add(1); 
LL.add(2); 
LL.add(3); 
LL.add(4); 
LL.add(4); 
LL.add(5); 
LL.removeSecondAppear("4"); 

Мой метод дополню:

public void add(Object data) 
{ 
    Node temp = new Node(data); 
    Node current = head; 

    while(current.getNext() != null) 
    { 
     current = current.getNext(); 
    } 

    current.setNext(temp); 

    listCount++; 
} 

Мой конструктор:

public LinkedList() 
{ 
    head = new Node(null); 
    listCount = 0; 
} 

Answer 1

Ваш вопрос будет найден здесь (в паре мест):

По мере прохождения цикла вы продолжаете продвигаться current, пока не найдете два экземпляра, где данные равны, а затем удалите их. Ваш remove не будет работать, потому что вы на самом деле не удаляете нужный узел, это следующий узел, который вы удаляете, что не обязательно будет равным, потому что вы уже переименовали этот список и потеряли предыдущий равный узел.

current = current.getNext(); 

if(current.getData().equals(temp.getData())) 
{ 
    if(found == true) 
    { 
     // remove element 
     current.setNext(current.getNext().getNext()); // this isn't actually removing 'current'... 
     listCount--; 
     break; 
    } 
    else if(found == false) 
    { 
     found = true; 
    } 

} 

Во-первых, вы не сбрасываете найденные данные после того, как не нашли равный узел. После if (equals) блока, добавьте:

else { 
    found = false; 
} 

Предполагая, что вы исправить это, вот где вы в конечном итоге. Возьмем следующий пример:

[3] -> [4] -> [4] -> [5] -> [6] 

В вашем алгоритме вы будете перебирать каждого элемента в этом списке, как так:

Pass 1:

found = false 
[3] -> [4] -> [4] -> [5] -> [6] 
^ 
current 
found = false 

Pass 2:

found = false 
[3] -> [4] -> [4] -> [5] -> [6] 
     ^
     current 
     found = true 

Пасс 3:

found = true 
[3] -> [4] -> [4] -> [5] -> [6] 
      ^
       current 

Когда вы здесь, вы настраиваете current.next к current.next.next, который эффективно извлекая [5] из списка, а не 4. (следовательно, это также вызывает ваш NPE ...рассмотрите эффекты, когда вы дойдете до конца списка, и нет next.next)

Что вы хотите сделать, это либо найти индекс вашего дублирующего узла, либо вызвать существующий метод для удаления элемента по индексу, или держите узел previous, чтобы удерживать значение узла, который приходит доcurrent, и когда вы удаляете, установите previous.setNext(current.getNext()), который эффективно удалит current.

Во-вторых, вы сделали использование метода equals для Object, который использует самые взыскательные метод определения равенства, в том, что он будет возвращать только true для случаев, когда два сравниваемых объектов относятся к одному объекту. Хотя это не обязательно проблема, это может привести к проблемам, зависящим от типа данных, которые вы храните. Вызов equals по любому объекту по умолчанию будет соответствовать самой близкой реализации equals для фактического типа данных, представляемых этим объектом, поэтому, если он не может найти его, он будет по умолчанию реализован в Object s, что почти всегда даст ложный результат если объекты не совпадают.

Метод equals для класса Object реализует наиболее различающееся возможное отношение эквивалентности объектов; то есть для любых ненулевых опорных значений x и y, этот метод возвращает true тогда и только тогда, когда x и y относятся к одному и тому же объекту (x == y имеет значение true).

Запрет на то, что вы можете изменить способ сравнения данных объекта, но я не думаю, что это действительно вызовет у вас слишком большую проблему.

И, наконец, вы, вероятно, захотите сделать несколько ошибок и немного исправить свой алгоритм цикла, так как у этого будут проблемы, если дубликаты во главе списка, но это должно заставить вас указывать в правильном направлении ,

Вот разрез на метод, который может помочь пролить свет на то, что я сказал:

public void removeSecondAppear(Object data) 
{ 
    Node temp = new Node(data); 
    Node current = head; 
    Node previous = null; 

    boolean found = false; 

    while(current != null) 
    { 

     // for the sake of argument, let's say this will return true if you find equal data 
     if(current.getData() != null && current.getData().equals(temp.getData())) 
     { 
      if(found) 
      { 
       // remove element 
       previous.setNext(current.getNext()); 
       listCount--; 
       break; 
      } 
      else 
      { 
       found = true; 
      } 

     } 
     else { 
      found = false; 
     } 

     previous = current; 
     current = current.getNext(); 
    } 

} 

Edit: Я написал небольшое подмножество реализации LinkedList, используя Node определение класса Ор и использовал небольшой тест, чтобы убедиться, что мой метод removeSecondAppear работает.

public class LinkedList { 
    private Node head; 

    public LinkedList() { 
     head = new Node(0); 
    } 
    public LinkedList(Node node) { 
     head = node; 
    } 

    public void add(Node node) { 
     Node ptr = head; 
     while (ptr.getNext() != null) { 
      ptr = ptr.getNext(); 
     } 
     ptr.setNext(node); 
    } 

    ... /// added removeSecondAppear here, but left out to keep it short(er) 

    // provided a print() method 
} 

С помощью этого теста:

public class Test { 
    public static void main(String[] args) { 
     LinkedList list = new LinkedList(new Node(1)); 
     list.add(new Node(2)); 
     list.add(new Node(4)); 
     list.add(new Node(4)); 
     list.add(new Node(5)); 
     list.print(); 

     list.removeSecondAppearance(4); 
     list.print(); 
    } 
} 

Мой результат:

1 2 4 4 5 
1 2 4 5 

Answer 2

Таким образом, проблема является ваш класс Node ....

В

public class Node { 
    ... 
    Object data; 
    .... 
} 

Так что, когда вы звоните

if(current.getData().equals(temp.getData())) 

в вашем removeSecondAppear, они не будут равны. Помните, Object.equal() на объекте сравнивает ячейки памяти. Ни один из элементов списка не будет равен друг другу, а только сам элемент.

EDIT: Кроме того, вы хотите

previous.setNext(current.getNext()) // К сожалению, исправлена ​​ошибка здесь !!!

РЕДАКТИРОВАТЬ 2: Также вы не исключаете то, что ищете, поэтому находите себя. Чтобы разобраться в этом, подумайте об этом таким образом;

У меня есть список 1, 2, 3, 4, 4, 5. Сколько раз он найдет 4? Я угадываю один раз. Причина в том, что каждый элемент списка имеет адрес, который не совпадает с другим, поскольку это означает, что данными является объект, которому присваивается место в памяти. Поэтому, когда вы вызываете Object.equals (someOtherObject), вы спрашиваете, имеют ли они одно и то же местоположение в памяти. Они не имеют того же места в памяти. Причина, по которой вы обнаруживаете только 1 секунду во время проверки во время удаленияSecondAppear, состоит в том, что вы снова просматриваете весь список и не исключаете нужный узел.

Answer 3

Добавление ответа pmac89, было бы лучше, если бы вы обобщенного ваш класс узла, так что вы можете использовать правильный .equals() метод типа ваших данных:

public class Node<T> { 
    Node<T> next; 

    T data; 

    ... 

} 

С этого момента по существу вы можете заменить Object с T и Node с Node<T>. Когда вы создаете узел, вы указываете его тип. Тогда скажите, что вы делаете Node<String>. Когда вы позвоните по номеру .equals() на данные, он будет использовать String.equals() вместо Object.equals().

Причина, по которой вы не хотите звонить Object.equals(), как сказал pmac89, потому что вы проверяете , если это тот же объект. То, что вы действительно хотите проверить, это , имеют ли они одинаковое значение.

Edit:
Как уже упоминалось Райан J, если ваши данные подкласс Object, он по умолчанию будет equals() реализации для этого типа, если есть один.

Вот дженерики учебник, если вы не знакомы с ними: http://docs.oracle.com/javase/tutorial/java/generics/