[Java] - 자바의 자료구조(1)
JCF(Java Collection Framework)
Collection 인터페이스
1. Iterable/Iterator 인터페이스
- Iterable :
ㄴ public Iterator iterator(); Iterator 인터페이스를 반환하는 메소드 - Iterator :
ㄴ public boolean hasNext(); / public E next(); /public remove();
Collection은 Iterable 인터페이스를 상속받고 List, Set을 구현하는 클래스에서 위의 메소드를 구현하여 데이터를 저장, 삭제하게 된다.
2. 저장 가능한 데이터 타입
Collection은 기본 데이터형이 아닌 참조 데이터형만 저장이 가능하므로 Object 타입의 객체로 저장해야 한다.
기본 데이터형은 Wrapper 클래스를 사용하여 저장하도록 한다.
List 인터페이스
- 동일한 데이터의 중복을 허용한다
- 데이터 저장 순서가 유지된다 (주의 - 인덱스가 유지되는 것이 아님)
- 객체를 인덱스로 관리하기 때문에 저장하면 자동으로 인덱스가 부여되고 인덱스를 활용하여 객체를 검색, 삭제할 수 있다
- 이때 List 컬렉션은 객체 자체를 저장하여 인덱스를 부여하는 것이 아니라 해당 인덱스에 있는 객체의 주소값을 참조하여 저장한다
- List 컬렉션에서 공통적으로 사용가능한 추가, 검색, 삭제 메소드를 가지고 있다
1. LinkedList
LinkedList 클래스는 List 및 Deque 인터페이스의 이중연결 리스트를 구현한 것이다. - 데이터의 삽입 삭제에 유리
이중연결 리스트란 단순연결 리스트 구조에서 바로 이전 노드를 가리키는 pre 포인터가 추가된 구조이다.
또한 비동기식이므로 여러 스레드가 동시에 LinkedList로 동작할 수 있다.
LinkedList 클래스는 내부적으로 연결 리스트를 이용하여 요소를 저장한다.
2. ArrayList
마찬가지로 인덱스로 관리된다.
일반 배열과 비슷하지만 초기화 시 크기를 고정시키지 않아도 된다.
3. Vector
ArrayList와 동일한 내부 구조를 가지고 있다.
ArrayList와 다르게 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 메소드들을 실행할 수 없다
4. Stack
List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공한다.
스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 LIFO의 구조를 따른다.
Stack 클래스는 스택 메모리 구조를 표현하기 위해, Vector 클래스의 메서드를 5개만 상속받아 사용한다.
boolean empty(); // 해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
E peek(); // 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환함.
E pop(); // 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거함.
E push(E item); // 해당 스택의 제일 상단에 전달된 요소를 삽입함.
int search(Object o); // 해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환함. 이때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함.
Set 인터페이스
- 저장 순서가 보장되지 않는다 - 인덱스 없음
- Data를 중복해서 포함할 수 없다 ★★
1. HashSet
순서가 필요없는 데이터를 hash table에 저장한다. Set 인터페이스를 구현한 클래스 중 가장 성능이 좋다.
데이터를 가져오려면 iterator 를 이용하면 된다.
Iterator<String> it = set.iterator(); // Iterator(반복자) 생성
while (it.hasNext()) { // hasNext() : 데이터가 있으면 true 없으면 false
System.out.println(it.next()); // next() : 다음 데이터 리턴
}
2. TreeSet
Set 인터페이스를 상속한 SortedSet 인터페이스를 구현한 클래스
데이터들이 자동으로 오름차순으로 정렬된다
3. LinkedHashSet
중복된 데이터를 제외하고 입력된 순서대로 데이터를 저장한다
Sorted 인터페이스
Set과 Map 인터페이스를 상속받아 정렬 기능이 추가된 SortedSet과 SortedMap 인터페이스가 된다.
그리고 이들은 각각 TreeSet 클래스와 TreeMap 클래스로 구성된다.
- Sorted를 지원하지 않는 클래스 - HashSet, HashMap
- Sorted를 지원하는 클래스 - TreeSet, TreeMap