[Java] Java에서 사용하는 여러 자료구조 정리

제가 주로 코딩 테스트를 C++로 응시하다 보니 C++의 문법에 상당히 익숙해져 있는 상태입니다.

Spring Boot 등의 프레임워크를 이용하는 경우 Java를 쓰게 되는데, 동일한 자료구조를 사용해도 문법이 약간 달라 헷갈리는 경우가 자주 있어 한번 정리해 보고자 만들었습니다.

자료구조 자체에 대한 설명을 하고자 하는 글이 아닌, C++에서 쓰던 자료구조를 Java에서 동일하게 사용하기 쉽도록 정리한 글입니다.

접은글 형식으로 작성하였으니 원하는 부분을 찾기 편리하실 겁니다.

 

Java에서는 데이터 타입에 대해 첫 글자가 대문자로 표기되는 점을 주의하면 됩니다.

 

1. Stack

Stack은 C++와 크게 차이나지 않습니다.

 

import java.util.Stack;	//대문자 주의

Stack<Integer> s1 = new Stack<>();
Stack<String> S2 = new Stack<>();

s1.push(1);				//s1에 값 1을 push
s1.push(2);				//s1에 값 2를 push
s1.pop();				//s1의 최상단 값(2)을 제거함
s1.peek();				//s1의 최상단 값(1)을 참조함
s1.size();				//s1의 크기를 구함
s1.contains(3);				//s1 내부에 3이라는 원소가 있는지 확인; 없으므로 false
s1.clear();				//s1을 전부 비운다.

참고: https://coding-factory.tistory.com/601

 

2. Queue

Queue는 사용되는 용어가 C++와 약간 차이가 있습니다.

 

import java.util.LinkedList;				//Linked List를 꼭 함께 써 주어야 한다.
import java.util.Queue;

Queue<Integer> q1 = new LinkedList<>();
Queue<String> q2 = new LinkedList<>();

q1.add(1);				//q1에 원소 1을 추가
queue.poll();				//q1의 최상단 값(1)을 참조하고 제거
q1.add(1);
q1.add(2);
q1.remove();				//q1의 최상단 값(1)을 제거
q1.peek();				//q1의 최상단 값(2)을 참조
q1.clear();				//q1 초기화

참고: https://coding-factory.tistory.com/602

 

3. Priority Queue

우선순위 큐의 경우 오름차순, 내림차순 등을 제외하면 C++와 유사합니다.

 

import java.util.PriorityQueue;

//int형 pq, 오름차순
PriorityQueue<Integer> pq1 = new PriorityQueue<>();
//int형 pq, 내림차순
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
//string pq, 오름차순
PriorityQueue<String> pqs1 = new PriorityQueue<>();
//string pq, 내림차순
PriorityQueue<String> pqs1 = new PriorityQueue<>(Collections.reverseOrder());

//값 추가
pq1.add(2);
pq1.add(1);
pq1.offer(3);

pq1.poll();				//pq1의 최상단 값(1)을 반환하고 제거
pq1.remove();			//pq1의 최상단 값(2)을 제거
pq1.clear();			//pq1의 모든 값을 제거

참고: https://coding-factory.tistory.com/603 

 

4. Vector

vector는 매우 빈번하게 쓰이므로 알아두면 좋습니다.

 

//선언

Vector v = new Vector();				//타입 미설정 vector
Vector<Student> vecs = new Vector<Student>();		//Student 객체형 vector
Vector<Integer> nums = new Vector<Integer>();		//Integer형 vector
Vector<Integer> nums2 = new Vector<>();			//Integer형 vector, 타입 패러미터 생략
Vector<String> str1 = new Vector<String>(10);		//String형 vector, 초기 크기 설정
Vector<Integer> nums3 = new Vector<Integer>(Arrays.asList(1,2,3));	//Int형 vector, 초기값 설정

//값 추가
nums.add(1);
nums.add(null);				//null값도 add 가능
nums.add(1, 10);			//index 1 뒤에 값 10을 추가

Vector<Student> student = new Student(name, age);
v.add(student);
v.add(new Member("카펀", 27));

//값 제거
nums3.remove(1);			//index 1 제거
nums3.removeAllElements();		//nums3의 모든 값 제거
nums3.clear();				//nums3의 모든 값 제거

//크기 구하기
vector<Integer> vecsize<Integer>(10);
vecsize.add(1);

System.out.println(vecsize.size());	//삽입된 데이터의 개수 1
System.out.println(vecsize.capacity());	//vecsize의 물리적 크기 10

//내용물 출력
vector<Integer> vecprint<Integer>(Arrays.asList(1,2,3));
System.out.println(vecprint.get(0));	//0번째 index 출력

