Java 자료구조 비교

여러가지 자료구조에 대한 비교를 해본다.

Array (배열)

• 같은 데이터 타입에 대해 데이터를 한 곳에 저장해두고 하나의 변수를 가지고 사용하는 것을 말한다. 
• 1차원배열과 다차원 배열이 존재
• 장점
• 간단하게 사용 가능
• 인덱스 통해 빠르게 데이터 접근 가능
• 단점
• 저장 공간이 제한적
• 동적 할당을 통해 새롭게 정의 가능하지만 데이터 이동을 또 해야함

Iterable

• 이름 그대로 반복할 수 있는지 확인하는 인터페이스
• 다음과 같은 abstract method를 갖음

 

boolean hasNext () // 요소가 더 많은 경우 true를 반환합니다.  E next () // 제네릭 타입 E의 다음 원소를 반환합니다.  void remove () // 반복자가 반환 한 마지막 요소를 제거합니다.

Collection

• 모든 콜렉션의 상위 인터페이스
• Collection이 갖는 핵심 메소드를 선언
• ex) add, contatin, remove, size, isEmpty, iterator 등

List

• Collection 인터페이스를 확장한 자료형
• 순서가 있음
• 인덱스가 존재
• 중복을 허용

Vector

Java 1.0 에서 추가

동기화 기능 제공

ArrayList와 거의 동일하지만 동기화 기능에서만 차이를 보임

ArrayList의 구현 버전

ArrayList

• Java 1.2 에서 추가
• 동기화 제공되지 않음
• 내부적으로 데이터를 배열에서 관리
• 데이터의 추가, 삭제를 위해 임시 배열을 생성해 데이터를 복사 하는 방법을 사용
• 패키지 : java.util
• 장점 : 검색이 빠름(각 데이터에 대한 인덱스를 가지고 있으므로)
• 단점 : 대량 데이터 추가/삭제시 느림 (배열의 복사가 빈번하게 발생)

CopyOnWriteArrayList

• ArrayList와 동일하지만 동기화 지원
• 동기화를 지원하므로 ArrayList에 비해서는 느림
• JDK 1.5에서 추가
• ArrayList는 CopyOnWriteArrayList가 수행 할 수없는 동안 ConcurrentModificationException을 발생
• package : java.util.concurrent

LinkedList

• Java 1.2 에서 추가
• 링크 기반 (데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태를 알고 있는 형태)
• 장점 : 대량 데이터 추가/삭제가 빠름(위치 정보의 수정만으로 가능)
• 단점 : 데이터가 많은 경우 검색이 느림 (순차적으로 모든 노드를 조회해야 함)

Stack

LIFO(Last In First Out)구조로 구현된 리스트

스택

Set

• 중복을 허용하지 않음

HashSet

• 데이터를 해쉬 테이블에 담는 클래스
• 순서가 없음

LinkedHashSet

• 해쉬 테이블에 데이터를 담음
• 순서가 있음 : 저장된 순서

TreeSet

• red-black이라는 트리에 데이터를 담음
• 순서가 있음 : 값에 따라서 정해짐
• HashSet보다 성능상 느림

Queue

• FIFO(Firsh In First Out)구조로 구현된 리스트

PrioriryQueue

• 큐에 추가된 순서와 상관없이 먼저 생성한 객체가 먼저 나옴

LinkedBlockingQueue

• 선택적으로 저장할 데이터의 크기를 정할 수도 있는 FIFO 기반의 링크 노드를 사용
• 블로킹 큐

ArrayBlockingQueue

• 저장되는 데이터의 크기가 정해져 있는 FIFO 기반
• 블로킹 큐

PriorityBlockingQueue

• 저장되는 데이터의 크기가 정해져 있지 않음
• 객체의 생성 순서에 따라서 순서가 저장
• 블로킹 큐

DelayQueue

• 큐가 대기하는 시간을 지정하여 처리하도록 되어 있는 큐

SynchronousQueue

• put() 메소드를 호출하면, 다른 스레드에서 take() 메소드가 호출될 때까지 대기하도록 되어 있는 큐
• 저장되는 데이터가 없음
• API에서 제공하는 대부분의 메소드는 0이나 null을 리턴

Blocking Queue

크기가 지정되어 있는 큐에 공간이 더 이상 없을 때, 공간이 생길 때까지 대기하도록 만들어진 큐

Map

Key와 Value 쌍으로 저장되는 자료구조

Hashtable

• 데이터를 해쉬 테이블에 담는 클래스입니다. 
• 내부에서 관리하는 해쉬 테이블 객체가 동기화되어 있음
• null 값을 허용하지 않음

HashMap

• 데이터를 해쉬 테이블에 담는 클래스
• null 값을 허용
• 동기화 되어 있지 않음

ConcurrentHashMap

• HashMap과 동일하지만 동기화 지원
• JDK 1.5에서 지원
• 동기화시 hashtable을 절체에 대해 lock을 걸지 않고 조각을 쪼개어 부분 부분 lock을 걸어 성능을 높임
• null 값을 허용하지 않음
• 동시성 처리를 위해서 null을 수용할 수 없음

TreeMap

• red-black 트리에 데이터를 담음
• 순서가 있음 : 키 값에 따라 정해짐

LinkedHashMap

• HashMap과 거의 동일
• 이중 연결 리스트(doubly-linkedlist)를 사용하여 데이터를 담음
• 순서가 있음 : 넣는 순서에 따라 정해짐

Reference

[1] The Collection Framework https://www.ntu.edu.sg/home/ehchua/programming/java/J5c_Collection.html