어서와 Java 는처음이지! 제 15 장컬렉션
컬렉션 (collection) 은자바에서자료구조를구현한클래스 자료구조로는리스트 (list), 스택 (stack), 큐 (queue), 집합 (set), 해쉬테이블 (hash table) 등이있다.
자바는컬렉션인터페이스와컬렉션클래스로나누어서제공한다. 자바에서는컬렉션인터페이스를구현한클래스도함께제공하므로이것을간단하게사용할수도있고아니면각자필요에맞추어인터페이스를자신의클래스로구현할수도있다.
집합 (Set) 은원소의중복을허용하지않는다.
HashSet HashSet 은해쉬테이블에원소를저장하기때문에성능면에서가장우수하다. 하지만원소들의순서가일정하지않은단점이있다. TreeSet 레드 - 블랙트리 (red-black tree) 에원소를저장한다. 따라서값에따라서순서가결정되며하지만 HashSet 보다는느리다. LinkedHashSet 해쉬테이블과연결리스트를결합한것으로원소들의순서는삽입되었던순서와같다.
import java.util.*; public class SetTest { x public static void main(string args[]) { HashSet<String> set = new HashSet<String>(); set.add("milk"); set.add("bread"); set.add("butter"); set.add("cheese"); set.add("ham"); set.add("ham"); System.out.println(set); [Bread, Milk, Butter, Ham, Cheese]
import java.util.*; public class FindDupplication { public static void main(string[] args) { Set<String> s = new HashSet<String>(); String[] sample = { " 단어 ", " 중복 ", " 구절 ", " 중복 " ; for (String a : sample) if (!s.add(a)) System.out.println(" 중복된단어 " + a); System.out.println(s.size() + " 중복되지않은단어 : " + s); 중복된단어중복 3 중복되지않은단어 : [ 중복, 구절, 단어 ]
s1.containsall(s2) 만약 s2 가 s1 의부분집합이면참이다. s1.addall(s2) s1 을 s1 과 s2 의합집합으로만든다. s1.retainall(s2) s1 을 s1 과 s2 의교집합으로만든다. s1.removeall(s2) s1 을 s1 과 s2 의차집합으로만든다.
public class SetTest1 { public static void main(string[] args) { 합집합 [D, A, B, C] 교집합 [A] Set<String> s1 = new HashSet<String>(); Set<String> s2 = new HashSet<String>(); s1.add("a"); s1.add("b"); s1.add("c"); s2.add("a"); s2.add("d"); Set<String> union = new HashSet<String>(s1); union.addall(s2); Set<String> intersection = new HashSet<String>(s1); intersection.retainall(s2); System.out.println(" 합집합 " + union); System.out.println(" 교집합 " + intersection);
리스트 (List) 는순서를가지는요소들의모임으로중복된요소를가질수있다.
ArrayList 를배열 (Array) 의향상된버전또는가변크기의배열이라고생각하면된다. ArrayList 의생성 ArrayList<String> list = new ArrayList<String>(); 원소추가 list.add( "MILK" ); list.add( "BREAD" ); list.add( "BUTTER" );
ArrayList<String> list = new ArrayList<String>(); list.add( "MILK" ); list.add( "BREAD" ); list.add( "BUTTER" ); list.add( 1, "APPLE" ); // 인덱스 1 에 "APPLE" 을삽입 list.set( 2, "GRAPE" ); // 인덱스 2 의원소를 "GRAPE" 로대체 list.remove( 3 ); // 인덱스 3 의원소를삭제한다.
빈번하게삽입과삭제가일어나는경우에사용
import java.util.*; public class LinkedListTest { public static void main(string args[]) { LinkedList<String> list = new LinkedList<String>(); list.add("milk"); list.add("bread"); list.add("butter"); list.add(1, "APPLE"); list.set(2, "GRAPE"); // 인덱스 1에 APPLE" 을삽입 // 인덱스 2의원소를 GRAPE" 로대체 list.remove(3); // 인덱스 3 의원소를삭제한다. for (int i = 0; i < list.size(); i++) System.out.println(list.get(i));
ArrayList<String> list = new ArrayList<String>(); list.add(" 하나 ); list.add(" 둘 ); list.add(" 셋 ); list.add(" 넷 ); String s; Iterator e = list.iterator(); while(e.hasnext()) { s = (String)e.next(); // 반복자는 Object 타입을반환! System.out.println(s); MILK APPLE GRAPE
List<String> list = Arrays.asList(new String[size]); 일반적인배열을리스트로변환한다.
큐는후단 (tail) 에서원소를추가하고전단 (head) 에서원소를삭제한다.
import java.util.*; public class QueueTest { public static void main(string[] args) throws InterruptedException { int time = 10; Queue<Integer> queue = new LinkedList<Integer>(); for (int i = time; i >= 0; i--) queue.add(i); while (!queue.isempty()) { System.out.print(queue.remove()+" "); Thread.sleep(1000); // 현재의스레드를 1 초간재운다. 10 9 8 7 6 5 4 3 2 1 0
우선순위큐는원소들이무작위로삽입되었더라도정렬된상태로원소들을추출한다. 즉 remove() 를호출할때마다가장작은원소가추출된다. 우선순위큐는히프 (heap) 라고하는자료구조를내부적으로사용한다.
import java.util.*; public class PriorityQueueTest { public static void main(string[] args) { PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); pq.add(30); pq.add(80); pq.add(20); for (Integer o : pq) System.out.println(o); System.out.println(" 원소삭제 "); while (!pq.isempty()) System.out.println(pq.remove()); 20 80 30 원소삭제 20 30 80
Map 은많은데이터중에서원하는데이터를빠르게찾을수있는자료구조이다. 맵은사전과같은자료구조이다.
import java.util.*; class Student { int number; String name; public Student(int number, String name) { this.number = number; this.name = name; public String tostring() { return name;
public class MapTest { public static void main(string[] args) { Map<String, Student> st = new HashMap<String, Student>(); st.put("20090001", new Student(20090001, " 구준표 ")); st.put("20090002", new Student(20090002, " 금잔디 ")); st.put("20090003", new Student(20090003, " 윤지후 ")); // 모든항목을출력한다. System.out.println(st); // 하나의항목을삭제한다. st.remove("20090002"); // 하나의항목을대치한다. st.put("20090003", new Student(20090003, " 소이정 ")); // 값을참조한다. System.out.println(st.get("20090003")); // 모든항목을방문한다. for (Map.Entry<String, Student> s : st.entryset()) { String key = s.getkey(); Student value = s.getvalue(); System.out.println("key=" + key + ", value=" + value);
{20090001= 구준표, 20090002= 금잔디, 20090003= 윤지후 소이정 key=20090001, value= 구준표 key=20090003, value= 소이정
Collections 클래스는여러유용한알고리즘을구현한메소드들을제공한다. 정렬 (Sorting) 섞기 (Shuffling) 탐색 (Searching)
정렬은데이터를어떤기준에의하여순서대로나열하는것이다.
import java.util.*; public class Sort { public static void main(string[] args) { String[] sample = { "i", "walk", "the", "line" ; List<String> list = Arrays.asList(sample); Collections.sort(list); System.out.println(list); // 배열을리스트로변경 [i, line, the, walk]
탐색이란리스트안에서원하는원소를찾는것이다.
import java.util.*; public class Search { public static void main(string[] args) { int key = 50; List<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < 100; i++) list.add(i); int index = Collections.binarySearch(list,key); System.out.println(" 탐색의반환값 =" + index); 탐색의반환값 =50
여기서는 Map 을사용하여서영어사전을구현하여보자. 사용자가단어를입력하면단어의설명을보여준다. 영어단어를입력하시오 :map 단어의의미는지도영어단어를입력하시오 :school 단어의의미는학교영어단어를입력하시오 :quit
import java.util.*; public class EnglishDic { public static void main(string[] args) { Map<String, String> st = new HashMap<String, String>(); st.put("map", " 지도 "); st.put("java", " 자바 "); st.put("school", " 학교 "); Scanner sc = new Scanner(System.in); do { System.out.print(" 영어단어를입력하시오 :"); String key = sc.next(); if( key.equals("quit") ) break; System.out.println(" 단어의의미는 " + st.get(key)); while(true);