//for문을 이용한 전체출력
for (Integer i : vecprint) {
	System.out.println(i);
}

//iterator를 이용한 출력
Iterator iter = vecprint.iterator();
while(iter.hasNext()) {
	System.out.println(iter.next());
}

 

참고: https://coding-factory.tistory.com/553 

 

5. Set

C++에서는 set, unordered_set이라고 부르는 두 가지가 있습니다.

공통점이라면 key의 중복을 허용하지 않습니다.

차이점으로는 내부 구현 방식에 있는데, set은 tree 기반이므로 삽입, 검색에 O(log N)의 시간복잡도를 요구하며, key가 모두 정렬된 상태입니다.

unordered_set은 hash 기반이므로 삽입, 겁색에 최선의 경우 O(1), 최악의 경우 O(N)의 시간복잡도를 요구하며, key가 정렬되어 있지 않습니다.

 

Java에서는 set을 tree set, unordered_set을 hash set이라고 부릅니다.

 

Tree Set

//선언
Treeset<Integer> tset1 = new Treeset<Integer>();
Treeset<Integer> tset2 = new Treeset<>();				//타입 패러미터 생략 가능
Treeset<Integer> tset3 = new Treeset<Integer>(tset1);			//tset1의 모든 값을 가진 새로운 set
Treeset<Integer> tset4 = new Treeset<Integer>(Arrays.asList(1,2,3));	//초기값

//값 추가
tset1.add(1);
tset1.add(3);
tset1.add(2);

//값 제거
tset1.remove(2);			//값 2 제거
tset1.clear();				//tset1 내의 모든 값 제거

//크기 구하기
System.out.println(tset1.size());

//값 출력
Treeset<Integer> prset = new Treeset<Integer>(Arrays.asList(4,1,5));
System.out.println(prset);			//전체출력: [1, 4, 5]
System.out.println(prset.first());		//최솟값 (1) 출력
System.out.println(prset.last());		//최댓값 (5) 출력
System.out.println(prset.higher(3));		//3보다 큰 데이터중 최솟값 출력; 없으면 null
System.out.println(prset.lower(3));		//3보다 작은 데이터중 최댓값 출력; 없으면 null

//iterator 이용하기
Iterator iter = prset.iterator();
while(iter.hasNext()) {
	System.out.println(iter.next());
}

 

Hash Set

//선언
Hashset<Integer> hset1 = new Hashset<Integer>();
Hashset<Integer> hset2 = new Hashset<>();				//타입 패러미터 생략 가능
Hashset<Integer> hset3 = new Hashset<Integer>(hset1);			//hset1의 모든 값을 가진 새로운 set
Hashset<Integer> hset4 = new Hashset<Integer>(Arrays.asList(1,2,3));	//초기값
Hashset<Integer> hset5 = new Hashset<Integer>(10);			//초기 용량 지정
Hashset<Integer> hset6 = new Hashset<Integer>(10, 0.7f);		//초기 용량, load factor 지정

//값 추가
hset1.add(1);
hset1.add(3);
hset1.add(2);

//값 제거
hset1.remove(2);				//값 2 제거
hset1.clear();					//tset1 내의 모든 값 제거

//크기 구하기
System.out.println(hset1.size());

//값 출력
Treeset<Integer> prset = new Treeset<Integer>(Arrays.asList(4,1,5));
System.out.println(prset);			//전체출력 [4, 1, 5];

//iterator 사용
Iterator iter = prset.iterator();
while(iter.hasNext()) {
	System.out.println(iter.next());
}

//값 검색
System.out.println(prset.contains(1));		//1을 포함하고 있는지 여부를 출력

 

둘 사이에 큰 차이는 없습니다.

Hashset은 저장공간이 부족해지면 list처럼 공간을 늘리는데, 기존 공간의 두 배만큼 늘리게 되며 여기서 과부하가 많이 발생합니다. 따라서 사용할 크기를 미리 알고 있다면 처음에 설정해 주면 좋습니다.

 

참고:

https://coding-factory.tistory.com/555

https://coding-factory.tistory.com/554

 

6. Map

Set과 유사하게, Map의 경우 C++에서는 map, unordered_map으로 나뉘며,

이는 Java에서는 각각 treemap, hashmap으로 나뉩니다.

 

Tree Map

//선언
TreeMap<Integer, Integer> tmap1 = new TreeMap<Integer, Integer>();	//key가 int, value가 int형인 map 선언
Treemap<Integer, String> tmap2 = new TreeMap<>();	//자료형을 생략할 수 있다.
TreeMap<Integer, Integer> tmap3 = new TreeMap<>(tmap1);	//tmap1의 모든 값을 가진 새로운 map 선언
Treemap<Integer, Integer> tmap4 = new TreeMap<>(){{
	put(1, 4);
}};	//초기값 설정: key가 1이고 value가 4인 값을 초기값으로 넣었다.
//treemap은 hashmap과는 다르게 크기를 미리 지정해 줄 수 없습니다.
 
