[Java] 자료구조 Collection과 Map

Java의 자료구조는 크게 Collection(List, Queue, Set)과 Map으로 나눌 수 있습니다.

List

리스트는 순서를 가지고, 원소의 중복이 허용된다는 특징이 있습니다.

 

ArrayList

ArrayList는 배열을 이용하여 만든 리스트입니다.

기본 크기는 10이지만 원소가 늘어나면 더 큰 배열에 옮겨담습니다.

배열의 특징 때문에 조회가 빠르다는 장점이 있지만, 삽입/삭제가 느리다는 단점이 있습니다.

ArrayList를 사용한다면, 조회를 많이 하는 경우에 사용하는 것이 좋습니다.

 

LinkedList

LinkedList는 노드와 포인터를 이용하여 만든 리스트입니다.

next와 prev로 양방향 포인터를 가집니다.

단순히 기존 포인터를 끊고 새로운 노드에 연결하면 되기에

LinkedList는 포인터로 각각의 노드들을 연결하고 있어서, 삽입/삭제가 빠르다는 장점이 있습니다.

하지만, 특정 원소를 조회하기 위해서는 첫 노드부터 순회해야하기 때문에 ArrayList에 비해 느리다는 단점이 있습니다.

LinkedList는 조회보다 삽입/삭제가 많은 경우에 사용하는 것이 좋습니다.

 

Vector

Vector는 ArrayList와 같이 배열로 만들어진 리스트입니다.

하지만, ArrayList와 다르게, Thread-Safe하여 동기화를 지원합니다.

한번에 하나의 스레드만 접근이 가능하며,

Thread-Safe하여 멀티 스레드 환경에서 사용하기 좋습니다.

하지만 get,put에 모두 synchronized가 있어서, 스레드마다 lock이 걸리게되고 성능은 ArrayList에 비해 안좋다는 단점이 있습니다.

 

Stack

Stack은 LIFO(Last-In-First-Out) 특성을 가지는 자료구조입니다.

마지막에 들어온 원소가 처음으로 나가는 특징을 가집니다.

들어올때는 push, 나갈때는 pop이라는 용어를 사용합니다.

 

Stack은 Vector를 implements 받습니다.

하지만 push()와 pop()은 Stack 클래스 내부에 구현되어 있기 때문에, 이 메소드를 사용하려면 Stack으로 받아야 합니다.

 

Set

집합이라고 부르며, 순서가 없고 원소의 중복을 허용하지 않는다는 특징이 있습니다.

HashSet > LinkedHashSet > TreeSet 순서로 성능의 차이를 보입니다.

 

HashSet

해싱을 이용해 구현합니다.

집합의 특징 때문에 중복을 허용하지 않습니다.

HashSet으로 작성된 데이터는 값을 저장할 때 인스턴스의 해시값을 기준으로 저장하기 때문에 순서대로 저장되지 않습니다.

내부적으로 HashMap을 사용합니다.

 

LinkedHashSet

중복을 허용하지는 않지만, 순서를 가진다는 특징이 있습니다.

입력한 순서대로 데이터를 정렬합니다.

내부적으로 LinkedHashMap을 사용합니다.

 

TreeSet

이진탐색트리의 형태로 데이터를 저장하는 컬렉션입니다.

이진탐색트리 중에서도 성능을 향상시킨 '레드-블랙 트리'로 구현되어있습니다.

따라서 데이터의 추가, 삭제에는 시간이 걸리지만, 검색과 정렬이 뛰어나다는 장점이 있습니다.

중복을 허용하지는 않지만, 오름차순으로 데이터를 정렬합니다.

내부적으로 TreeMap을 사용합니다.

 

Queue

Queue는 FIFO(First-In-First-Out)특성을 가지는 자료구조입니다.

들어올때는 enqueue, 나갈때는 dequeue라고 합니다.

 

PriorityQueue

우선순위를 가지는 Queue로 일반적인 Queue와는 조금 다르게, 원소에 우선순위를 부여하여 높은 순으로 먼저 반환합니다.

이진 트리 구조로 구현되어 있습니다.

 

ArrayDeque

deque는 양쪽으로 넣고 빼는 것이 가능한 큐 자료구조입니다.

Map

Key와 Value로 이루어진 자료구조입니다.

Set과 같이 순서를 가지지 않습니다.

Key 값은 중복될 수 없지만, Value값은 중복 될 수 있습니다.

Map 메소드 중 가장 많이 쓰이는 메소드는 put(), get(), remove()입니다.

 

HashMap

Hashing기법을 사용하므로 많은 양의 데이터중에서 원하는 데이터를 빠르게 가져올 수 있습니다.

Hashing기법이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법입니다.

해시함수는 데이터가 저장되어 있는 곳을 알려주며, 다량의 데이터 중에서 원하는 데이터를 빠르게 찾을 수 있는 특징이 있습니다.

Map의 기본형식입니다. 마치 키를 리스트나 배열에 존재하는 인덱스처럼 가져와 밸류를 뽑기에

시간복잡도가 O(1)입니다.

HashMap<키의 타입, 데이터의 타입> 객체명 = new HashMap<>(배열 수);

put() - 반드시 키값, 데이터 두개의 파라미터를 넘겨 주어야 합니다. put("key", "data")

get() - 저장된 데이터값을 호출합니다. 키값을 넣어줘야합니다. get(key)

remove() - 저장된 데이터를 삭제합니다. 키값을 넣어줘야합니다. remove(key)

 

HashTable

HashMap과 동일한 특징을 가지지만, 차이점이라고 하면 Thread-Safe하여 동기화를 지원합니다.

 

LinkedHashMap

일반적으로 Map 자료구조는 순서를 가지지 않지만, LinkedHashMap은 들어온 순서대로 순서를 가집니다.

 

TreeMap

이진트리로 구성이 되어있고, TreeSet과 같이 정렬하여 데이터를 저장하고 있습니다.

데이터를 저장할때 정렬하기 때문에 저장 시간이 다른 자료구조에 비해 오래 걸립니다.