중복되지 않는 목록 구현이 있습니까?

중복되지 않는 목록 구현이 있습니까?

---

나는 알고 SortedSet있지만, 내 경우에는 그 구현 뭔가가 필요 List, 그리고 Set. 그렇다면 API 또는 다른 곳에 구현이 있습니까?

나 자신을 구현하는 것은 어렵지 않지만 여기 사람들에게 먼저 물어 보는 것은 어떨까요?

---

이 작업을 수행하는 표준 라이브러리에는 Java 컬렉션이 없습니다. 그래도 LinkedHashSet<E>a와 비슷하게 순서를 유지 List하므로 a List로 사용하고 싶을 때 세트를 a로 래핑 하면 원하는 List의미를 얻을 수 있습니다.

또는 Commons Collections (또는 commons-collections4일반 버전의 경우)에는 List이미 원하는 작업을 수행하는 SetUniqueList/ SetUniqueList<E>.

---

여기 내가 한 일이 있으며 작동합니다.

내가이 있으리라 믿고 ArrayList내가 한 첫 번째 일은 함께 작동하도록하는 것은 새를 만들었습니다 LinkedHashMap.

LinkedHashSet<E> hashSet = new LinkedHashSet<E>()

그런 다음 새 요소를 LinkedHashSet. add 메서드는를 변경하지 않고 LinkedHasSet새 요소가 중복 된 경우 false를 반환합니다. 그래서 이것은 ArrayList.

if (hashSet.add(E)) arrayList.add(E);

이것은 배열 목록에 중복 항목이 추가되는 것을 방지하는 간단하고 우아한 방법입니다. 원하는 경우이를 캡슐화하고을 확장하는 클래스에서 add 메서드를 재정의 할 수 있습니다 ArrayList. addAll요소를 반복하고 add 메서드를 호출하여 처리하는 것을 기억하십시오 .

---

그래서 결국 제가 한 일이 있습니다. 다른 사람에게 도움이되기를 바랍니다.

class NoDuplicatesList<E> extends LinkedList<E> {
    @Override
    public boolean add(E e) {
        if (this.contains(e)) {
            return false;
        }
        else {
            return super.add(e);
        }
    }

    @Override
    public boolean addAll(Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(copy);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(index, copy);
    }

    @Override
    public void add(int index, E element) {
        if (this.contains(element)) {
            return;
        }
        else {
            super.add(index, element);
        }
    }
}   

---

dhiller의 대답을 진지하게 고려해야합니다.

1. 중복이없는 목록에 개체를 추가하는 것에 대해 걱정하는 대신, 기본적으로 중복을 필터링하는 집합 (모든 구현)에 추가합니다.
2. List가 필요한 메서드를 호출해야하는 경우이를 a new ArrayList(set)(또는 a new LinkedList(set)등)로 래핑합니다 .

귀하가 게시 한 솔루션 NoDuplicatesList에는 주로 contains()메서드에 문제가 있으며 클래스가 addAll()메서드에 전달 된 컬렉션의 중복 검사를 처리하지 않는다고 생각합니다 .

---

목록으로 집합을 캡슐화하지 않는 이유는 다음과 같습니다.

new ArrayList( new LinkedHashSet() )

이것은 Collections의 진정한 마스터 인 누군가를 위해 다른 구현을 남겨 둡니다. ;-)

---

나는 그런 것이 필요했기 때문에 커먼즈 컬렉션에 가서 SetUniqueList를 사용했지만 성능 테스트를 실행했을 때 Set을 사용하고 배열을 사용하여 배열을 얻으려면 사례에 비해 최적화되지 않은 것 같습니다. Set.toArray () 메서드를 사용하는 경우 SetUniqueTest는 다른 구현과 비교하여 100,000 개의 문자열을 채우고 순회하는 데 20 : 1 시간이 걸렸으므로 큰 차이가 있으므로 성능이 걱정 되시면 Set 및 SetUniqueList의 논리가 실제로 필요한 경우가 아니면 SetUniqueList를 사용하는 대신 배열을 가져 오면 다른 솔루션을 확인해야합니다.

테스트 코드 주요 방법 :

