Предпочтительный метод фильтрации LinkedList

Question

Классы TestListRemoveFunctional & TestListRemoveUpdateState выполняет фильтрацию во время выполнения LinkedList.

Я думаю, что реализация TestListRemoveFunctional чиста, поскольку она не обновляет состояние, но менее эффективна, так как создает новый список на каждом этапе фильтрации.

Хотя TestListRemoveFunctional & TestListRemoveUpdateState по существу выполняют ту же работу, TestListRemoveFunctional является предпочтительным, так как он не обновляет состояние, в отличие от фильтрации в реализации TestListRemoveUpdateState.

Обратите внимание, что я не могу использовать java8 lambdas или проект Guava lambdas.

Можете подтвердить мое утверждение, что TestListRemoveFunctional предпочтительнее?

import java.util.LinkedList; 

public class TestListRemoveFunctional { 

    public static void main(String args[]) { 

     TestListRemoveFunctional t = new TestListRemoveFunctional(); 
     LinkedList<MyObj> l = new LinkedList<MyObj>(); 
     l.add(new MyObj("1")); 
     l.add(new MyObj("2")); 

     System.out.println("size : "+l.size()); 

     LinkedList<MyObj> f1 = t.filterItem1(l); 
     System.out.println("size : "+f1.size()); 

     LinkedList<MyObj> f2 = t.filterItem2(f1); 
     System.out.println("size : "+f2.size()); 
    } 

    private LinkedList<MyObj> filterItem1(LinkedList<MyObj> l) { 

     LinkedList<MyObj> toReturn = new LinkedList<MyObj>(); 
     for (MyObj myObj : l) { 

      if (!myObj.param.equalsIgnoreCase("1")) { 
       toReturn.add(myObj); 
      } 
     } 
     return toReturn; 
    } 

    private LinkedList<MyObj> filterItem2(LinkedList<MyObj> l) { 

     LinkedList<MyObj> toReturn = new LinkedList<MyObj>(); 
     for (MyObj myObj : l) { 

      if (!myObj.param.equalsIgnoreCase("2")) { 
       System.out.println(myObj.param); 
       toReturn.add(myObj); 
      } 
     } 
     return toReturn; 
    } 



    private static class MyObj { 

     public String param; 

     public MyObj(String param) { 
      this.param = param; 
     } 
    } 

} 

******************************************************************************************** 


import java.util.Iterator; 
import java.util.LinkedList; 

public class TestListRemoveUpdateState { 

    public static void main(String args[]) { 

     TestListRemoveUpdateState t = new TestListRemoveUpdateState(); 
     LinkedList<MyObj> l = new LinkedList<MyObj>(); 
     l.add(new MyObj("1")); 
     l.add(new MyObj("2")); 

     System.out.println("size is : " + l.size()); 

     t.filterItem1(l);  
     System.out.println("size is : " + l.size()); 

     t.filterItem2(l); 
     System.out.println("size is : " + l.size()); 
    } 

    private void filterItem1(LinkedList<MyObj> l) { 

     Iterator<MyObj> iter = l.iterator(); 
     while (iter.hasNext()) { 
      MyObj myObj = iter.next(); 

      if (myObj.param.equalsIgnoreCase("1")) { 
       iter.remove(); 
      } 
     } 
    } 

    private void filterItem2(LinkedList<MyObj> l) { 

     Iterator<MyObj> iter = l.iterator(); 
     while (iter.hasNext()) { 
      MyObj myObj = iter.next(); 

      if (myObj.param.equalsIgnoreCase("2")) { 
       iter.remove(); 
      } 
     } 
    } 

    private static class MyObj { 

     public String param; 

     public MyObj(String param) { 
      this.param = param; 
     } 
    } 

} 

Answer 1

Одним из преимуществ связанных списков является очень эффективная операция remove.

Рассмотрим следующий связанный список (в Java, связанные списки фактически дважды связанный список):

e1 <-> e2 <-> e3 <-> e4 <-> e5 

Если вы хотите удалить e3, все, что вам нужно сделать, это:

e3.previous.next = e3.next; 
e3.next.previous = e3.previous; 
e3.next = null; 
e3.previous = null; 
e3.element = null; 

И это как раз то, что iterator.remove() делает.

Поэтому TestListRemoveUpdateState является более эффективным, потому что вы регулируете LinkedList

---

Как примечание стороны, предпочтительный метод на ArrayList будет TestListRemoveFunctional.

Если вы фильтровать по ArrayList, то TestListRemoveFunctional, чем были бы более эффективным, чем TestListRemoveUpdateState, потому что операция удалить на ArrayList воссоздает полный спектр Подкладочного каждый раз, когда она вызывается (даже если System.arraycopy является очень эффективен) ,

Answer 2

Что предпочтительнее? Сохранять состояние исходного элемента или эффективность? Чтобы оправдать любой выбор между этими классами, вы должны указать, какую черту вы считаете наиболее важной, потому что у вас нет одного без другого. Кстати, и имеет несколько недостатков, как для повышения эффективности идет, а также читаемость

ОБНОВЛЕНИЕ

(читаемость) вместо двух методов фильтрации (один для пункта 1, по одному для пункта 2), только один метод необходимо: Список < T> filterItem (Список < T> l, T item)

(Повторное использование) Используйте дженерики вместо конкретных типов. Вместо < MyObj>, объявите их как < T>. Таким образом, вы можете использовать эти классы и методы со списками любого компонента.

Если вы объявляете параметры как List вместо LinkedList, вы увеличиваете удобство использования этих методов.

(Гибкость) Если вы объявите тип возврата как Список, вы сможете изменить конкретную реализацию List, которую хотите использовать, избегая при этом пользователям ваших классов переписывать свой код.

Было бы еще лучше использовать «фильтр» класс как Викисклад коллекция

(КПД) в конкретной реализации методов фильтра вы используете equalsIgnoreCase со строками, которые не являются не чувствителен к регистру, вы можете просто использовать равные в этом случае.

(Безопасность) Списки могут содержать нуль, в зависимости от реализации. В частности, LinkedList может, поэтому существует риск исключения NullPointerException в этих фильтрах как путем доступа к элементу списка, так и при доступе к его значению MyObj.param.

Answer 3

Это зависит от того, что вы подразумеваете под «предпочтительным». Удаление элемента из списка во время повтора через него безопасно выполняется с помощью итератора (как вы это делаете).

Если вы посмотрите на свой другой подход, то да, вы создаете новый связанный список. В худшем случае вы в конечном итоге используете пространство O(2*n), если не закончите фильтровать что-либо. Так что это зависит от того, комфортно ли вы используете больше памяти.

Я думаю, что первый подход прекрасен, поскольку в документации, используя iterator.remove(), совершенно безопасно.Это было бы небезопасно, если вы не можете гарантировать, что коллекция будет изменена кем-то еще в одно и то же время (т. Е. Одновременный доступ).