Java의 참조자료형 : Map,Set,Queue,Stack,Deque

Map

키와 값의 쌍으로 이루어진 데이터를 저장하는 자료구조

순차적으로 요소의 값을 구하지 않고 키 값을 통해 값을 구함

Map 인터페이스를 구현한 자료형에는 HashMap, LinkedHashMap, TreeMap 등이 있음

특징

키의 중복이 불가능

순서가없음

• LinkedHashMap은 삽입된 순서 보장, TreeMap은 정렬된 채 삽입

검색 속도가 복잡도 O(1)로 굉장히 빠르다

주요메서드

• containsKey
• key가 있는지 true false반환
• getOrDefault
• key가 없으면 default값 반환
• putIfAbsent
• key가 맵에 없을 때만 put
• keySet

키를 set형태로 반환

• values

맵에 있는 값 목록을 반환

Set

수학에서의 집합과 유사한 성질을 지닌 자료형

map과 마찬가지로 LinkedHashSet, TreeSet 존재

중복을 제거할 때 일반적으로 사용

집합 관련 함수

• retainAll
• 교집합
• addAll
• 합집합
• removeAll
• 차집합

Queue

가장 먼저 저장된(push) 데이터가 가장 먼저 인출(pop)되는 선입선출(FIFO)의 자료 구조

LinkedList를 통한 선언이 가장 보편적

→ LinkedList는 이중 연결 리스트(doubly linked list)로, 각 노드가 이전 및 다음 노드에 대한 참조를 하므로, 큐의 주요 연산인 삽입(offer)과 삭제(poll)에 있어서 효율적인 성능을 제공

ArrayList와 LinkedList의 차이

• ArrayList는 인덱스를 통한 요소의 접근에 있어서 매우 빠름(O(1)).
• 리스트의 중간에 요소를 추가하거나 제거하는 경우에는 뒤의 요소들을 이동시켜야 하기 때문에 더 많은 시간이 소요(O(n))

Stack

후입선출(LIFO), 즉, 가장 나중에 저장된(push) 데이터가 가장 먼저 인출(pop)되는 자료구조

사용 예시 ) 페이지 뒤로 가기, 괄호 짝 맞추기

효율성 문제로 deque를 사용하길 권장

Deque

양방향 큐(Double Ended Queue)를 의미

양쪽 끝에서 요소의 추가와 삭제가 가능한 자료구조

ArrayDeque를 사용해 선언

stack과 queued의 결합으로 성능이 더 좋음