Java - 자료구조와 컬렉션 프레임워크

출처: https://static.javatpoint.com/images/java-collection-hierarchy.png

출처: https://media.vlpt.us/images/wo_ogie/post/d8a7523a-0aa7-41d0-a593-dd10bef6881f/image.png

컬렉션 프레임워크(collection framework)란?

자바에서 데이터를 저장하는 클래스들을 표준화한 클래스 집합. 데이터를 저장하는 자료구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해놓음

자료구조

Collection

Collection은 객체의 모음, 그룹이다. Iterable 인터페이스를 상속받으므로 Iterable 인터페이스는 내부에 Iterator 인터페이스를 반환하는 iterator() 메소드를 정의하고 있다.

Collection을 상속받아 List와 Set, Queue을 구현하는 클래스에서는 Iterable의 iterator() 메소드를 구현해야 함.

Collection은 기본 데이터형이 아닌, 참조 데이터형만 저장이 가능하다. 따라서 Collection에서의 데이터는 Object 타입의 객체로서 저장이 된다.

List

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

특징

1] 동일한 데이터의 중복을 허용.

2] 데이터 저장 순서가 유지

3] 힙(heap) 영역 내에서 List는 객체를 일렬로 늘어놓은 구조

4] 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동으로 인덱스가 부여.

- List 주요 메소드 설명

메소드	설명
get(int index)	요소의 index 순서에 해당하는 값을 가져온다.
add(V) add(int index, V)	요소에 값을 추가한다. 데이터를 추가 성공시 true, 중복데이터 저장시 false 반환 param이 2개인경우, 첫번째는 순서를 지정할 수 있음
set(int index, V)	요소에 index에 해당하는 데이터를 변경한다.
contains(V)	요소내에 지정한 객체를 포함하고 있는지를 확인
remove(V) remove(int index)	요소내 지정한 객체를 삭제. 객체를 지정하거나 순서를 지정할 수 있다. 삭제성공시 true, 실패시 false 반환
clear()	요소의 모든 데이터를 삭제
indexOf(V)	요소내 해당하는 데이터의 위치를 반환. 해당되는 데이터가 없으면 -1을 리턴 데이터가 여러개라면, 맨처음으로 해당하는 위치를 리턴
lastIndexOf(V)	요소내 해당하는 데이터의 위치를 반환. 해당되는 데이터가 없으면 -1을 리턴 데이터가 여러개라면, 맨마지막으로 해당하는 위치를 리턴
sort(Comparator)	요소의 데이터를 Comparator 인터페이스를 입력하여 정렬한다.
size()	요소의 크기를 반환
toArray() toArray(new T[n])	요소를 배열로 변환 - toArray(): Object Array - toArray(new T[n]): T Array

- List 구현가능 Class

= ArrayList: 배열기반, 데이터의 추가와 삭제에 불이, 순차적인 추가삭제는 제일 빠르다.

(List 인터페이스의 구현 클래스) 크기가 가변적으로 변하는 선형리스트. 일반적인 배열과 같은 순차리스트이며, 인덱스로 내부의 객체를 관리한다는 점은 배열과 같지만, 일반 배열은 크기가 변하지않지만, ArrayList는 객체들이 추가되어 저장용량을 초과한다면 자동으로 부족한 크기만큼 저장 용량(capacity)이 늘어난다는 특징이 있다. LinkedList와는 반대로, 인덱스로 객체를 관리하기때문에, 검색측면에서는 성능이 우수하지만, 추가/삭제시에는 인덱스를 재정렬하는 과정이 거쳐지기때문에, 속도가 조금 떨어진다.

 

= LinkedList: 연결기반, 데이터의 추가와 삭제에 유리. 임의의 요소에 대한 접근성이 좋지 않음.

List 인터페이스를 구현. (+ Deque 인터페이스와 같이) 연결 리스트. 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당하는데, 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 따라서, 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기 때문에, 추가/삭제는 용이하지만, 인덱스가 없어서 특정 요소에 접근하는데에 순차 탐색을 하게되므로, 속도가 조금 떨어진다.

(!) 데이터의 추가/삭제가 많은 경우 이 자료구조를 사용.

- LinkedList 주요 메소드 설명

