자바 - 컬렉션 프레임워크

신범철·2022년 2월 11일

Java collecion 자료구조

자바

목록 보기

7/17

자료구조의 분류

선형 자료구조(Linear Data Structure)
- 리스트(List)
- 큐(Queue)
- 덱(Deque)
비선형 자료구조(Nonlinear Data Structure)
- 그래프(Graph)
- 트리(Tree)
집합 자료구조
- 집합(Set)
파일 자료구조
- 순차파일
- 색인파일
- 직접파일

Java Collections FrameWork

일정 타입의 데이터들이 모여 쉽게 가공할 수 있도록 지원하는 자료구조들의 뼈대(기본구조)

점선은 구현 관계이고 실선은 확장 관계이다.
인터페이스끼리는 다중 상속 가능
Collection을 구현만 클래스 및 인터페이스들은 모두 java.util 패키지에 존재한다.

List, Queue, Set 이 3가지의 형태에 따른 자료구조들이 있다. 그리고 Queue와 Set에는 조금 더 구체화되어 Deque와 SortSet이라는 형태에 따른 자료구조가 존재한다.
각각의 자료구조들은 구현되어 class로 제공한다. 구현된 자료구조가 녹색 부분이다.

Iterable

사진의 맨 위에 Iterable이 존재한다. 이는 반복가능하다는 의미의 단어이다.
Iterable안에서 제공하는 class들은 모두 객체형태로 내부 구현 또는 대게 Object[]배열 형태가 아니라 각각의 객체를 갖고 움직인다.
그래서 객체의 데이터들을 모두 순회하면서 출력하려면 사용자들이 각각의 데이터 순회 방법을 알거나 하나씩 get()같은 메소드를 통해 데이터를 하나씩 꺼내와야한다.

하지만 Iterable에서는 인터페이스를 보면 알겠지만 for-each를 제공한다. 즉 Iterable 인터페이스를 쓰는 모든 클래스들은 기본적으로 for-each문법을 쉽게 사용할 수 있다.
즉 반복자로 구현되게 나오게 한다는 말이다.

List

상세한 자료는
List Interface 상세 자료
또는 내 velog에서 List를 검색해보잣~

List Interface는 대표적인 선형 자료구조로 주로 순서가 있는 데이터를 목록으로 이용할 수 있도록 만들어진 인터페이스이다.
nt[] array = new int[10];이라고 선언하면 10개의 공간 외에는 사용하지 못한다.
즉 array[13]= 32;라고 하면 할당된 범위 밖이기 때문에 IndexOutofBoundsException이라는 에러가 발생한다.

이런 단점을 보완하여 List를 통해 구현된 클래스들은 '동적 크기'를 갖으며 배열처럼 사용할 수 있게 되어 있다.

List Interface를 구현하는 클래스
1. ArrayList
1. LinkedList
2. Vector(+Vector를 상속받은 Stack)

List Interface에 선언된 대표적인 메소드

ArrayList

Object[] 배열을 사용하면서 내부 구현을 통해 동적으로 관리를 한다. 우리가 흔히 쓰는 primitive 배열(ex int[])과 유사한 형태라고 생각하자
즉, 최상의 타입인 Object타입으로 배열을 생성하여 사용하기 때문에 요소 접근(access elements)에서 탁월한 성능을 보이나, 중간의 요소가 삽입, 삭제가 일어나는 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야 하기 때문에 삽입, 삭제에서 비효율적이다.

LinkedList

데이터와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식이다. 데이터와 주소로 이루어진 클래스를 Node라고 하고, 각 노드는 이전의 노드와 다음 노드를 연결하는 방식이다. 즉 객체끼리 연결하는 방식
요소 접근(access elements)시 모든 노드를 방문해야한다는 점에서 성능이 떨어지나, 해당 노드를 삭제, 삽입해야하는 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에 삽입, 삭제에서는 좋은 효율을 보인다.

Vector

사실 잘 쓰는 클래스는 아니다.
ArrayList와 비슷하다.
Object[] 배열을 사용하며 요소 접근에서 빠른 성능을 보인다.

그럼 ArrayList만 있으면 되지 왜 Vector가 존재할까?
Vector는 Collection Framework가 도입되기 전부터 지원하던 클래스였다.
Vector는 항상 동기화를 지원한다.(여러 쓰레드가 동시에 데이터에 접근하려하면 순차적으로 처리하도록 한다.)
고로 멀티 스레드 환경에서 안전하지만, 단일 스레드에서도 동기화를 하기 때문에 Arraylist에 비해 성능이 느리다.

Stack

LIFO(Last in First out)
Stack의 경우 Vector클래스를 상속받고 있고, java에서 지원하는 Stack 클래스의 메소드들도 모두 Vector에 있느 메소드를 이용하여 구현되어 있다.

List Interface 객체 생성 방법

/* 
T는 객체 타입을 의미하며 기본적으로
Integer, String, Double, Long 같은 Wrapper Class부터
사용자 정의 객체까지 가능하다.
ex) LinkedList<Integer> list = new LinkedList<>();
primitive type은 불가능하다.
*/
 
