자바의 자료구조

June Lee·2021년 2월 3일

Java

목록 보기

11/23

컬렉션 프레임워크

배열, 리스트와 같이 데이터 군을 저장하고 사용하기 위한 표준화된 방법을 제공하는 클래스의 집합을 뜻한다. JDK 1.2 이전까지는 각 클래스들이 서로 다른 방식으로 데이터 군을 다루었지만, 이후 이를 표준화된 방식으로 체계화하였다.

컬렉션 프레임워크에는 List, Set, Map이라는 3가지의 인터페이스가 존재한다. 그리고 이 중 List와 Set은 요소가 많기 때문에 이런 점을 뽑아 Collection 인터페이스를 추가로 정의하였다.

List

순서가 있는 데이터의 집합

데이터 중복 허용

구현 클래스: ArrayList, LinkedList, Stack

List에서 요소 찾아서 없애기
리스트에서 요소를 찾을 때는 get, 찾은 요소를 삭제할 때는 remove를 사용한다. 일단 get의 경우 매개변수로 인덱스를 받는다. 이를 통해 해당 인덱스에 어떤 요소가 있는지 반환한다.
remove의 경우, Object 자체 혹은 인덱스(int) 둘 다로 요소를 삭제할 수 있다. 근데 이게 정말 헷갈리고 문제인 것이, 리스트에 Integer를 담은 경우, get을 했을 때 반환값으로 숫자가 나오지만, 이 숫자는 사실 Object이기 때문에 인덱스가 아닌 요소 자체가 삭제된다. 이런 버그는 잡기도 힘드니 주의를 기울이는 것이 좋다ㅎ..

Set

순서가 없는 데이터의 집합

데이터 중복 허용 x

구현 클래스: HashSet, TreeSet

Map

key-value 쌍으로 이루어진 데이터 집합

순서 없음

key는 중복 불가, value는 중복 가능

구현 클래스: HashMap, TreeMap

제네릭(Generic)

제네릭은 코드의 일관성과 안정성을 유지하기 위해, 객체 생성 시에 클래스 내에서 사용되는 변수나 메소드들이 가져야할 자료형을 정해주는 표기를 뜻한다.

public class Student<T> {

    private T book;
    
    public void read(T book) {
    	...
    }

위와 같이 제네릭을 붙여 정의한 클래스는, 객체를 생성할 때에 타입이 정해진다.

컬렉션 인터페이스에 있는 많은 클래스들의 경우, 제네릭을 붙여서 객체를 생성하는 것이 필수는 아니지만, 제네릭을 붙일 경우 코드의 안정성을 높일 수 있으므로 가급적 제네릭을 붙이는 것이 추천된다.

+)
제네릭을 붙이지 않을 경우, 데이터를 넣을 때 기본적으로 Object 클래스형으로 형변환되기 때문에, 다시 데이터를 찾을 때 또 한 번 형변환 과정을 거쳐줘야한다.

Map 인터페이스

<method>

entrySet() => 반환 타입: Set
keySet() => 반환 타입: Set
values() => 반환 타입: Collection

Map 인터페이스를 구현한 HashMap, TreeMap 등에는 다양한 메서드들이 있는데, key-value 쌍을 얻고 싶거나, key 혹은 value만을 얻고 싶을 때는 위의 메서드들을 사용한다.

이때 entrySet과 keySet은 결과 값들이 중복이 없는 데이터들의 집합이므로 반환 타입이 Set이고, values의 결과 값들은 중복 가능한 데이터들의 집합이므로 반환 타입이 Collection이다.

ArrayList vs. LinkedList

둘의 차이점은 우선 메모리에 값이 어떤 방식으로 저장되는냐이다. ArrayList의 경우, Array와 마찬가지로 메모리에서도 값이 순차적으로 저장된다.
한편, LinkedList는 메모리에서 값이 서로 다른 위치에 저장되고, 그 주소를 순서 상 앞에 위치한 요소에서 레퍼런스하는 식으로 순서가 유지된다.

따라서, 배열(그리고 ArrayList)의 경우, 배열 객체를 생성했을 때 반환되는 주소값이 변수에 저장되어 있어서, 이를 이용해 간단한 계산만으로 원하는 요소의 주소를 얻고 저장된 데이터를 곧바로 읽어올 수 있지만,
LinkedList의 경우 처음부터 찾고자 하는 요소까지를 순차적으로 읽어야만 원하는 값을 얻을 수 있다.

ArrayList

access time이 빠름

데이터의 추가/삭제 시 속도가 느림. 단 순차적 추가/삭제의 경우 더 빠름

비효율적 메모리 사용 (先 메모리 할당 -> 後 데이터 삽입)

LinkedList

access time이 느림

데이터 추가/삭제 시 속도가 빠름

ArrayList와 Array의 차이?

