12장. 자료구조로 사용되는 클래스 자료구조란? 자료구조 클래스의 사용방법.

Presentation on theme: "12장. 자료구조로 사용되는 클래스 자료구조란? 자료구조 클래스의 사용방법."— Presentation transcript:

1 12장. 자료구조로 사용되는 클래스 자료구조란? 자료구조 클래스의 사용방법

2 12.1 자료구조 자료구조 자료구조 종류 데이터를 효율적으로 사용할 수 있도록 만들어진 구조.
데이터 추가, 삭제, 검색의 효율성을 제공 자료구조 종류 리스트(List) : 데이터를 1차원으로 늘어놓은 형태의 자료구조. - 배열리스트, 연결리스트 스택(Stack) : 마지막에 넣은 데이터부터 순서대로 꺼낼 수 있는 자 료구조. 큐(Queue) : 입력된 순서대로 데이터를 꺼낼 수 있는 자료구조. 해쉬테이블(Hash table) : 키(key)를 이용해서 데이터를 검색하는 자료구조. 집합(Set) : 키(key)를 이용해서 데이터를 검색하는 구조이긴 하나 데이터를 중복 저장하지 않는 자료구조.

3 12.2 자료구조 클래스들 자료구조 클래스 이름 리스트 ArrayList LinkedList 스택 LinkedList 큐
해쉬 테이블 HashMap 집합 HashSet

4 12.3 Collection과 Map

5 12.3.1 배열의 발전된 형태 배열의 발전된 모델 배열과 컬렉션이나 맵계열의 클래스와의 차이점
컬렉션(Collection)과 맵(Map) 계열의 클래스 배열과 컬렉션이나 맵계열의 클래스와의 차이점 배열은 크기를 동적으로 늘릴 수 없지만 컬렉션이나 맵 계열의 클래스는 동적으로 메모리를 확장할 수 있다. Collection류와 Map류의 클래스 자료구조적인 기능의 클래스 Collection과 Map 인터페이스 Collection과 Map은 인터페이스이기 때문에 메서드의 프로토타입만 존재한다. Collection을 구현해서 사용하면 집합적인 저장공간으로서의 기능을 구현한 클래 스가 된다. Map을 구현해서 사용하면 검색적인 저장공간으로서의 기능을 구현한 클래스가 된 다. 5

6 12.3.2 Collection과 Map의 상속구조 Collection Set List Map HashSet TreeSet
Stack Vector ArrayList LinkedList SortedMap Hashtable HashMap TreeMap SortedSet 키와 값으로 데이터 핸들 순서나 집합적인 저장공간 순서가 있는 저장 공간 집합적인 저장 공간 동기화 보장하는 Map 계열의 클래스 동기화 보장하지 않는 Map 계열의 클래스 정렬을 위한 Map 계열의 클래스 정렬을 위한 Set 계열의 클래스 동기화 보장 동기화 보장하지 않음 스택자료구조 링크드리스트 Set계열의 대표클래스 6

7 12.3.3 Collection 인터페이스 Collection 인테페이스의 특징
이것을 구현한 클래스들은 모두 집합적인 저장공간으로서의 기능을 가진다. Collection 인터페이스를 구현하고 있는 클래스 Stack, Vector, LinkedList, TreeSet, HashSet Collection 인터페이스의 추상 메서드 Java 1.4 Java 1.5 (5.0) 설 명 boolean add(Object o) boolean add(E o) 객체를 삽입하는 메서드 boolean remove(Object o) 특정 객체를 삭제하는 메서드 boolean isEmpty() 비어 있는지 확인하는 메서드 boolean contains(Object o) 특정 객체가 포함되어 있는지 확인하는 메서드 int size(); 포함된 객체의 수를 리턴하는 메서드 Object[] toArray() T[] toArray() 포함된 모든 객체들을 배열 형태로 리턴 하는 메서드 7

8 12.3.4 Map 인터페이스 Map 인터페이스의 특징 Map으로 구현된 클래스 Map 인터페이스의 추상 메서드
Collection과 달리 Map은 검색적인 개념을 담고 있는 인터페이스 Map으로 구현된 클래스 Attributes, HashMap, Hashtable, TreeMap Map 인터페이스의 추상 메서드 Java 1.4 Java 1.5 (5.0) 설 명 Object put(Object key, Object value) V put(V key, V value) 데이터를 삽입하는 메서드 Object remove(Object key) 키(key)를 이용해서 데이터를 제거하는 메서드 Object get(Object key) 키(key)를 이용해서 데이터를 검색하는 메서드 boolean isEmpty() 비어 있는지 확인하는 메서드 boolean containsKey(Object key) 특정 키가 있는지 확인하는 메서드 boolean containsValue(Object value) 특정 데이터가 있는지 확인하는 메서드 int size() 포함된 객체가 몇 개인지 확인하는 메서드 8

