Array
- 같은 형의 데이터 타입을 메모리에 저장하는 선형적 자료구조
- 논리적 구조와 물리적 구조가 동일 ( 주소가 순서대로 들어있음 )
- fixed-length
- 인덱스 연산 가능 (int일 경우 4바이트씩 차지하기 때문에 n 번째 주소를 찾기 쉽다)
- 중간의 자료를 비울 수 없다. 중간에 비었으면 다시 땡겨야함
- insert / delete가 n에게 dependent 하다
Linked List
- 논리적 구조와 물리적 구조가 동일하지 않음
- fixed-length가 아님
- 자신의 다음 주소를 가리킴
- 인덱스 연산이 힘들기에 맨 첫번째 주소를 찾아야 한다.
Stack
- Array / Linked List 로 구현 가능
- Stack 클래스도 사용 가능
- 데이터의 추가 삭제가 상단 에서만 일어난다.
- LIFO
- 맨 상단에서 넣고 뺀다. (push() / pop())
- peek() 스택에서 제거는 하지 않고 맨 위에 있는 원소를 반환
Queue
- 대기열
- ArrayList, Vector, LinkedList로 구현 가능
- Front와 Rear로 구분되어 있음
- FIFO , 선착순
- 넣을 때는 rear에서 enqueue() 꺼낼 때는 front에서 dequeue()
Tree - Binary Search Tree
- 자식 노드의 수가 최소 2개인 노드
- Parent node, left Child, right Child
- 나를 중심으로 왼쪽에 있는 애들은 모두 작은 수여야 한다.
- 나를 중심으로 오른쪽에 있는 애들은 모든 큰 수여야 한다.
- 중복을 허용하지 않는다.
- 검색 속도의 향상을 위해 사용한다.
- Treeset, TreeMap
Hashing
- 산술 연산을 이용한 검색 방식
- HashMap, HashSet
- Collision 발생
- index = h(key)
- 나머지로 자료 주소값을 계산
컬렉션 프레임워크
- 프로그램 구현에 필요한 자료구조(Data Structure)를 구현해 놓은 라이브러리
- java.util 패키지에 구현되어 있음
- 개발에 소요되는 시간을 절약하면서 최적화된 알고리즘을 사용할 수 있음
- 여러 인터페이스와 구현 클래스의 사용방법을 이해해야 함
Collection 인터페이스
- 하나의 객체를 관리하기 위한 메서드가 선언된 인터페이스
- 하위에 List와 Set이 있다
- 여러 클래스들이 Collection 인터페이스를 구현함
| List 인터페이스 | Set 인터페이스 |
| * 순서가 있는 자료관리 * 중복 허용 * 이 인터페이스를 구현한 클래스는 ArrayList, Vector, LinkedList, Stack, Que 등이 있다. |
* 순서가 정해져 있지 않음 * 중복을 허용하지 않음 * 이 인터페이스를 구현한 클래스는 HashSet, TreeSet 등이 있음 |
Collection 인터페이스에 선언된 주요 메서드
List 인터페이스
- Collection 하위 인터페이스
- 객체의 순서에 따라 저장하고 관리하는데 필요한 메서드가 선언된 인터페이스
- 배열의 기능을 구현하기 위한 인터페이스
- ArrayList, Vector, LinkedList 등이 많이 사용됨
ArrayList와 Vector
- 객체 배열을 구현한 클래스
- Vector는 자바 2부터 제공된 클래스
- 멀티 쓰레드 상에서 리소스에 대한 동기화가 필요한 경우 Vector 사용
- 일반적으로 ArrayList를 더 많이 사용함
- ArrayList에 동기화 기능이 추가되어야 하는 경우
Collections.synchronizedList(new ArrayList<String>());- 동기화(synchronization) : 두 개의 쓰레드가 동시에 하나의 리소스에 접근 할 때 순서를 맞추어 데이터에 오류가 발생하지 않게 함
LinkedList 클래스
- 논리적으로 순차적인 자료구조가 구현된 클래스
- 다음 요소에 대한 참조값을 가지고 있음
- 요소의 추가/삭제 에 드는 비용이 배열보다 적음
Stack과 Queue
- Stack 과 Queue의 기능은 구현된 클래스가 있지만 ArrayList나 LinkedList를 활용하여 사용할 수 있다.
- Stack : Last in First Out (LIFO)
- 맨 마지막에 추가된 요소가 먼저 꺼내지는 자료 구조
- Queue : First in First Out (FIFO)
- 먼저 저장된 자료가 먼저 꺼내지는 선착순 대기열 구조
Iterator 사용하여 순회하기
- Collection의 개체를 순회하는 인터페이스
- iterator() 메서드 호출
Iterator ir = memberArrayList.iterator();- 선언된 메서드
Set 인터페이스
- Collection 하위의 인터페이스
- 중복을 허용하지 않음
- 아이디, 주민번호, 사번 등 유일한 값이나 객체를 관리할 때 사용
- List는 순서 기반의 인터페이스지만, Set은 순서가 없음
- 저장된 순서와 출력순서는 다를 수 있음
- get(i) 메서드가 제공되지 않음
- 아래 캡쳐에서는, HashSet의 id 값이 중복이 허용 된다
- Member 객체와 다르게 String은 클래스에 equals(), hashCode() 메소드가 선언이 되어 중복 체크가 되기 때문
- 중복을 허용하지 않기 위해 Member 클래스에도 equals(), hashCode() 메소드 오버라이딩 해주기
TreeSet 클래스
- 객체의 정렬에 사용되는 클래스
- 중복을 허용하지 않으면서 오름차순이나 내림차순으로 객체를 정렬함
- 내부적으로 이진 검색 트리(binary search tree)로 구현되어 있음
- 이진 검색 트리에 자료가 저장될 때 비교하여 저장될 위치를 정함
- 객체 비교를 위해 Comparable 이나 Comparator 인터페이스를 구현해야함
- String 클래스는 이미 Comparable 인터페이스를 구현해놓았기 때문에 java.lang.Compatable 오류가 발생하지 않음
- 실습에서는 Member 객체를 사용하고 있기 때문에 Member 클래스에서 Comparable 인터페이스를 구현해야 함
Comparable , Comparator 인터페이스
- 정렬 대상이 되는 클래스가 구현해야하는 인터페이스
- Comparable은 compareTo() 메서드 구현
- 매개 변수와 객체 자신(this) 비교
- Comparator은 compare() 메서드 구현
- 두 개의 매개 변수를 비교
- TreeSet 생성자에 Comparator가 구현된 객체를 매개변수로 전달
TreeSet<Member> treeSet = new TreeSet<Member>(new Member());- 일반적으로 Comparable을 더 많이 사용
- 이미 Comparable이 구현된 경우 Comparator를 이용하여 다른 정렬방식을 정의 할 수 있다.
Map 인터페이스
- key - value pair 의 객체를 관리하는데 필요한 메서드가 정의됨
- key는 중복될 수 없음
- 검색을 위한 자료 구조
- key를 이용하여 값을 저장하거나 검색, 삭제 할 때 사용하면 편리함
- 내부적으로 hash 방식으로 구현 됨 index = hash(key)
- key가 되는 객체는 객체의 유일성함의 여부를 알기 위해 equals()와 hashCode() 메서드를 재정의 함
HashMap 클래스
- Map 인터페이스를 구현한 클래스 중 가장 일반적으로 사용하는 클래스
- HashTable 클래스는 자바 2부터 제공된 클래스로 Vector처럼 동기화를 제공
- 여러 메서드를 활용하여 pair 자료를 쉽고 빠르게 관리할 수 있음
- itorator()메서드는 하나의 Collection 객체만을 반환하므로 pair로 이루어진 객체는 각각 순회해야 한다.
public void showAll() {
Iterator<Integer> ir = hashMap.keySet().iterator();
while (ir.hasNext()) {
int key = ir.next();
Member member = hashMap.get(key);
System.out.println(member);
}
}
TreeMap 클래스
- key객체를 정렬하여 key-value pair로 관리하는 클래스
- key에 사용되는 클래스에 Comparable, Comparator 인터페이스를 구현
- java에 많은 클래스들은 이미 Comparable이 구현되어 있음
- 구현된 클래스를 key로 사용하는 경우는 구현할 필요가 없음
public final class Integer extends Number implements Comparable<Integer> {
...
public int compareTo(Interger anotherInteger) {
return compareTo(this.value, anotherInteger.value);
}- TreeMap<Integer, Member> - Integer클래스 내부에 이미 Comparable이 구현되어 있으므로 자동정렬 가능
- 정렬방식을 바꾸고 싶은 경우 재구현 하여 사용