둘의 차이는 Array와 달리 ArrayList는 실행 중에 동적으로 배열의 크기를 바꿔준다는 것이다(배열의 크기가 없는 것이 아니라, 임의로 지정된 크기와 데이터 갯수가 같아지면 그때 동적으로 늘려주는 것이다)
그리고 배열의 크기를 동적으로 바꿔준다고 했지만 내부 구현을 살펴보니, 실제로는 용량이 꽉 찼을 때 기존의 용량보다 1.5배를 늘린 새로운 배열에 기존 배열을 copy하는 식으로 동작했다.
또한, 담을 수 있는 자료형에도 차이가 있다. 한 가지 자료형만 담을 수 있는 Array와 달리, ArrayList는 제네릭을 쓰지 않을 경우 여러 자료형을 담을 수 있다.

List list = new ArrayList();
list.add("abc"); // String Type
list.add(new Person("David", 10)); // Person Class Type

스택(Stack)과 큐(Queue)

스택은 선입후출(Last In Fist Out), 큐는 선입선출(First In First Out)의 유명한 자료 구조이다. 자바에서는 이를 컬렉션의 클래스들 중 어떤 것을 사용해서 구현할까?
우선 스택의 경우, 제일 뒤의 요소를 pop하는 연산이 자주 일어난다. 이처럼 중간 요소를 변경하거나 중간에 데이터를 삽입할 일이 없는 경우에는 ArrayList를 쓰는 것이 좋다.
한편 큐의 경우, 제일 앞의 요소를 poll(peek)하는 연산이 자주 일어나는데, ArrayList로 이를 구현할 경우 데이터를 꺼낼 때마다 빈공간을 채우기 위해 데이터 복사가 필요하므로, LinkedList로 구현하는 것이 더 적합하다.

자바에서는 스택을 별도의 Stack 클래스로 구현하여 제공하고 있고, 큐의 경우 큐 인터페이스로만 정의해두었기 때문에 이를 오버라이딩하여 구현한 LinkedList 클래스(이 외에도 다양한 클래스들이 있긴 하다)를 사용하면 된다.

Stack st = new Stack();
st.push(0);
System.out.println(st.pop()); // 0

Queue q = new LinkedList();
q.offer(0);
System.out.println(q.poll()); // 0
System.out.println(q.peek()); // 0, 첫번째 요소를 삭제 없이 읽어옴

Iterator

Iterator는 컬렉션에 저장된 요소에 접근하는데 사용되는 인터페이스이다. (++ Interator의 기능에서 양방향 조회 기능이 추가된 ListIterator도 있다!)

컬렉션 프레임워크에서는 컬렉션에 저장된 요소들을 읽어오는 방식을 표준화하였는데, 그것이 바로 Iterator이다.
우선 List(ArrayList, LinkedList)의 경우, 순서가 있기 때문에 Iterator가 없어도 index를 이용해 순차적으로 접근하여 읽어오는 것이 가능하다. 그러나 순서가 없는 Set, Map 등의 경우 이렇게 읽어오는 것이 불가능하여, Set은 toArray() 메소드를 이용해 배열로 변환한 후 차례로 읽어줘야한다. 그리고 Map의 경우에는 key를 이용해 값을 읽는 get() 메소드가 있지만, 차례로 읽어오는 메소드는 정의되어 있지 않다.
이처럼, 서로 다른 방식으로 자료들을 읽어오는 대신, 저장된 자료들을 순차적으로 뽑아오면 된다는 공통된 특징을 이용해서 읽어오는 방식을 표준화한 것이 Iterator이다.

Iterator를 사용하기 위해서는, Iterator를 구현한 클래스의 인스턴스를 반환하는 iterator() 메소드가 필요하다. 그런데 iterator()는 원래 Collection 인터페이스에 정의된 메소드이기 때문에, Map의 경우 Set(key-value 쌍, keys) 혹은 Collection(values)으로 변환한 후 iterator()를 사용할 수 있다. 그리고 iterator 객체를 얻은 후에는 해당 클래스의 hasNext(), next() 메소드를 이용해 데이터를 반복적으로 가지고 온다.

Iterator<Integer> iterator = set.iterator();
while(iterator.hasNext()) {
	System.out.println(iterator.next());
}

TreeSet

TreeSet은 이진 탐색 트리(Binary Search Tree) 형태로 데이터를 저장하는 클래스이다. 그 중에서도 TreeSet은 Red-Black tree라는 향상된 이진 탐색 트리로 구현되어 있다.
TreeSet은 기본적으로 Set이므로, 중복된 데이터를 저장하지 않고, 정렬된 위치에 데이털르 저장하기 때문에 입력 순서를 유지하지 않는다.

cf) 이진 탐색 트리
1. 모든 노드가 최대 두 개의 자식노드를 가진다.
2. 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
3. 노드의 추가 삭제 시 반복 비교로 자리를 찾아 저장하므로 시간이 소요된다.(탐색이 필요하므로 마찬가지로 O(logN))
4. 검색과 정렬에 유리하다. (N개 노드에 대해 O(logN)만큼 소요된다(Well-balanced 트리의 경우)
5. 중복된 값을 저장하지 못한다.

TreeSet에 String, int 등 비교 가능한 값이 아닌 객체를 저장할 경우, TreeSet에 저장되는 객체가 Comparable을 구현하거나 Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 한다.