// 방법 1
ArrayList<T> arraylist = new ArrayList<>();
LinkedList<T> linkedlist = new LinkedList<>();
Vector<T> vector = new Vector<>();
Stack<T> stack = new Stack<>();
 
// 방법 2
List<T> arraylist = new ArrayList<>();
List<T> linkedlist = new LinkedList<>();
List<T> vector = new Vector<>();
List<T> stack = new Stack<>();
 
// Stack은 Vector를 상속하기 때문에 아래와 같이 생성할 수 있다.
Vector<T> stack = new Stack<>();

Queue

Queue Interface는 선형 자료구조로 순서가 있고
First-in First-out을 위해 만들어진 인터페이스이다.
가장 앞쪽에 있는 위치를 head라고 부르고, 가장 뒤에 있는 위치를 tail이라고 부른다.

Queue를 상속하고 있는 Deque이라는 Interface도 있는데
Queue는 한쪽 방향으로만(단방향) 삽입 삭제가 가능하다.
Deque는 Double ended Queue라는 의미로 양쪽에서 삽입 삭제가 가능하다.

Queue/Deque Interface를 구현하는 클래스
1. LinkedList
1. ArrayDeque
2. PriorityQueue

Queue/Deque Interface에 선언된 메소드

LinkedList, ArrayDeque

여기서 LinkedList가 또 나왔다..

LinkedList는 List를 구현하기도 하고, Deque를 구현하기도 한다.
즉 LinkedList는 사실상 3가지 용도로 쓸 수 있다... 병신같긴하네
1. List
2. Deque
3. Queue

실제로 LinkedList Class를 보면 다음과 같이 List와 Deque를 모두 구현한다.

Deque또는 Queue를 LinkedList처럼 Node 객체로 연결해서 관리하길 원한하면 LinkedList를 사용하면된다.
반대로 ArrayList처럼 Object[] 배열로 구현되어 있는 것은 ArrayDeque이다.
물론 LinkedList와 ArrayDeque 둘 다 Deque를 구현하고 있고, Deque는 Queue를 상속받기 때문에 Queue로도 쓰일 수 잇다.

일반적인 큐를 사용하고자 하면 LinkedList로 생성하여 Queue로 선언하면 된다.

Queue<T> queue = new LinkedList<>();

Deque도 마찬가지이다.

Deque<T> queue = new LinkedList<>();

PriorityQueue

우선순위 큐
일반적으로 큐는 FIFO이라고 했다. 하지만 PriorityQueue는 데이터 우선순위이다.
Default는 낮은 순자가 높은 우선순위를 갖는다.
쉽게 생각하면 정렬메소드인 sort()와 같은 순서대로 데이터 우선순위를 가진다.
PriorityQueue는 주어진 데이터들 중 최댓값, 혹은 최솟값을 꺼내올 때 매우 유용하다.
다만 사용자가 정의한 객체를 타입으로 쓸 경우 반드시 Comparator 또는 Comparable을 통해 정렬 방식을 구현해주어야한다.

Queue Interface 생성 방법

/* 
T는 객체 타입을 의미하며 기본적으로
Integer, String, Double, Long 같은 Wrapper Class부터
사용자 정의 객체까지 가능하다.
단, primitive type은 불가능하다.
*/
 
ArrayDeque<T> arraydeque = new ArrayDeque<>();
PriorityQueue<T> priorityqueue = new PriorityQueue<>();
 
Deque<T> arraydeque = new ArrayDeque<>();
Deque<T> linkedlistdeque = new LinkedList<>();
 
Queue<T> arraydeque = new ArrayDeque<>();
Queue<T> linkedlistdeque = new LinkedList<>();
Queue<T> priorityqueue = new PriorityQueue<>();

Set

데이터를 중복해서 저장할 수 없다.
입력 순서대로 저장 순서를 보장하지 않는다.

(But LinkedHashset은 Set임에도 순서대로의 저장순서를 보장한다)

그리고 Set Interface를 상속 받은 SortedSet Interface도 존재한다.
SoredSet Interface는 Queue와 유사하게 Set를 상속 받을수 있다.

Set/SortedSet Interface를 구현하는 클래스
1. HashSet
1. LinkedHashSet
2. TreeSet

Set/SortedSet Interface에 선언된 메소드

HashSet

중복을 허용하지 않으면서 순서도 보장받고 싶지 않은 경우

삽입, 삭제, 색인이 매우 빠른 컬렉션

LinkedHashSet

중복을 허용하지 않으면서 순서를 보장받고 싶은 경우

TreeSet

중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합

Set Interface 클래스 생성방법

/* 
T는 객체 타입을 의미하며 기본적으로
Integer, String, Double, Long 같은 Wrapper Class부터
사용자 정의 객체까지 가능하다.
단, primitive type은 불가능하다.
*/
 
HashSet<T> hashset = new HashSet<>();
LinkedHashSet<T> linkedhashset = new LinkedHashSet<>();
TreeSet<T> treeset = new TreeSet<>();
 
SortedSet<T> treeset = new TreeSet<>();
 
Set<T> hashset = new HashSet<>();
Set<T> linkedhashset = new LinkedHashSet<>();
Set<T> treeset = new TreeSet<>();