[Java] 알고리즘용 자료구조

---

 

 

자바의 모든 자료구조를 정리한 것은 아니고, 주로 사용하게 되는 클래스와 인터페이스 위주로 상속 관계를 그려봤다. (틀릴 수도 있음) 하이라이트 한 자료구조만 조금 더 다뤄보려고 한다.

 

당연하지만 클래스는 기본 자료형이 아니므로, 위의 자료구조를 사용하기 위해 패키지를 추가해야 한다. 모두 java.util 패키지 하위에 존재한다.

import java.util.*;

 

 

 

---

Array

가장 기본적인 자료구조 클래스

배열의 정렬, 이진 탐색, 리스트 변환 등의 method를 지원한다.

Array의 sort()는 Dual Pivot 퀵 정렬을 사용한다. (내가 직접 구현하는것보다 훨씬 성능이 좋다는 뜻이다.)

asList()는 Array를 List로 변환하는 method이다. 그러나 접근 가능한 ArrayList가 아니라 조회만 가능한 정적 리스트 클래스를 리턴한다.

 

 

 

 

 

List

Collection(object 집합 인터페이스)과 Iterable(반복자)를 implement하는 인터페이스

구현 클래스로는 AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWritArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector가 있다.

 

List 구현체의 대부분은 선형탐색을 사용한다. 효율이 그리 좋지 않다.

List는 참조 자료형(클래스)의 집합이다. 따라서 기본자료형을 타입으로 받을 수 없다.

List<Integer> list; // O
List<int> list; // X

 

List는 중복을 허용한다. 같은 주소를 참조하는 원소를 중복하여 리스트에 추가할 수 있다.

List<Integer> list = new ArrayList<Integer>();
list.add(0); // 첫번째 원소
list.add(0); // 두번째 원소

위 코드를 실행해보면, 두 원소가 모두 id=45인 동일한 객체를 참조하고 있다.

 

 

 

 

 

ArrayList

List의 구현 클래스

크기 조절이 가능하며, 원소로 null을 허용한다.

*구조적 변경이 동기화되지 않는다. 다중 접근이 필요한 환경에서는 외부에서 동기화 작업을 해주거나, wrapper를 사용해야 한다.

*구조적 변경이란, 리스트에 원소가 추가/삭제되는 등 리스트의 크기가 변하는 작업을 의미한다. 원소의 값 변경은 구조적 변경이 아니다.

List<> list = Collections.synchronizedList(new ArrayList<>());

 

 

 

 

 

 

Stack

Last-In-First-Out

Vector 클래스의 확장: 크기 조절이 가능하며, 구조적 변경이 동기화된다.

 

<스택의 대표적인 method>

stack.push(E item); // return item
stack.pop(); // return item, 스택이 빈 경우 예외처리
stack.peek(); // return item, 스택이 빈 경우 예외처리
stack.isEmpty(); // return boolean
stack.search(Object o); // return int(위치), -1은 해당 원소 없음

 

Stack은 중복을 허용한다.

Stack 클래스를 사용하는 것보다, Deque을 사용하여 LIFO 스택을 구현하는 것이 더 안정적이다.

Deque<T> stack = new ArrayDeque<T>();

 

 

 

 

 

Priority Queue

내부 규칙에 따라 정렬되는 Heap 구조

PriorityQueue<T> pq = new PriorityQueue<>
(
    new Comparator<T> { 
        // Item은 T 자료형의 비교값
        public int compare(Item i1, Item i2){
                return (i1.val == i2.val)?
                Integer.compare(i1.val2, i2.val2):Integer.compare(i1.val, i2.val);
            }
     }
);

 

중복을 허용하고, null을 허용하지 않는다.

동기화를 지원하지 않는다. 멀티 스레드 환경에서 PQ에 접근하는 경우, thread-safe 한 PriorityBlockingQueue 클래스를 사용해야 한다.

 

 

 

 

 

HashMap

Key-Value 쌍을 저장하는 자료구조

비정렬, 중복 비허용

Key와 Value의 null을 허용

구조적 변경의 동기화를 지원하지 않으므로 wrapper method를 사용해야 한다.

Map map = Collections.synchronizedMap(new HashMap<>());

 

 

 

 

 

Set

중복 비허용, 하나의 null만 허용

 

TreeSet

- Set의 구현 클래스로 정렬됨

 

HashSet

- Set의 구현 클래스로 정렬되지 않음

 

 

 

 

 

---

 참고자료 

• 알고리즘에서 자주 쓰는 자료구조 in JAVA
• JAVA 8 Docs
• Java Array 내부 정렬 방식 - Dual Pivot Quick Sort

 

😥 Array, ArrayList, List 구현하면서 맨날 똑같은 부분 까먹은 이유가 이 부분 정리를 안 해서였다. 앞으로는 헷갈리지 말자