9 12.4. 컬렉션 클래스 비교

10 12.4.1 Vector와 ArrayList의 비교 Vector와 ArrayList의 공통점
순서가 있는 Collection이다. List 인터페이스를 구현하고 있다. 데이터를 중복해서 포함할 수 있다. Vector와 ArrayList의 차이점 Vector는 자동으로 동기화를 보장해준다. ArrayList는 동기화를 보장해주지 않는다. ArrayList의 동기화 지원 방법 List list = Collections.synchronizedList(new ArrayList(...)); Vector와 ArrayList의 기능 ArrayList는 배열에 동적 메모리 증가 기능을 구현한 클래스이다. Vector는 ArrayList에 동기화가 보장되도록 최적화한 클래스이다. Collection List Stack Vector ArrayList LinkedList 동기화보장 동기화보장하지 않음 10

11 12.4.2 Hashtable, HashMap의 비교 Hashtable, HashMap의 공통점
키(Key)와 값(Value)을 이용해서 데이터를 관리한다. Hashtable과 HashMap Hashtable은 동기화가 보장 되지만 HashMap은 동기화가 보장되지 않는 다. HashMap의 동기화 지원 방법 Map m = Collections.synchronizedMap(new HashMap(...)); Hashtable, HashMap과 HashSet과의 관계 Hashtable과 HashMap은 둘다 Map 인터페이스를 구현하고 있다. HashSet은 내부적으로 Hash기법을 사용하지만 Set 인터페이스를 구현하 고 있다. Map SortedMap Hashtable HashMap 동기화보장 동기화보장하지 않음 11

12 12.4.3 ArrayList와 HashSet의 비교
객체의 저장공간이다. 동기화를 보장하지 않는다. ArrayList와 HashSet의 차이점 ArrayList List 인터페이스를 구현하는 클래스이다. 순서의 개념이 있다. 데이터의 중복을 허용한다. HashSet Set 인터페이스를 구현하는 클래스이다. 순서의 개념이 아니라 집합의 개념이 있다. 데이터의 중복을 허용하지 않는다. ArrayList와 HashSet의 기능 순서가 중요한 의미를 가진다면 ArrayList를, 순서는 중요하지 않고 데이 터가 중복되지 않기를 원한다면 HashSet을 이용하면 된다. Collection Set List HashSet Stack Vector ArrayList LinkedList SortedSet 순서의개념, 중복허용 집합의개념, 중복불허 12

13 12.5 Collection 계열 클래스 구현

