Java 자료구조 - List , Set 정리

Collection 프레임워크에서 지원하는 자료구조들과 Map은 전부 힙 영역에 저장이 된다.

List, Set, Map의 각 노드에는 객체를 가르키는 주소가 저장되어있다. 중복이 허용되는 List와 Map은 A요소와 B요소가 서로 완전히 똑같은 값을 가진 객체가 배정 된다면 하나의 객체를 가르키는 주소값을 서로 공유 하는 형태로 구성된다.

 

 

List

List는 중복된 값을 삽입하는 것이 가능하고 인덱스 넘버를 통해 참조하고 관리된다.

List 종류	특징
ArrayList	중복된 요소 저장 o 스레드 안전성 x 삽입, 삭제시 인덱스 요소들이 직접 이동 o
Vector	중복된 요소 저장 o 스레드 안전성 x
LinkedList	중복된 요소 저장 o 스레드 안전성 x 삽입, 삭제시 인덱스 요소들이 직접 이동 x (just 링크가 끊김)

ArrayList vs Vector

멀티 스레드 환경이 아닌경우 ArrayList사용이 바람직하다.

또한, Vector 클래스는 컬렉션 프레임워크가 나오기전에 가변 개수의 배열이 필요할 때 과거에 사용되었으며, 현대에는 성능 상 사용하지않고 ArrayList를 사용한다. 다만 호환성을 위해서 제거하지않고 남겨두었다고 보면 된다.

Vector와 ArrayList의 주요 차이점중 하나는 동기화이다. 
Vector는 내부적으로 여러개의 스레드가 접근 할 때 데이터 안정성을 위해 한개의 스레드씩 순차적으로 처리할 수 있도록 동기화 되어있다. (스레드 안전성) 안정성을 보장하는 만큼 일을 많이 처리한다는 의미이고 메모리를 많이 사용한다고 볼 수 있다. ArrayList는 동기화되어있지 않기때문에 여러개의 스레드에서 접근 할 때 필요에 따라 동기화 처리를 해주어야 한다.

따라서, 멀티 스레드 환경이 아닌경우 ArrayList사용이 바람직하다.
Vector가 동기화 한다는 것은 복수의 스레드로부터 추가/삭제가 이루어져도 내부의 데이터 처리는 안전하게 한번에 하나의 스레드만 처리되도록 보장한다는 의미이다. 데이터 처리가 안정적으로 이루어지도록 보장하는 것이다. 단일 스레드의 경우 자동으로 동기화를 보장하는 것이 오히려 성능 저하를 일으킬 수 있기 때문에 동기화를 진행하지 않는 ArrayList가 더 효율적인 성능을 보장한다고 할 수 있다. 

 

ArrayList vs LinkedList

데이터를 조회하는 작업이 많은 경우 인덱스의 장점을 가진 ArrayList를 사용하는 것이 바람직하고,
데이터 추가/삭제 작업이 많은 경우 참조값만 변경하면 되는 LinkedList를 사용하는 것이 바람직하다.

ArrayList와 LinkedList의 주요 차이점중 하나는 삽입, 삭제 시 요소들이 이동하는지이다.
ArrayList는 중간 인덱스의 요소를 특정해서 삭제하면 해당 요소보다 뒤의 인덱스를 가진 요소들이 한 칸 씩 앞으로 당겨진다.
LinkedList는 먼저 중간 인덱스에서 삭제가 이루어지면 해당 링크(L)와 서로 바라보던 L-1번 L+1번인덱스의 링크들과 연결을 끊고 -1, +1번 인덱스가 서로 다시 링크를 연결한다. 실질적으로 리스트의 요소 사이의 빈공간 없이 관리되지만 원래 중간 링크가 가지고있던 인덱스 번호는 비어있게 된다.
이 특징 덕분에 높은 빈도의 삽입 삭제가 이루어 질 때 속도 측면에서 ArrayList보다 유리하다.

 

Set

Set은 저장 순서를 보장하지않고 중복을 허용하지 않는다. 중복 금지에선 null도 해당된다. 두 개 이상의 null값을 저장하지 않는다.

HashSet > LinkedHashSet > TreeSet 순서로 성능이 좋다.

Set 종류	특징
HashSet	중복된 요소 저장 x 순서 유지 x
LinkedHashSet	중복된 요소 저장 x 입력된 순서대로 유지 o
SortedSet	- 인터페이스이므로 구현체가 필요 - SortedSet에 포함된 객체가 Comparable 인터페이스를 구현한 객체이거나 - Comparator인터페이스를 구현한 객체여야 한다
TreeSet	중복된 요소 저장 x 순서 유지 x 오름차순 정렬 (red-black tree)

 

HashSet vs LinkedHashSet