//값 추가
tmap2.put(1, "네이버");
tmap2.put(2, "카카오");
tmap3.put(3, "NHN");

//값 제거
tmap2.remove(2);			//key가 2인 값 제거
tmap2.clear();				//tmap2의 모든 값을 제거

//단일 값 출력
//위의 값 추가를 통해 3개의 key-value 쌍을 넣었다고 가정했을 때,
System.out.println(tmap2);		//tmap2의 모든 값 출력
//{1=네이버, 2=카카오, 3=NHN}
System.out.println(tmap2.get(1));	//key가 1인 값의 value 출력: 네이버
System.out.println(tmap2.firstKey());	//가장 낮은 key를 출력: 1
System.out.println(tmap2.firstEntry());	//가장 낮은 key를 가지는 value를 출력: 네이버
System.out.println(tmap2.lastKey());	//가장 높은 key를 출력: 3
System.out.println(tmap2.lastEntry());	//가장 높은 key를 가지는 value를 출력: NHN

//전체 값 출력
//enterySet() 이용
for (Entry<Integer, String> entry : tmap2.entrySet()) {
	System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
}
//keySet() 이용
for (Integer i : tmap2.keySet()) {
	System.out.println("key: " + i + ", value: " + tmap2.get(i));
}
//위 두 방법 중 데이터가 많을 경우 keySet은 key를 이용해서 value를 매번 찾으므로 entrySet() 이 더 성능이 좋다.

//iterator를 이용하는 방법
//iterator entrySet
Iterator<Entry<Integer, String> > entries = tmap2.entrySet().iterator();
while(entries.hasNext()) {
	Map.Entry<Integer, String> entry = entries.next();
    System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
}
//iterator keySet
Iterator<Integer> keys = tmap2.keySet().iterator();
while(keys.hasNext()) {
	int key = keys.next();
    System.out.println("key: " + key + ", value: " + map.get(key));
}

 

Hash Map

HashMap<String,String> hmap1 = new HashMap<String,String>();	//string형 key, string형 value를 가지는 hashmap 선언
HashMap<Integer,String> hmap2 = new HashMap<>();	//자료형을 생략할 수 있다.
HashMap<String,String> hmap3 = new HashMap<>(hmap1);	//hmap1의 모든 값을 가진 hmap3을 선언
HashMap<String,String> hmap4 = new HashMap<String,String>(){{
    put("a","b");
}};	//초기값으로 key: "a", value: "b"를 가지는 원소를 집어넣는다.
HashMap<String,String> hmap5 = new HashMap<>(10);	//초기 용량 설정
HashMap<String,String> hmap6 = new HashMap<>(10, 0.7f);	//초기 용량 및 load factor 지정
//hashmap은 treemap과 달리 크기를 미리 지정해 주는 것이 좋습니다.
//자세한 내용은 https://d2.naver.com/helloworld/831311 참고

//값 추가
hmap2.put(1, "넥슨");
hmap3.put(3, "크래프톤");
hmap2.put(2, "네오플");
//값 추가는 treemap과 차이가 없습니다.

//값 삭제
hmap2.remove(3);	//key값이 3인 원소 (3, "크래프톤") 제거
hmap2.clear();		//hmap2의 모든 원소 제거

//값 출력
//hmap2 내의 값은 값 추가 부분에서 추가한 3개의 값이라고 가정
System.out.println(hmap2);
//전체 출력: {1:=넥슨, 3=크래프톤, 2=네오플}
//entrySet() 활용
for (Entry<Integer, String> entry: hmap2.entrySet()) {
	System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
}
//keySet() 활용
for (Integer i : hmap2.keySet()) {
	System.out.println("key: " + i + ", value: " + hmap2.get(i));
}

//iterator 사용
//iterator entrySet
Iterator<Entry<Integer, String> > entries = hmap2.entrySet().iterator();
while(entries.hasNext()) {
	Map.Entry<Integer, String> entry = entries.next();
	System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
}
//iterator keySet
Iterator<Integer> keys = hmap2.keySet().iterator();
while(keys.hasNext()) {
	int key = keys.next();
    System.out.println("key: " + key + ", value: " + hmap2.get(key));
}

 

참고:

https://coding-factory.tistory.com/557

https://coding-factory.tistory.com/556

https://d2.naver.com/helloworld/831311

 

 

이 외에 참고하면 좋을 내용입니다:

• linked list: https://coding-factory.tistory.com/552
• array list: https://coding-factory.tistory.com/551