14 12.5.1 Stack import java.util.*; public class StackMain{
public static void main(String[] args) { Stack<String> stack = new Stack<String>(); System.out.println(stack.empty()); stack.push(new String(“홍길동")); stack.push(new String(“성춘향")); stack.push(new String(“이몽룡")); System.out.println(stack.peek()); System.out.println(stack.pop()); System.out.println(stack.search(“이산")); } Collection List Stack Vector ArrayList LinkedList 14

15 12.5.2 ArrayList import java.util.*; public class ArrayListMain{
public static void main(String args[]) { ArrayList<String> list = new ArrayList<String>(); list.add("홍길동"); list.add("김삿갓"); list.add("이몽룡"); list.add("성춘향"); list.add("변사또"); System.out.println(list); System.out.println("Index 2 : " + list.get(2)); System.out.println("Index 0 : " + list.get(0)); String[] arList = new String[list.size()]; list.toArray(arList); System.out.println("Index 1 : " + arList[1]); System.out.println("Index 3 : " + arList[3]); } Collection List Stack Vector ArrayList LinkedList 15

16 12.5.3 HashSet HashSet Collection Set SortedSet import java.util.*;
public class HashSetMain{ public static void main(String args[]) { Set<String> set = new HashSet<String>(); set.add("김삿갓"); set.add("홍길동"); set.add("춘향이"); set.add("이도령"); set.add("향단이"); System.out.println("HashSet : " + set); set.remove("이도령"); System.out.println(set.contains("홍길동")); Iterator<String> iter = set.iterator(); while(iter.hasNext()){ String temp = iter.next(); System.out.print(temp + ", "); } System.out.println(); } } Collection Set HashSet SortedSet 16

17 12.5.4 Vector I Vector v에 데이터가 삽입된 순서 Vector v = new Vector();
public class VectorMain { public static void main(String[] args) { Vector<String> v = new Vector<String>(); //Vector 객체 생성 System.out.println("Vector 생성 직후의 size : " + v.size()); v.addElement(new String("망아지")); v.addElement(new String("송아지")); v.addElement(new String("강아지")); v.addElement(new String("병아리")); System.out.println("Vector에 데이터 삽입 후의 size : " + v.size()); for(int i=0; i< v.size(); i++){ String temp = v.elementAt(i); System.out.println("Vector v의 " + i + "번째 :" + temp); } Collection List Stack Vector ArrayList LinkedList new String("망아지") new String(”송아지") new String(”강아지") new String(”병아리") 인덱스 : 0 인덱스 : 1 인덱스 : 2 인덱스 : 3 Vector v에 데이터가 삽입된 순서 Vector v = new Vector(); v.addElement(new String("강아지")); v.addElement(new String("병아리")); v.addElement(new String(”망아지")); v.addElement(new String("송아지")); 17

18 Vector II Vector<Object> v = new Vector<Object>(); //객체 생성 v.addElement(new Character('A')); //Wrapper 클래스의 사용 v.addElement(new String("굼뱅이")); v.addElement(new Integer(100)); //Wrapper 클래스의 사용 v.addElement(new Integer(200)); //Wrapper 클래스의 사용 System.out.println("Vector의 size():" + v.size()); v.insertElementAt(new Float( ), 1); System.out.println("insertElementAt()-size():" + v.size()); v.setElementAt("Hello", 3); System.out.println("setElement()-size():" + v.size()); System.out.println("v의0번째:" + (Character)v.elementAt(0)); System.out.println("v의1번째:" + (Float)v.elementAt(1)); System.out.println("v의2번째:" + (String)v.elementAt(2)); System.out.println("v의3번째:" + (String)v.elementAt(3)); System.out.println("v의4번째:" + (Integer)v.elementAt(4)); if(v.contains("Hello")){ //데이터가 있는지 확인 int find = v.indexOf("Hello"); //데이터 위치 확인 //위치(인덱스)를 이용한 데이터의 추출 System.out.println("v의" + find + "번째:" + (String)v.elementAt(find)); } Vector v에 객체삽입 1번째에 중간삽입, 1번째에 있던 데이터는 2번째가 된다. 3번째 존재하는 데이터를 수정 삽입한 데이터 타입이 다르기 때문에 하나씩 추출한 뒤 형변환 후 사용 "Hello" 검색 18

19 12.5.6 AutoBoxing(자바 5.0) 자바 1.4까지 자바 5.0 이후
Vector v = new Vector(); //객체 생성 v.addElement(new Integer(100)); //Wrapper 클래스의 사용 v.addElement(new Integer(200)); //Wrapper 클래스의 사용 Integer t0 = (Integer)v.elementAt(0); Integer t1 = (Integer)v.elementAt(1); 자바 5.0 이후 Vector<Integer> v = new Vector<Integer>(); v.addElement(100); //AutoBoxing 발생 v.addElement(200); //AutoBoxing 발생 int a0 = v.elementAt(0);//AutoUnBoxing 발생 int a1 = v.elementAt(1);//AutoUnBoxing 발생 자바 5.0 이상에서는 컴파일러가 내부에서 자동으로 객체를 적절한 상수값으로 변경시켜 준다. 자바 5.0 이상에서는 컴파일러가 내부에서 자동으로 Wrapper 클래스의 객체로 변경시켜 준다. 19

20 12.6 Map 계열 클래스

21 12.6.1 HashMap Map SortedMap Hashtable HashMap import java.util.*;
public class HashMapMain{ public static void main(String args[]) { Map<String, Integer> map = new HashMap<String, Integer>(); map.put("홍길동", new Integer(1)); map.put("김삿갓", new Integer(2)); map.put("이도령", new Integer(3)); map.put("춘향이", new Integer(4)); map.put("향단이", new Integer(5)); System.out.println(map.get("홍길동")); System.out.println(map.get("김삿갓")); System.out.println(map.get("이도령")); System.out.println(map.get("춘향이")); System.out.println(map.get("향단이")); } Key Value Map SortedMap Hashtable HashMap 21

22 12.6.2 Hashtable Map SortedMap Hashtable HashMap
import java.util.Hashtable; public class HashtableMain { public static void main(String[] args) { Hashtable<String, Object> h = new Hashtable<String, Object>(); //Hashtable에 키와 데이터의 삽입 h.put("Name", new String("홍길동")); h.put("Age", new Integer(27)); h.put("Tel", new String(" ")); h.put("Handphone", new String(" ")); h.put("Etc", new String("I'm a boy")); //키 값을 이용해서 객체 추출 String name = (String)h.get("Name"); Integer age = (Integer)h.get("Age"); } Key Value Map SortedMap Hashtable HashMap 22

23 12.7 Enumeration 과 Iterator

24 12.7.1 컬렉션 검색 컬렉션 검색을 위한 인터페이스 Enumeration과 Iterator
Advanaced for(foreach) Enumeration과 Iterator의 특징 데이터의 마지막에 상관하지 않고 모든 데이터에 접근할 수 있다. Iterator는 자바 1.2에서 제공, Enumeration의 대체용 컬렉션 검색을 위한 제어문(자바 5.0) Advanced for(일명 for each) 자바 5.0에 새롭게 추가된 컬렉션을 위한 반복 제어문 데이터의 마지막에 상관하지 않고 검색하기 위한 제어문 Advanced for의 예 String[] ar = new String[]{"안녕1", "안녕2", "안녕3"}; for (String tmp : ar ){ System.out.println( tmp ); } 24

25 12.7.2 Vector에서의 Enumeration
Enumeration 키를 움직이는 방법 4 3 6 5 실제 데이터 첫위치는 어떠한 데이터도 가르키지 않는다. hasMoreElements() nextElement() true 1 2 nextElement() 할 때마다 키가 움직임 nextElement()는 데이터가 있는지 확인한 후 사용 데이터가 있는지 확인 데이가 있는지 확인할 때 hasMoreElements() 사용 Vector 생성과 데이터 삽입 Vector<String> v = new Vector<String>(); v.addElement(new String("망아지")); v.addElement(new String("송아지")); v.addElement(new String("강아지")); v.addElement(new String("병아리")); Enumeration 얻어내기 Enumeration<String> en = v.elements(); Enumeration을 이용해서 전체 데이터 추출 while(en.hasMoreElements()){ String temp = en.nextElement(); System.out.println(temp); } 25

26 12.7.3 Hashtable에서의 Enumeration
Hashtable<String, String> h = new Hashtable<String, String>(); h.put("1", new String("홍길동")); h.put("2", new String("안녕하세요")); h.put("3", new String(" ")); h.put("4", new String(" ")); Enumeration 얻기 Enumeration en = h.elements(); Hashtable의 값(Value)을 Enumeration 얻기 Enumeration<String> en = h.elements(); while(en.hasMoreElements()){ //데이터 얻기(다운캐스팅 필요) String temp = en.nextElement(); System.out.println(temp); } Hashtable의 키(Key)에 해당하는 Enumeration 얻기 Enumeration<String> en2 = h.keys(); while(en2.hasMoreElements()){ String temp = en2.nextElement(); 26

27 12.7.4 Iterator(자바 1.2) Vector의 Iterator Hashtable의 Iterator
Vector<String> v = new Vector<String>(); v.addElement(new String("망아지")); v.addElement(new String("송아지")); v.addElement(new String("강아지")); v.addElement(new String("병아리")); Iterator<String> iter = v.iterator(); while(iter.hasNext()){ String temp = iter.next(); System.out.println(temp); } Hashtable의 Iterator Hashtable<String,String> h = new Hashtable<String,String>(); h.put("1", new String("홍길동")); h.put("2", new String("안녕하세요")); h.put("3", new String(" ")); h.put("4", new String(" ")); Iterator<String> iter2 = h.values().iterator(); while(iter2.hasNext()){ String temp = iter2.next(); 27

28 12.7.5 Enumeration과 Iterator의 차이
Fail-Fast 방식 Iterator를 이용해서 순차적으로 접근하고 있는 도중 다른 곳에서 해당 컬렉션에 데이터 를 추가하거나 삭제하는 등의 작업이 일어난다면 ConcurrentModificationException이 발생하게 하는 방식 자바 1.2부터 지원 Enumeration은 컬렉션의 집합을 통째로 복사해서(SnapShot) 사용하기 때문에 Fail-Fast 를 지원하지 않는다. Enumeration과 Iterator의 차이점 메서드의 이름이 다르다 hasMoreElements()가 hasNext()로 대체 nextElement()가 next()로 대체 Iterator는 remove() 메서드를 제공한다. Fail-Fast 지원 여부 Iterator는 Fail-Fast방식을 지원한다. Enumeration은 Fail-Fast 방식을 지원하지 않는다. 대체적으로 Enumeration보다는 Iterator를 사용하기를 권장한다. 28

29 12.7.6 for each 문(자바 5.0)의 예 import java.util.*;
public class ForEachMain{ public static void main(String[] args){ ArrayList<String> ar = new ArrayList<String>(); ar.add("안녕1"); ar.add("안녕2"); ar.add("안녕3"); //1. 일반적인 For문 for (Iterator<String> i = ar.iterator(); i.hasNext(); ) { String tmp = i.next(); System.out.println(tmp); } //2. For Each문 Java SE 5.0의 코드 for (String tmp : ar){ 29