Java Collections Framework(JCF)

Java에서 컬렉션(Collection)이란 데이터의 집합, 그룹을 의미하며,

JCF(Java Collections Framework)는 이러한 자료구조인 컬렉션과, 이를 구현하는 클래스를 정의하는 인터페이스를 제공한다.

다음은 Java 컬렉션 프레임워크의 상속 구조를 나타낸다.

java

Collection 인터페이스는 List, Set, Queue로 크게 3가지 상위 인터페이스로 분류할 수 있다.

그리고 여기에 Map의 경우 Collection 인터페이스를 상속받고 있지 않지만 Collection으로 분류된다.

Collection 인터페이스의 특징

인터페이스	구현클래스	특징
Set	HashSet,TreeSet	순서를 유지하지 않는 데이터의 집합으로 데이터의 중복을 허용하지 않는다.
List	LinkedList,Vector,ArrayList	순서가 있는 데이터의 집합으로 데이터의 중복을 허용한다.
Queue	LinkedList,PriorityQueue	List와 유사
Map	Hashtable,HashMap,TreeMap	키(Key), 값(Value)의 쌍으로 이루어진 데이터으 집합으로,순서는 유지되지 않으며 키(Key)의 중복을 허용하지 않으나 값(Value)의 중복은 허용한다.

Set 인터페이스

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

import java.util.HashSet;
import java.util.Set;

public class SetExample {
	public static void main(String[] args) {
		
		Set set = new HashSet();
		
		set.add("three");
		set.add("one");
		set.add("two");
		set.add("four");
		set.add("five");
		//Byte, Short, Integer, Long
		//Float, Double, Boolean, Character
		set.add(new Integer(4));
		
		//추가되지 않을 경우(이미 있을 경우)false반환
		boolean isAdded = set.add("five");
		
		System.out.println(set); 
		//배열이라면 주소값이 출력될 것
		//Set은 순서가 없음
		
		System.out.println(isAdded); //false
		System.out.println(set.size());
		
		set.remove("two");
		System.out.println(set);
		
		set.clear();
		System.out.println(set);
		
		if (set.isEmpty()) {
			System.out.println("set is Empty");
		}	
	}
}

HashSet

가장빠른 임의 접근 속도
순서를 예측할 수 없음

public class HashSetExample {
	public static void main(String[] args) {
		
		//만들때 <Integer> -> 정수만 넣음
		HashSet<Integer> set = new HashSet<>();
		set.add(4);
		set.add(4);
		//중복을 허용하지 않으므로 4 하나만 들어감
		System.out.println(set);
		System.out.println(set.size());
		
		while(set.size()<6) {
			set.add((int)(Math.random()*45+1));
		}
		System.out.println(set);
		
		HashSet<Person> pset = new HashSet<Person>();
		pset.add(new Person("송민지",20));
		pset.add(new Person("송민지",20));
		System.out.println(pset);
		Person p1 = new Person("송민지",20);
		
		System.out.println(p1.equals(new Person("송민지",20)));
		//p1객체랑 데이터 값이 같기 때문에 true를 반환
		
		System.out.println(pset);
	}
}

package set_;

public class Person {
	public String name;
	public int age;
	
	public Person(String name, int age) {
		this.name =name;
		this.age=age;
	}

	@Override
	public String toString() {
		return "Person [name=" + name + ", age=" + age + "]";
	}

	
	//마우스오른쪽 -> source -> generate hashCode()and equals()
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + age;
		result = prime * result + ((name == null) ? 0 : name.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Person other = (Person) obj;
		if (age != other.age)
			return false;
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}
}

TreeSet

정렬방법을 지정할 수 있음

TreeSet<Integer> set = new TreeSet<>();
		while(set.size()<6) {
			set.add((int)(Math.random()*45+1));
		}
		System.out.println(set);  //순서대로 출력

public class TreeSetExample {

	public static void main(String[] args) {
	
		TreeSet<String> set = new TreeSet<String>();
		set.add("가나");
		set.add("1");
		set.add("나다");
		set.add("나");
		set.add("abc");
		set.add("a");
		set.add("2");
		System.out.println(set);
		
		TreeSet<Person> pset = new TreeSet<>();
		pset.add(new Person("홍길동",20));
		pset.add(new Person("송민지",21));
		pset.add(new Person("김철수",21));
		System.out.println(pset);
	}
}

만일 String 이 아니라 일반 객체가 엘리먼트라면 해당 객체끼리의 비교가 가능해야 함

=> Person 클래스에서 Comparable 인터페이스를 상속받아야 비교가 가능,

그렇지 않으면 아래와 같은 예외가 출력됨

[ Exception in thread "main" java.lang.ClassCastException: set_.Person cannot be cast to java.lang.Comparable ]

public class Person implements Comparable<Person>{
	public String name;
	public int age;
	
	public Person(String name, int age) {
		this.name =name;
		this.age=age;
	}

	@Override
	public String toString() {
		return "Person [name=" + name + ", age=" + age + "]";
	}
	
	@Override
	public int compareTo(Person o) {
		return this.name.compareTo(o.name);
		//return this.age - o.age;  => 나이 순으로 출력
	}
}

