앞서 배열은 한 번 생성하면 크기를 변경할 수 없고, 항목을 저장, 삭제, 추가하는 메소드가 없기 때문에 직접 인덱스를 사용해야 하는 불편함이 있었다. 이러한 불편함을 해결하기 위해 자바는 컬렉션 프레임 워크를 제공한다.
List 인터페이스
List 컬렉션은 배열과 비슷하게 객체를 인덱스로 관리하는데 저장 용량이 자동으로 증가하고, 객체 저장 시 인덱스가 자동으로 부여되는 차이점이 있다.
List 컬렉션은 객체 자체를 저장하는 것이 아니라 객체의 번지를 참조하여 동일한 객체를 중복 저장할 수 있으며, 이 때 동일한 번지가 참조된다.
구현 클래스로는 ArrayList, Vector, LinkedList 등이 있다.
중복을 허용하면서 저장순서가 유지되는 컬렉션 구현 시 사용
List 인터페이스의 대표적인 구현 클래스로 저장되는 객체 수가 늘어나면 용량이 자동적으로 증가하고 인덱스는 0부터 시작한다.
ArrayList를 생성하기 위해서는 저장할 객체 타입 E 타입 파라미터 자리에 표기하고 기본 생성자를 호출한다. 다음 코드는 String 타입을 저장하는 ArrayList 생성하는 코드이다.
List<String> list = new ArrayList<String>();
ArrayList에 객체 추가 시 0번 인덱스부터 차례로 저장되고, 특정 인덱스의 객체 제거 시 바로 뒤 인덱스부터 마지막 인덱스까지 모두 한 칸씩 당겨진다. 이와 마찬가지로 특정 인덱스에 객체 추가 시 해당 인덱스부터 마지막 인덱스까지 모두 한 칸씩 밀려난다.
그렇기 때문에 빈번한 객체 삭제와 삽입이 일어날 경우 ArrayList를 사용하는 것은 적절하지 않다.
Vector는 ArrayList와 동일한 내부 구조를 가지고 있지만 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 Vector의 메소드들을 실행할 수 없고, 하나의 스레드가 메소드 실행을 완료해야만 다른 스레드가 메소드를 실행할 수 있다. 이는 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있음을 의미하며 스레드에 안전하다고 표현한다.
LinkedList는 데이터와 포인터로 이루어진 노드가 일렬로 이어진 형태의 자료구조로 각 노드의 주소는 연속적이지 않은 특징이 있다. 특정 인덱스의 객체 삽입, 삭제 시 포인터가 가르키는 주소만 달라지기 때문에 빈번한 객체 삽입, 삭제 시 ArrayList보다 좋은 성능을 발휘한다.
Single Linked List (단일 연결리스트)
- 구조
class Node {
Node next; // 다음 요소의 주소 저장
Object obj; // 데이터 저장
}
Doubly Linked List (이중 연결리스트)
class Node {
Node next; // 다음 요소의 주소 저장
Node previous; // 이전 요소의 주소 저장
Object obj; // 데이터 저장
}
Circular Linked List (원형 연결리스트)
- 끝이 없고 원형으로 순환하는 형태
Set 인터페이스
Set 컬렉션은 List 컬렉션과 달리 중복을 허용하지 않고 저장순서가 유지되지 않는다. Set 컬렉션은 인덱스로 객체를 검색해서 가져오는 메소드가 없기 때문에 전체 객체를 대상으로 한 번씩 반복해서 가져오는 반복자(Iterator)를 제공한다.
구현 클래스로는 HashSet, LinkedHashSet, TreeSet 등이 있다.
중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 구현 시 사용
HashSet은 객체를 저장하기 전에 객체의 hashCode() 메소드를 호출해서 해시코드를 얻어내고, 이미 저장되어 있는 객체들의 해시코드와 비교한다. 만약 동일한 해시코드가 있다면 다시 equals() 메소드로 두 객체를 비교해서 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않는다.
같은 문자열을 HashSet에 저장할 경우 동등한 객체로 간주되어 하나의 값만 저장이 되는데, 그 이유는 String 클래스가 hashCode()와 equals() 메소드를 재정의해서 같은 문자열인 경우 hashCode()의 리턴값은 같게, equals()의 리턴값은 true가 나오게 했기 때문이다.
Map 인터페이스
Map 컬렉션은 키와 값으로 구성된 Map.Entry 객체를 저장하는 구조로 키는 중복 불가능, 값은 중복 가능하다는 특징이 있다.
구현 클래스로는 HashMap, TreeMap, Hashtable, Properties 등이 있다.
HashMap의 키와 값 타입으로 기본 타입은 사용할 수 없고 클래스 및 인터페이스 타입만 사용 가능하다. 만약 정수 타입을 저장하고 싶을 때는 Integer 타입을 사용하면 되는데 이 때 오토박싱되어 저장된다.
Hashtable은 HashMap과 동일한 내부 구조를 가지고 있지만 동기화된 메소드로 구성되어 있어 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있어서 스레드에 안전하다.
마지막으로 컬렉션 프레임워크에 있는 Stack 클래스와 Queue 인터페이스에 대해 알아보자.
마지막에 저장한 데이터를 가장 먼저 꺼내는 자료구조(Last In First Out)로 순차적인 추가, 삭제가 용이한 ArrayList를 사용한다.
스택의 활용 ex) 수식계산, 수식괄호검사, 웹브라우저의 뒤로/앞으로
처음에 저장한 데이터를 가장 먼저 꺼내는 자료구조(First In First Out)로 비순차적인 추가, 삭제가 용이한 LinkedList를 사용한다.
스택과 달리 큐는 인터페이스만 정의되어 있어 인터페이스를 구현한 클래스 중 하나(대표적인 구현 클래스 : LinkedList)를 선택해서 사용한다.
큐의 활용 ex) 최근사용문서, 버퍼
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class StackQueueEx {
public static void main(String[] args) {
// Stack은 클래스로 제공
// Queue는 Queue 인터페이스를 구현한 클래스 중 하나를 선택해서 사용
Stack st = new Stack();
Queue q = new LinkedList(); // Queue 인터페이스의 구현체인 LinkedList 사용
st.push("0");
st.push("1");
st.push("2");
q.offer("0");
q.offer("1");
q.offer("2");
System.out.println("Stack");
while (!st.empty()) {
System.out.println(st.pop()); // 2 1 0
}
System.out.println("Queue");
while (!q.isEmpty()) {
System.out.println(q.poll()); // 0 1 2
}
}
}
import java.util.EmptyStackException;
import java.util.Vector;
public class MyStack extends Vector {
public Object push(Object item) {
addElement(item);
return item;
}
public Object pop() {
Object obj = peek(); // 스택에 저장된 마지막 요소 읽어옴
// 만약 스택이 비어있다면 EmptyStackException 발생
// 마지막 요소 삭제
removeElementAt(size() - 1); // 마지막 인덱스
return obj;
}
public Object peek() {
int len = size();
if (len == 0) {
throw new EmptyStackException();
}
// 마지막 요소 반환
return elementAt(len - 1);
}
public boolean empty() {
return size() == 0;
}
public int search(Object o) {
int i = lastIndexOf(o); // 끝에서부터 탐색
if (i >= 0) {
return size() - i;
}
return -1; // 해당 객체를 찾지 못하면 -1 반환
}
}
Queue 인터페이스의 구현체 중 하나로 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내며, null은 저장할 수 없다. 힙 형태로 저장하여 최대값이나 최소값을 빠르게 찾을 수 있다.
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueEx {
public static void main(String[] args) {
Queue pq = new PriorityQueue();
pq.offer(3);
pq.offer(1);
pq.offer(5);
pq.offer(2);
pq.offer(4);
System.out.println(pq);
Object obj = null;
// 우선순위가 높은 것부터 출력되는데 숫자가 작을수록 우선순위가 높음
while ((obj = pq.poll()) != null) {
System.out.println(obj); // 1 2 3 4 5
}
}
}
Deque은 Queue의 변형으로 스택과 큐를 합쳐놓은 것과 같으며 양쪽 끝에 추가 및 삭제가 가능하다.
Deque의 조상은 Queue이며, 구현체로는 ArrayDeque과 LinkedList 등이 있다.