[Set]

중복을 허용하지 않는 자료구조로, 모든 데이터가 Unique 하다.

Set Interface 를 구현하는 HashSet, LinkedHashSet, TreeSet 은 위와 같은 성질을 따른다.

 

[HashSet]

내부적으로 HashMap 을 사용

순서 보장 X

null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다

 

[LinkedHashSet]

내부적으로 LinkedHashMap을 사용

순서 보장 O (입력한 순서)

null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다

 

[TreeSet]

내부적으로 TreeMap을 사용

인자값으로 받은 Comparator 를 기준으로 정렬, 인자값이 없는 경우 오름차순 정렬

null 입력 불가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
Set<Integer> set = new HashSet<>();
set.add(null);
set.add(null); //중복허용X
set.add(3);
set.add(2);
set.add(1);
set.add(1);    //중복허용X
 
System.out.print("HashSet: ");
 
Iterator<Integer> si = set.iterator();
while(si.hasNext()) {
    System.out.print(si.next()+" ");
}
System.out.println();
 
 
Set<Integer> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add(3);
linkedHashSet.add(2);
linkedHashSet.add(1);
linkedHashSet.add(1); //중복허용 X
 
System.out.print("linkedHashSet: ");
for(int i : linkedHashSet) {
    System.out.print(i+" ");
}
System.out.println();
 
 
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(2);
treeSet.add(1);
treeSet.add(1); //중복허용X
 
System.out.print("TreeSet: ");
for(int i : treeSet) {
    System.out.print(i+" ");
}
System.out.println();
 
 
Set<Integer> treeSetDescending = new TreeSet<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        //내림차순
        return o2-o1;
    }
});
 
System.out.print("TreeSetDescending: ");
try {
    treeSetDescending.add(null);    //null 허용 X
}catch(NullPointerException ne) {
    System.out.println("exception:"+ne.getMessage());
}
treeSetDescending.add(3);
treeSetDescending.add(2);
treeSetDescending.add(1);
treeSetDescending.add(1); //중복허용X
 
for(int i : treeSetDescending) {
    System.out.print(i+" ");
}
 cs

 

[실행 결과]

HashSet: 1 2 3
linkedHashSet: 3 2 1
TreeSet: 1 2 3
TreeSetDescending: 3 2 1

 

[시간복잡도]

HashSet 이 LinkedHashSet, TreeSet보다 성능이 좋으며 메모리를 적게 사용.

   HashSet LinkedHashSet TreeSet
performance Θ(1) Θ(1) Θ(log(n))

 

참고 :

https://javaconceptoftheday.com/hashset-vs-linkedhashset-vs-treeset-in-java/

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20
트리 순회  (0) 2019.11.26

[List]

순서가 있는 데이터의 집합, 데이터 중복을 허용

List Interface 를 구현하는 ArrayList, LinkedList, Vector 는 모두 위 성질을 따름

 

[사용법]

ArrayList, LinkedList, Vector 모두 사용법이 동일하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
List<Integer> al = new ArrayList<>();
al.add(1);
al.add(2);
al.add(2);    //중복허용, 순서보장
//al.remove(0);
 
System.out.print("ArrayList: ");
for(int i:al) {
    System.out.print(i+" ");
}
System.out.println();
 
List<Integer> ll = new LinkedList<>();
ll.add(1);
ll.add(2);
ll.add(2);    //중복허용, 순서보장
//ll.remove(0);
 
System.out.print("LinkedList: ");
for(int i:ll) {
    System.out.print(i+" ");
}
System.out.println();
 
List<Integer> v = new Vector<>();
v.add(1);
v.add(2);
v.add(2);    //중복허용, 순서보장
//v.remove(0);
 
System.out.print("Vector: ");
for(int i:v) {
    System.out.print(i+" ");
}
 cs

[실행 결과]

ArrayList: 1 2 2
LinkedList: 1 2 2
Vector: 1 2 2

 

[차이점]

ArrayList

배열과 동일하나 저장되는 자료크기에 따라 내부적으로 배열의 크기가 늘었다 줄었다 하는 resizable array.

조회 수행속도가 빠르다.

데이터 삽입이 발생하면 삽입된 데이터 뒤에 위치하는 모든 데이터의 인덱스를 하나씩 증가시킨다(한 칸씩 민다)

데이터 삭제가 발생하면 삭제된 데이터 뒤에 위치하는 모든 데이터의 인덱스를 하나씩 감소시킨다(한 칸씩 당긴다).

 

LinkedList

자료의 주소값을 기준으로 데이터들이 연결된 형태.

삽입과 삭제의 수행속도가 빠르다.

데이터 삽입이 발생하면 삽입될 데이터 앞의 데이터는 삽입될 데이터의 주소값을,

삽입될 데이터는 삽입될 데이터 뒤에 위치한 데이터의 주소값을 참조하게 한다.

 

Vector

Thread Safe 한 ArrayList (Synchronized)

 

[ArrayList vs LinkedList 성능 비교]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
private static long START_TIME = 0;
    private static long END_TIME = 0;
    
    public static void main(String[] args) {
        
        List<Integer> ArrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            ArrayList.add(0);
        }
        setEndTime();
        System.out.print("ArrayList add: ");
        printDuration();
 
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            linkedList.add(0);
        }
        setEndTime();
        System.out.print("LinkedList add: ");
        printDuration();
        
        System.out.println("-------------------------------------------------");
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            ArrayList.get(i);
        }
        setEndTime();
        System.out.print("ArrayList get: ");
        printDuration();
        
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            linkedList.get(i);
        }
        setEndTime();
        System.out.print("LinkedList get: ");
        printDuration();
        
        System.out.println("-------------------------------------------------");
        
        setStartTime();
        Iterator<Integer> ai = ArrayList.iterator();
        while(ai.hasNext()) {
            ArrayList.remove(0);
        }
        setEndTime();
        System.out.print("ArrayList remove: ");
        printDuration();
        
        
        setStartTime();
        Iterator<Integer> li = linkedList.iterator();
        while(li.hasNext()) {
            linkedList.remove(0);
        }
        setEndTime();
        System.out.print("LinkedList remove: ");
        printDuration();
        
    }
    
    private static void setStartTime() {
        START_TIME = System.nanoTime();
    }
    
    private static void setEndTime() {
        END_TIME = System.nanoTime();
    }
    
    private static void printDuration() {
        System.out.println(END_TIME - START_TIME);
    }
 cs

[실행 결과]

ArrayList add: 1049700
LinkedList add: 1224800
-------------------------------------------------
ArrayList get: 861200
LinkedList get: 42666800
-------------------------------------------------
ArrayList remove: 6322100
LinkedList remove: 1229300

 

조회(get)는 ArrayList가 상대적으로 뛰어난 성능을 보여준다.

삽입(add)/삭제(remove)는 LinkedList가 상대적으로 뛰어난 성능을 보여준다.

[ArrayList vs LinkedList 시간복잡도]

   ArrayList LinkedList
Indexing Θ(1) Θ(n)
Insert/delete at beginning Θ(n) Θ(1)
Insert/delete at end Θ(1) Θ(n)-last element is unknown
Θ(1)-last element is known
Insert/delete in middle Θ(n) search time + Θ(1)
Wasted space (average) Θ(n) Θ(n)

 

 

참고 :

https://dzone.com/articles/arraylist-vs-linkedlist-vs

http://www.nextree.co.kr/p6506/

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20
트리 순회  (0) 2019.11.26

+ Recent posts

티스토리툴바