※Iterator

Iterator는 한방향으로 움직임
ListIterator는 양방향으로 움직임

public class TreeSetExample {

	public static void main(String[] args) {
	
		TreeSet<String> set = new TreeSet<String>();

		//Iterator : 순차적인
		Iterator<Person> iter = pset.iterator();
		while(iter.hasNext()) {
			Person p = iter.next();
			if(p.name.charAt(0)>'바') {
				System.out.println(p);
			}
		}
		//위와 동일한 결과를 출력하는 향상 for문
		for(Person p : pset) {
			if(p.name.charAt(0)>'바') {
				System.out.println(p);
			}
		}
	}
}

List 인터페이스

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

LinkedList

양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치정보만 수정하면 되기에 유용하다.
스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰인다.

연결리스트는 헤드노드부터 시작하며 하나의 노드는 데이터와 다음 노드에 대한 주소를 가진다.

주소값만 조절하면 되므로 추가, 삭제가 간편하지만 탐색속도는 떨어진다.
메모리 공간의 활용도가 높다

public class LinkedListExample {

	public static void main(String[] args) {
		
		LinkedList<String> list = new LinkedList<String>();
		
		list.add("hello");
		list.add("java");
		list.add("banana");
		list.addFirst("apple");
		list.addLast("zoo");
		
		System.out.println("list data : "+list);

		list.remove(); //head엘리먼트 삭제
		System.out.println("list data after remove() : "+list);
		
		list.remove(2); //2번 인덱스 엘리먼트 삭제
		System.out.println("list data after remove(2) : "+list);
		
		list.set(1, "new element"); //1번째 엘리먼트 변경
		System.out.println("list data after set() : "+list);
		
		String str1 = list.peek(); //첫번째 엘리먼트 조회
		System.out.println("str1 : "+str1);
		System.out.println("list data after peek() : "+list);
	
		String str2 = list.poll(); //첫번째 엘리먼트 조회 후 삭제
		System.out.println("str2 : "+str2);
		System.out.println("list data after poll() : "+list);
	
	}
}

# output
list data : [apple, hello, java, banana, zoo]
list data after remove() : [hello, java, banana, zoo]
list data after remove(2) : [hello, java, zoo]
list data after set() : [hello, new element, zoo]
str1 : hello
list data after peek() : [hello, new element, zoo]
str2 : hello
list data after poll() : [new element, zoo]

※ Queue

queue는 인터페이스 형태로만 구현되어 있음

=> 때문에 Queue를 직간접적으로 구현한 클래스가 많은데, 이 중 LinkedList클래스가 Queue를 구현하는데 가장 많이 쓰임

선입선출(FIFO)의 구조 : 가장 먼저 저장(push)된 데이터가 가장 먼저(pop)나오게 됨

public class PriorityQueueExample {

	public static void main(String[] args) {

		PriorityQueue<Integer> que = new PriorityQueue<Integer>();
		que.add(3); que.add(5);
		que.add(2); que.add(1);
		que.add(4);
		
		while(! que.isEmpty()) {
			System.out.println(que.poll());
		}
	}
}

※ Stack

stack은 List컬렉션 클래스의 Vector클래스를 상속받아 구현되어 있음 -> List가 보유한 메서드도 사용 가능
선입후출(LIFO) : 가장 나중에 저장된(push) 데이터가 가장 먼저(pop) 나옴
스택은 인터넷 브라우저 히스토리 방식이라고 생각하면 쉬움

public class StackExample {

	public static void main(String[] args) {
		//스택(Stack) -> 선입후출: First In Last Out
		Stack<Integer> stack = new Stack<Integer>();
		stack.add(1);  stack.push(4);
		stack.push(5); stack.add(2);
		stack.push(3);
		
		while(stack.size()>0) {
			System.out.println(stack.pop());
		}
		
		//브라우저 히스토리
		Stack<String> history = new Stack<>();
		history.add("네이버"); history.add("네이버웹툰"); 
		history.add("목요웹툰"); history.add("연애혁명");
		history.add("연애혁명1화"); 
		
		while(history.size()>0) {
			System.out.println(history.pop()); //가장 나중에 들어온게 가장 먼저 나감
		}
	}
}

※ Collections 메서드

shuffle(List list)
sort(List list)
reverseOrder()

public class CollectionsExample {

	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int i=0;i<=45;i++) {
			list.add(i);
		}
		
		System.out.println(list);
		
		Collections.shuffle(list);
		System.out.println(list);
		
		Collections.sort(list);
		System.out.println(list);
		
		Collections.sort(list,Collections.reverseOrder());
		System.out.println(list);
	}
}

Vector

과거에 대용량 처리를 위해 사용했으며, 내부에서 자동으로 동기화처리가 일어나 비교적 성능이 좋지 않고 무거워 잘 쓰이지 않음

ArrayList

단방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 조회 기능에 성능이 뛰어남

ArrayList를 이용하면 동적으로 리스트의 크기가 변하고,

다양한 메서드를 통해 간단하게 추가 삭제가 가능