(!) List의 주요 메소드 사용가능

메소드	설명
addFirst(V) addLast(V)	요소의 맨앞, 맨뒤에 값을 추가
getFirst() getLast()	요소의 맨앞, 맨뒤의 값을 가져온다
offer(V) offerFirst(V) offerLast(V)	요소의 맨앞(offer, offerFirst), 맨뒤(offerLast)에 값을 추가한다 add()는 Exception이 발생하는데, offer는 boolean을 반환한다
peek() peekFirst() peekLast()	요소의 맨앞(peek, peekFirst), 맨뒤(peekLast)의 값을 조회한다
poll() pollFirst() pollLast()	요소의 맨앞(poll, pollFirst), 맨뒤(pollLast)의 값을 가져오면서 해당되는 요소를 제거한다
pop()	요소의 맨앞의 값을 가져오면서 해당되는 요소를 제거한다

= Vector: Legacy. 가변길이의 배열.

Vector는 ArrayList와 동일한 내부 구조를 가지고 있다. Vector를 생성하기 위해서는 지정한 객체 타입을 타입 파라미터를 표기하고 기본 생성자를 호출하면 된다. ArrayList와의 차이점은, 멀티 스레드 사용시, 하나의 스레드가 실행을 완료해야만 다른 스레드가 실행을 할 수 있다는 점. (데이터의 무결성 보장)

- Vector 주요 메소드 설명

(!) List의 주요 메소드 사용가능

메소드	설명
capacity()	요소의 가용길이를 반환
addElement(V)	요소에 값을 추가. (add와 동일한 기능) 이 메소드는 Vector에만 존재하며 별도의 리턴값이 없고, JDK 1.1에서는 이 메소드를 사용해야 함
firstElement() lastElement()	요소의 첫번째, 마지막 값을 가져온다
elementAt(int index)	요소의 index번째 값을 가져온다
insertElementAt(V, int index)	요소의 index번째에 값을 끼워넣는다

 

= Stack: Vector를 상속받으며, 후입선출(LIFO)

Stack은 synchronized가 붙어있어서 Thread-Safe하지만, 멀티스레드 환경이 아닐때 사용하면 lock을 거는 작업때문에 많은 overhead가 발생한다. 그리고 Vector를 상속받은것은 자바의 큰 실수라고 한다. 한쪽에서만 데이터가 들어가야하는데, Vector를 상속받았기 때문에 중간에 데이터 삽입, 삭제를 할 수 있게 된다. Stack대신에 ArrayDeque로 대체할 수 있다.

- Stack 주요 메소드 설명

(!) List의 주요 메소드 사용가능

메소드	설명
pop()	요소의 맨뒤의 값을 가져오면서 해당되는 요소를 제거한다
peek()	요소의 맨앞의 값을 조회한다
push(V)	요소의 맨뒤에 값을 넣는다
search(V)	해당하는 요소의 위치를 찾는다. 순서는 맨앞이 아닌 맨뒤가 0부터 시작 (Stack의 특성) 해당하는 값이 없다면 -1을 반환한다
setSize(int size) capacity()	요소의 저장길이를 변경한다 (default: 10) 요소의 길이정보를 가져온다
firstElement() lastElement()	요소의 첫번째, 마지막 값을 가져온다

Set

순서를 유지하지 않는 데이터의 집합. 데이터의 중복을 허용하지 않음

- Set 주요 메소드 설명

메소드	설명
add(V)	요소에 값을 추가. 성공시 true, 중복데이터 저장시 false 반환
contains(V)	요소에 지정한 값을 포함하고 있는지를 확인
remove(V)	요소에 지정한 값을 삭제. 삭제성공시 true, 실패시 false 반환
clear()	요소내 모든 데이터를 삭제
size()	요소의 크기를 반환

= HashSet: 데이터 중복저장 불가능(Set 상속), 순서를 보장하지 않음.

 

= TreeSet: 데이터 중복저장 불가능(Set 상속), 오름차순으로 데이터를 정렬. (Red-Black Tree구조)

- TreeSet 주요 메소드 설명

(!) Set의 주요 메소드 사용가능

