Как добавить новый уникальный элемент в список

Question

У меня есть список из 100000 объектов. И его уникальный список. Я хочу добавить к нему новый объект. Но условие для добавления должно быть уникальным значением, если новый элемент уже находится в списке, не следует добавлять в список и должен генерировать исключение. Пожалуйста, дайте мне знать, если есть идея.

Answer 1

Вы можете использовать набор, он содержит только уникальные результаты http://docs.oracle.com/javase/7/docs/api/java/util/Set.html.

Благодаря

Answer 2

Вы должны скорее использовать Set скорее List.

Но если вы можете получить его -

List<Object> list =...; 
public boolean add(Object obj){ 
    Set<Object> set = new HashSet<>(list); 
    return set.add(obj); 
} 

Answer 3

Вы должны использовать структуру Set данных для вашего требования. Но он не будет генерировать исключение, если вы попытаетесь добавить новый дубликат.

Если у вас уже есть список, то вы можете создать Set с помощью

Set<YourType> foo = new HashSet<YourType>(yourList); 

Answer 4

Использование Set вместо List. Если вы действительно хотите иметь Список, рассмотрите следующий пример.

List<String> myList=new ArrayList<>(); 
    myList.add("asd"); 
    myList.add("asf"); 
    myList.add("asf"); 
    Set<String> set=new HashSet<>(); 
    set.addAll(myList); 
    set.add("newString"); 
    myList.clear(); 
    myList.addAll(set); 

Answer 5

Если порядок вставки важно, использовать LinkedHashSet вместо того, который является в основном набор, но также отслеживает элемент в списке, чтобы позволить итерации по элементам в том же порядке, как они были вставлены (как со списком).

Что касается исключения при попытке добавить дубликат элемента, вы можете проверить, если элемент был добавлен, проверив, что метод add(..) вернулся true и бросить Exception иначе, или путем создания специализированного подкласса, который делает эту проверку:

public class UniqueItemList <E> extends LinkedHashSet<E> { 

    @Override 
    public boolean add (E e) { 
     checkContains(e); 
     return super.add(e); 
    }; 

    @Override 
    public boolean addAll (Collection<? extends E> collection) { 
     for (E e : collection) { 
      add(e); 
     } 
     return !collection.isEmpty(); 
    } 

    private void checkContains (E e) { 
     if (contains(e)) { 
      throw new IllegalArgumentException("Element was already added"); 
     } 
    } 
} 

Answer 6

Если у вас есть хороший повод, чтобы использовать List, например, потому, что имеет значение для того, чтобы вам, просто использовать contains, чтобы проверить, является ли элемент, который вы хотите добавить, уже в списке:

public void addUnique(Object element) throws NotUniqueException { 
    if (list.contains(element)) { 
     throw new NotUniqueException(list, element); 
    } else { 
     list.add(element); 
    } 
} 

Однако для 100 000 объектов contains будет медленным, поскольку он должен выполнять линейный поиск.

Альтернативой может быть, если ваши списки хранят ваши объекты в некотором естественном порядке, например, порядок, который может быть описан с помощью java.util.Comparator. В этом случае, вместо того, чтобы использовать contains, вы можете использовать бинарный поиск, чтобы сократить поиск от O (N) до O (журнал (п)):

public void addUnique(Object element) throws NotUniqueException { 
    int index = Collections.binarySearch(list, element, comparator); 
    if (index >= 0) { 
     throw new NotUniqueException(list, element); 
    } else { 
     list.add(index, element); 
    } 
} 

Однако недостатком является то, что ваш add теперь становится дороже, потому что для сортировки списка некоторые элементы нужно перемещать, чтобы освободить место для нового элемента. Это делает вашу линейную операцию add.

Структура данных, которая дает вам как заказ, так и быстрый contains и быстрый add - это отсортированное дерево, поэтому вы можете оценить, подходит ли это вам.

Наконец, вы могли бы объединить Set с List, т.е. хранить каждый элемент как: набор дает вам быстрый contains а список сохраняет порядок элементов. При таком подходе, вы не ограничены в определенном порядке, определенном в Comparator, но вы можете просто использовать порядок вставки:

public void addUnique(Object element) throws NotUniqueException { 
    if (set.contains(element)) { 
     throw new NotUniqueException(list, element); 
    } else { 
     list.add(element); 
     set.add(element); 
    } 
} 

Это в основном то, что LinkedHashSet делает для вас - смотрите также ответ Питера Вальзера в.