HashSet와 LinkedHashSet의 차이점은 입력된 순서가 유지되는지이다.

LinkedHashSet을 사용하면 내부에 정렬된 목록이 포함되어 있다. 즉, LinkedHashSet은 삽입된 순서대로 집합 요소의 연결된 목록을 유지한다. 그러나 이로 인해 LinkedHashSet 클래스가 HashSet 클래스 보다 더 긴 작업을 수행하게 된다.

 

HashSet vs TreeSet

HashSet와 TreeSet의 차이점은 정렬이다.

TreeSet은 이진탐색트리의 형태로 데이터를 저장하는 컬렉션이다. 이진탐색트리 중에서도 성능을 향상시킨 '레드-블랙 트리'로 구현되어 있다. 따라서 데이터의 추가, 삭제에는 시간이 걸리지만, 검색과 정렬이 뛰어나다는 장점이 있다.
TreeSet은 디폴트 값은 오름차순이며 인스턴스의 비교 기준을 정하는 Comparable이나 Comparator를 기반으로 정렬 기준을 직접 커스텀할수도 있다.

 

SortedSet

SortedSet은 인터페이스이기 때문에 이를 구현할 구현체가 있어야 한다. 대표적인 구현체는 TreeSet

Method	설명
headSet(E toElement)	toElement(미포함)보다 작은 객체들로 구성된 SortedSet 리턴
tailSet(E fromElement)	fromElement(포함)보다 큰 객체들로 구성된 SortedSet 리턴
subSet(E fromElement, E toElement)	fromElement(포함)보다 크고 toElement(미포함)보다 작은 객체들로 구성된 SortedSet 리턴
first()	가장 작은 엘리먼트 리턴
last()	가장 큰 엘리먼트 리턴

 

Sorted<String> sortedSet = new TreeSet<>();

sortedSet.add("Elem5");
sortedSet.add("Elem2");
sortedSet.add("Elem4");
sortedSet.add("Elem3");
sortedSet.add("Elem1");

SortedSet<String> headSet = sortedSet.headSet("Elem3");
System.out.println("Head Set");
for (String elem : headSet) {
    System.out.println(elem);
}

SortedSet<String> tailSet = sortedSet.tailSet("Elem4");
System.out.println("Tail Set");
for (String elem : tailSet) {
    System.out.println(elem);
}

SortedSet<String> subSet = sortedSet.subSet("Elem2", "Elem5");
System.out.println("Sub Set");
for (String elem : subSet) {
    System.out.println(elem);
}

System.out.println("First");
System.out.println(sortedSet.first());

System.out.println("Last");
System.out.println(sortedSet.last());

Head Set
Elem1
Elem2
Tail Set
Elem4
Elem5
Sub Set
Elem2
Elem3
Elem4
First
Elem1
Last
Elem5

 

Collection 대표적인 메서드

Method	설명
add(E e)	컬렉션에 요소 삽입 인덱스를 지정해 값을 삽입, 값을 맨 뒤에 삽입
A.addAll(B)	컬렉션의 컬렉션 삽입 B컬렉션의 요소들을 추출해 A컬렉션에 삽입 인덱스를 지정해 해당 인덱스부터 중간에 끼워넣어 삽입
clear()	컬렉션의 모든 요소를 지운다.
contains(Ojbect o)	컬렉션에 요소들 중 파라미터로 넘긴 인자가 있는지 확인한다. 있으면 true 없으면 false를 리턴한다.
A.containsAll(B)	컬렉션 A의 요소들중 컬렉션 B의 요소가 완전히 포함되는지 확인한다. 있으면 true 없으면 false를 리턴한다.
remove(Objcet o)	컬렉션에서 인덱스나 값에 해당되는 요소를 제거한다.
A.removeAll(B)	A컬렉션의 요소들중 B컬렉션의 요소에 해당하는 것들을 전부 삭제한다.
A.retainAll(B)	A컬렉션에서 B컬렉션의 요소만 남기고 전부 삭제한다.
size()	컬렉션의 현재 크기를 리턴한다.
toArray(T[])	컬렉션의 요소들을 지정한 타입의 배열로 만들어 리턴한다.
iterator()	요소들을 하나씩 꺼내어 반복해주는 iterator 객체를 리턴해준다. 1. hasNext() : 다음 값의 유무를 판단해 참, 거짓을 리턴해준다. 2. next() : 현재 노드가 가르키고있는 객체를 리턴해주고 다음 노드로 이동한다. 3. remove() : 직전 next() 메서드에 의해 리턴 된 객체가 저장되어있는 노드를 삭제한다. 위의 메서드들 중 리턴 방식이 설명 되지않은 메서드들은 전부 메서드가 정상 작동했는지 여부를 boolean으로 리턴한다.
stream()	Stream을 리턴