메소드	설명
ceiling(V) floor(V)	요소내 지정한 값을 반환. 없으면 큰 값을 가진 객체 중 제일 가까운 값의 값을 반환. 없다면 null 요소내 지정한 값을 반환. 없으면 작은 값을 가진 객체 중 제일 가까운 값의 값을 반환. 없다면 null
descendingSet()	TreeSet에 저장된 요소들을 역순으로 정렬해서 반환
first() last()	정렬된 순서에서 첫번째 순서 값을 반환 정렬된 순서에서 마지막 순서 값을 반환
pollFirst() pollLast()	요소내 첫번째 값을 가져온다 (가장 작은) 요소내 마지막 값을 가져온다 (가장 큰)
headSet(V) tailSet(V)	요소내 지정한 값보다 작은 값들을 반환 요소내 지정한 값보다 큰 값들을 반환
subSet(V1, V2)	요소내 V1~V2 범위 검색의 결과 값들을 반환

 

Queue

FIFO(First In First Out) 형태를 가지며, 컴퓨터 버퍼, 대기열 등을 만들어 순차적으로 처리할 때 사용

= LinkedList: 연결기반으로 List이외에 Queue 인터페이스 구현체로도 사용한다. (위의 LinkedList 주요메소드 참고)

 

= PriorityQueue: FIFO의 구조를 가지면서도, 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조.

- 주요 메소드 설명

메소드	설명
add(V), offer(V)	데이터를 추가
poll(), remove()	앞열의 데이터를 반환하면서 대기열에서 제거 poll은 대기열 1열에 데이터가 없는경우 null을 반환 / remove는 데이터가 없는경우 NoSuchElementException을 반환
peek()	앞열의 데이터를 반환 (대기열에서 제거하지는 않음)

Map

Key, Value의 쌍으로 이루어진 데이터의 집합. Key는 중복허용하지 않고, Value는 중복을 허용

= HashMap: 배열과 연결이 결합된 형태. 추가, 삭제, 검색, 접근성이 모두 뛰어남. 특히 검색에는 좋은 성능을 보임.

 

= TreeMap: 연결기반. 정렬과 검색(특히 범위검색)에 적합. 검색성능은 HashMap보다 떨어짐.

 

= Hashtable: HashMap과 거의 동일하나, 동기화가 필요할때 사용, null값이 허용되지 않음.(Error 발생)

 

= Properties: Hasttables의 하위 Class. 파일 입출력을 지원

- 주요 메소드 설명

(!) 여기서 V는 HashMap의 Collection에 선언된 타입

메소드	설명
put(key, value)	기본적으로 HashMap에 key, value를 넣음
get(key)	key에 해당하는 value값을 가져온다.
remove(key)	지정한 키의 Map요소를 삭제
clear()	모든 Map요소를 삭제
[Map.Entry<K, V>] entrySet()	Map에 담겨있는 key와 value의 연결들을 반환
[Set<K>] setKey()	Map에 담겨있는 key를 반환
containsKey(key)	Map에 해당하는 key가 있는지 확인
getOrDefault(key, defaultValue)	Map에 해당하는 key가 있는지 확인하여 있으면 key의 value를 반환하고, 없으면 defaultValue를 반환
values()	Map에 있는 value데이터를 Collection<K>형으로 반환

- Map.Entry? Map 인터페이스이며, for문이나 Stream 사용시, Map 형식의 데이터에서 처리가 필요할 때 사용한다.

java.util.Arrays

메소드	설명
copyOf(원본배열, 복사할 길이)	원본배열에서 복사할 길이를 지정하여 배열을 리턴
copyOfRange(원본배열, 복사할 시작인덱스, 복사할 끝인덱스)	원본배열에서 시작, 끝을 지정하여 부분적으로 배열을 가져와서 리턴
binarySearch()	정렬이 되어있는 배열이어야함. 이진 검색 알고리즘을 사용하여 검색한 후, 해당 위치를 반환
fill(배열, 초기화할 값)	해당 배열을 초기화할 값으로 변경한다
sort(배열)	대상 배열을 오름차순으로 정렬한다
equals(배열1, 배열2)	전달받은 두 배열이 같은지를 확인

참고자료

= http://www.tcpschool.com/java/java_api_arrays