public static void main (String [] args) {

SetUniqueList pq = SetUniqueList.decorate(new ArrayList());
Set s = new TreeSet();

long t1 = 0L;
long t2 = 0L;
String t;


t1 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    pq.add("a" + Math.random());
}
while (!pq.isEmpty()) {
    t = (String) pq.remove(0);
}
t1 = System.nanoTime() - t1;

t2 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    s.add("a" + Math.random());
}

s.clear();
String[] d = (String[]) s.toArray(new String[0]);
s.clear();
for (int i = 0; i < d.length; i++) {
    t = d[i];

}
t2 = System.nanoTime() - t2;

System.out.println((double)t1/1000/1000/1000); //seconds
System.out.println((double)t2/1000/1000/1000); //seconds
System.out.println(((double) t1) / t2);        //comparing results

}

감사합니다 Mohammed Sleem http://abusleem.net/blog

---

참고 : 하위 목록 구현은 고려 하지 않습니다 .

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class UniqueList<T> extends ArrayList<T> {

    private static final long serialVersionUID = 1L;

    /** Unique elements SET */
    private final Set<T> set=new HashSet();

    /** Used by addAll methods */
    private Collection<T> addUnique(Collection<? extends T> col) {
        Collection<T> unique=new ArrayList();
        for(T e: col){
            if (set.add(e)) unique.add(e);
        }
        return unique;
    }

    @Override
    public boolean add(T e) {
        return set.add(e) ? super.add(e) : false;
    }

    @Override
    public boolean addAll(Collection<? extends T> col) {
        return super.addAll(addUnique(col));
    }

    @Override
    public void add(int index, T e) {
        if (set.add(e)) super.add(index, e);
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> col) {
        return super.addAll(index, addUnique(col));
    }

}

---

The documentation for collection interfaces says:

Set — a collection that cannot contain duplicate elements.
List — an ordered collection (sometimes called a sequence). Lists can contain duplicate elements.

So if you don't want duplicates, you probably shouldn't use a list.

---

in add method, why not using HashSet.add() to check duplicates instead of HashSet.consist(). HashSet.add() will return true if no duplicate and false otherwise.

---

Off the top of my head, lists allow duplicates. You could quickly implement a UniqueArrayList and override all the add / insert functions to check for contains() before you call the inherited methods. For personal use, you could only implement the add method you use, and override the others to throw an exception in case future programmers try to use the list in a different manner.

---

I just made my own UniqueList in my own little library like this:

package com.bprog.collections;//my own little set of useful utilities and classes

import java.util.HashSet;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author Jonathan
*/
public class UniqueList {

private HashSet masterSet = new HashSet();
private ArrayList growableUniques;
private Object[] returnable;

public UniqueList() {
    growableUniques = new ArrayList();
}

public UniqueList(int size) {
    growableUniques = new ArrayList(size);
}

public void add(Object thing) {
    if (!masterSet.contains(thing)) {
        masterSet.add(thing);
        growableUniques.add(thing);
    }
}

/**
 * Casts to an ArrayList of unique values
 * @return 
 */
public List getList(){
    return growableUniques;
}

public Object get(int index) {
    return growableUniques.get(index);
}

public Object[] toObjectArray() {
    int size = growableUniques.size();
    returnable = new Object[size];
    for (int i = 0; i < size; i++) {
        returnable[i] = growableUniques.get(i);
    }
    return returnable;
    }
}

I have a TestCollections class that looks like this:

package com.bprog.collections;
import com.bprog.out.Out;
/**
*
* @author Jonathan
*/
public class TestCollections {
    public static void main(String[] args){
        UniqueList ul = new UniqueList();
        ul.add("Test");
        ul.add("Test");
        ul.add("Not a copy");
        ul.add("Test"); 
        //should only contain two things
        Object[] content = ul.toObjectArray();
        Out.pl("Array Content",content);
    }
}

Works fine. All it does is it adds to a set if it does not have it already and there's an Arraylist that is returnable, as well as an object array.

참고URL : https://stackoverflow.com/questions/268672/is-there-a-no-duplicate-list-implementation-out-there