(기존의 배열은 새로운 데이터를 추가, 삭제할 때 뒤의 데이터들도 처리해줘야하므로 불편,

또한 크기를 늘리기 위해서는 배열을 새로 생성해야 함)

public class ArrayListExample {

	public static void main(String[] args) {
		List list = new ArrayList();

		list.add("one");
		boolean a = list.add("second");
		list.add("3rd");
		list.add(new Integer(4));
		list.add(new Float(5.0f));
		
		boolean b = list.add("second");
		list.add(new Integer(4));
		list.add("SECOND");
		
		System.out.println(a);
		System.out.println(b);
		System.out.println(list);
		
		list.remove(0);
		System.out.println(list);

		Object o = list.get(1);
		System.out.println(o);
		
		int i = list.indexOf("second");
		System.out.println("second = "+i);
		
		list.clear();
		if(list.isEmpty()) {
			System.out.println("list is Empty");
		}
	}
}

Map 인터페이스

Map에 있는 하나의 엘리먼트는 key와 value한쌍으로 이루어져 있음
Key/value쌍은 중복될 수 없고 유일해야 함
value는 중복될 수 있지만 key는 유일해야 함
HashMap, TreeMap

키(Key), 값(Value)의 쌍으로 이루어진 데이터으 집합으로,

순서는 유지되지 않으며 키(Key)의 중복을 허용하지 않으나 값(Value)의 중복은 허용한다.

public class HashMapExample {

	public static void main(String[] args) {
		HashMap<String,Integer> map = new HashMap<>();
		         //키   , 값
		map.put("송민지", 20);
		map.put("홍길동", 22);
		map.put("김철수", 23);
		map.put("송구름", 16);
		//값은 중복될 수 있지만 키는 중복X
		System.out.println(map);
		
		System.out.println(map.get("송민지"));

		//map에 저장된 키들을 Set객체로 반환
		Set<String> keyset = map.keySet();
		for(String key : keyset) {    //위의 줄을 생략하고 keyset대신 map.keySet()도 가능
			if(map.get(key)>20)
				System.out.println("키 : "+key+", 값 : "+map.get(key));
		}
		
		System.out.println("================");
		//Map.Entry객체를 엘리먼트로 갖는 Set객체를 반환
		Set<Map.Entry<String, Integer>> entryset = map.entrySet();
		for(Map.Entry<String, Integer> entry : entryset) {
			if(entry.getValue()>20)
			System.out.println("키 : "+entry.getKey()+", 값 : "+entry.getValue());
		}
		
		System.out.println("===================");
		//map이 포함하고 있는 값(Value)을 Collection객체로 반환
		Collection<Integer> values = map.values();
		for(int a :values) {
			System.out.println("값 : "+a);
		}
	}
}

{홍길동=22, 송구름=16, 송민지=20, 김철수=23}
20
키 : 홍길동, 값 : 22
키 : 김철수, 값 : 23
================
키 : 홍길동, 값 : 22
키 : 김철수, 값 : 23
===================
값 : 22
값 : 16
값 : 20
값 : 23

Hashtable

HashMap보다는 느리지만 동기화 지원
null불가

HashMap

중복과 순서가 허용되지 않으며 null값이 올 수 있다.

TreeMap

정렬된 순서대로 키(Key)와 값(Value)을 저장하여 검색이 빠름

코딩테스트 문제 - HashMap 이용

마라톤에 참가한 사람보다 완주한 사람이 항상 한 명 적음
동명이인이 있을 수 있음
완주하지 못한 사람의 이름을 반환하는 코드를 작성하라

import java.util.HashMap;

public class MarathonExample {

	public static void main(String[] args) {
		String[] participant = {"mislav", "ana", "mislav","stanko"};
		String[] completion = {"mislav", "ana","stanko"};
		System.out.println(solution(participant,completion));

	}
	
	public static String solution(String[] participant, String[] completion) {
		HashMap<String, Integer> map = new HashMap<>();
		
		//등장한 횟수
		for(String part : participant) {
			map.put(part,map.getOrDefault(part, 0)+1);
		}
		//System.out.println(map);
		
		for(String com : completion) {
			map.put(com, map.get(com)-1);
		}
		//System.out.println(map);

         //map이 갖고있는 key들을 Set객체로 반환
		for(String key : map.keySet()) {
			if(map.get(key)==1) {
				return key;
			}
		}
		return null; //위의 if문이 실행되지 않을수도 있기때문에 return null;적어주어야함
	}
}

getOrDefault(Object key, Integer defaultValue) : 키와 매핑되는 값이 없으면 기본값을 반환

한 줄 요약

Set — 중복 X, 순서 X. HashSet(빠름·순서없음), TreeSet(정렬). 사용자 객체는 equals/hashCode 또는 Comparable 필요
List — 순서 O, 중복 O. ArrayList(조회 빠름), LinkedList(삽입·삭제 유리)
Queue/Stack — FIFO / LIFO. LinkedList·PriorityQueue·Stack로 구현
Map — key-value, key 중복 X. HashMap(일반), TreeMap(정렬), Hashtable(동기화)

JAVA 자료구조