[Java] Collections Framework

한호성·2022년 5월 23일

자료구조

자료구조의 분류

자료구조를 분류하는 방법 중 대표적인 방법은 선형 자료구조, 비선형 자료구조로 나뉠 수 있다. (형태에 따른 자료구조)

- 선형 자료구조
선형 자료구조는 데이터가 일렬로 연결된 형태, ex) 배열

대표적인 선형 자료구조 : List,Queue,Deque

- 비선형 자료구조
일렬로 나열된 것이 아닌, 각 요소가 여러 개이 요소와 연결된 형태를 생각하면 된다. 

대표적인 비선형 자료구조 : Graph, Tree

두가지 부류에 속하지 않는 자료구조 집합(Set)이 있다. 보통 기타 자료 구조이다.

Java Collections FrameWork

Collections

어떤 일정한 부류의 것을 수집하여 한 공간에 모아놓은 것을 컬렉션이라 한다.
Java에서 비슷한 류의 데이터들을 쉽게 다루기 위해 모아놓은 것들을 가공 및 처리 할 수 있도록 지원하는 자료구조의 모음이라 생각할 수 있다.

Framework

어떤 문제를 해결하기 위한 구조의 뼈대가 되는 기본 구조를 의미한다.
기본 뼈대 -> 자바 언어의 Interface가 뼈대를 나타낸다.

Java 언어에서 제공하는 Collection 은 크게 3가지 인터페이스로 나뉘어져 있고,
List(리스트), Queue(큐), Set(집합) 으로 나뉘어 있다.

구조를 이미지로 나타내보면 아래와 같다

*cf) Java 에서는 map 을 Collections 이라고 보지 않는다. Map class 가 Collections interface를 상속하지 않는다.

*cf) Collection을 구현한 클래스 및 인터페이스는 java.util package에 있다.

List

대표적인 선형 자료구조로 순서가 있는 데이터 목록으로 이용할 수 있도록 만들어진 인터페이스

배열과 달리 동적크기를 갖으면서, 배열처럼 사용할 수 있다.

<List Interface를 구현하는 클래스>
1. ArrayList
2. LinkedList
3. Vector

ArrayList

ArrayList는 object[] 배열을 사용하면서 내부 구현을 통해 동적으로 관리 한다. 일반 배열과 유사한 형태. 최상위 타입인 Object 타입으로 배열 생성하여 사용하기 때문에 요소 접근에 이점이 있으나, 중간의 요소 삽입,삭제가 일어나는 경우, 그 뒤의 요소들을 한칸씩 밀거나 당겨야 하기 때문에, 삽입에서는 단점이 있다.

(그런가...? 제일 많이 쓰는 클래스인데.. 불편함을 느껴보진 못했던거 같다.)

LinkedList

데이터와 주소로 이루어진 클래스를 만들어 서로연겨하는 방식. 데이터와 주소로 이루어진 클래스를 Node(노드)라고 하고, 각 노드와 이전 노드, 다음 노드를 연결하는 방식이다. 이중 연결 리스트 라고도 함. 요소 검색시, 처음부터 끝까지 검색해야 한다는 단점이 있으나, 해당 노드 삭제, 삽입 해야할 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에, 삽입, 삭제에서는 매우 좋은 효율을 보인다.

Vector

ArrayList와 거의 비슷하다. Collection Framework 도입 전부터 존재하던 클래스 Vector 클래스는 항상 동기화를 지원한다 -> 같은 데이터에 여러개의 쓰레드가 접근하면 순차적으로 데이터를 처리한다.(나쁘지 않은 자료구조 class인거 같다..)
멀티 쓰레드에서는 안전하지만, 단일 쓰레드에서도 동기화를 하기 떄문에 성능이 ArrayList 에 비해 떨어지는 편이다.

(한번도 사용해보지 않았던 자료구조, 멀티쓰레드에서 이점이 있을 것으로 생각된다.)

Stack

LIFO(Last in First out) 후입선출.
가장 대표적인 예시 웹페이지의 뒤로가기 버튼이다.
Vector 클래스를 상속받고 있다.

Queue

선형 자료구조 FIFO( First-in-First-out) 을 위해 만들어진 인터페이스. 가장 앞쪽을 head 라고 부르고, 가장 후위의 위치를 tail 이라 부른다.

Queue 단방향 삽입 삭제가 가능하다. Queue를 상속받는 Deque 는 Double ended Queue 양쪽에서 삽입삭제가 가능한 자료구조이다.

Queue/Deque Interface를 구현하는 클래스

LinkedList
ArrayDeque
PriorityQueue

대표적인 메소드

LinkedList & ArrayDequeue

앞선 List에서 LinkedList가 List interface를 구현한다고 설명되어 있는데,
LinkedList 는 List를 구현하기도 하고, Deque도 구현한다.

LinkedList는 List,Deque,Queue 3가지 용도로 사용 가능하다.

LinkedList class를 확인해보자

ArrayList 와 LinkedList의 차이는 데이터를 Object[] 로 관리하느냐 Node라는 객체에 연결해서 관리하느냐 이다. 상황에 맞춰서 사용할 수 있다. Queue를 LinkedList 처럼 Node로 관리하기를 원한다면 , LinkedList로 생성하여 선언해서 쓰면된다.

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

ArrayDeque는 object[] 배열로 구현되어 있다.

PriorityQueue

단어 해석 그대로 '우선순위 큐'다. LinkedList는 Queue로 사용할 수 있다고 했다. PriorityQueue는 데이터 우선순위에 기반하여, 우선순위가 높은 데이터가 먼저 나오는 원리다. PriorityQueue 는 주어진 데이터에서 최대값 , 최소값 꺼내올 때 유용하게 사용된다.

사용자가 정의한 객체를 타입으로 쓸 경우 Comparator, comparable 통해 정렬방식을 구현해 주어야 한다.

Set

집합을 의미하는 Set. 특징 2가지가 존재

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

<Set/SortedSet Interface를 구현하는 클래스>

1.HashSet
2.LinkedHashSet
3.TreeSet

자주 사용되는 메소드

*cf) LinkedHashSet은 입력 순서대로의 저장순서를 보장하고, 나머지 class들은 순서를 보장하지 않는다.

HashSet

가장 기본적인 Set 컬렉션의 클래스, 입력 순서를 보장하지 않고, 순서도 마찬가지로 보장되지 않는다.

사용예시 : 닉네임을 만들거나 중복확인을 눌러 중복된 닉네임 또는 아이디인지 확인 -> 데이터 정렬되어 있을 필요 없고, 빠르게 중복되는지만 확인하면 되기 때문에 유용한 방법이다.

hash에 의해 데이터 위치를 특정시켜 해당 데이터를 빠르게 색인 가능하게 만든 것이다.

LinkedHashSet

Link+Hash+Set 3개의 성질을 갖고 있는 자료구조
Set의 경우 기본적으로 입력 순서대로의 저장순서를 보장하지 않아 '중복은 허용하지 않으면서 순서를 보장받고 싶은경우'에는 불편할 수밖에 없다. 이를 보완하기 위해 존재하는 것이 바로 LinkedHashSet인 것이다.

TreeSet

SortedSet Interface 를 구현하는 클래스로 데이터의 가중치에 따른 순서대로 정렬되어 보장한다는 것이 특징이다. '중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 쓴다' -> 특정 구간의 집합요소들을 탐색할 때 매우 유용하다.(Tree 라는 자료구조 자체가 데이터를 일정 순서에 의해 정렬하는 구조다. 거기에 더해진 것이 바로 Set인 중복값 방지 자료구조인 것이다.)