자바[JAVA] - Collections Framework (feat. 자료구조)

자료구조(Data Structure)

• 자료구조와 알고리즘은 뗄 수 없는 의존적인 관계이다. 따라서 알고리즘 문제를 해결함에 있어 자료구조의 공부는 필연적이라 할 수 있다.
• 자바의 대표적인 자료구조인 Collection을 통해 자료구조를 직접 구현해 본다.

자료구조의 분류(형태에 따른 분류)

1. 선형 자료구조(Linear Data Structure)

   • 데이터가 일렬로 연결된 형태
   • int[] 배열, 리스트(list), 큐(Queue), 덱(Deque)

2. 비선형 자료구조(Nonlinear Data Structure)

   • 일렬로 연결나열된 것이 아닌, 하나의 요소가 여러 개의 요소와 연결 된 형태.
   • 그래프(Graph), 트리(Tree)

3. 기타 자료구조

   • 집합(set)

Java Collection FrameWork

위의 그림에서 처럼 Collection 인터페이스는 크게 List, Queue, Set 인터페이스로 나눠진다. 여기서 인터페이스는 쉽게 말해 기본 뼈대를 뜻한다. 예를 들어, HashSet의 경우는 Set이라는 뼈대(인터페이스)를 구현해 만든 작업물(Class)이라고 할 수 있다. 이 Collection으로 부터 나눠진 List, Queue, Set에 대해 알아보도록 하겠다.

List

• List Interface(리스트 인터페이스)는 대표적인 선형 자료구조이다.
• 주로 순서가 있는 데이터를 목록으로 이용할 수 있도록 만들어진 인터페이스이다.
• 배열과 그 쓰임이 거의 비슷하지만 배열은 처음 지정한 공간만 사용가능 하지만, list는 '동적 크기'를 갖기 때문에 쓰임이 유용하다.

<List Interface를 구현하는 클래스>

1. ArrayList

2. LinkedList

3. Vector(+Vector를 상속받은 Stack)
   

Queue

• 선형 자료구조로 주로 순서가 있는 데이터를 기반으로 '선입선출(FIFO: First-in-First-out)' 형의 인터페이스이다.
• 예를 들어 10, 20, 30 순으로 데이터를 넣으면 10, 20, 30 순으로 데이터가 나오는 구조이다.
• Queue를 상속하는 Deque(덱)은 간단히 양방향 Queue라고 생각하면 된다.
• 즉, head에서도 접근 가능하며, tail에서도 접근 가능한 양방향 큐로 생각하면 된다.

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

1. LinkedList

2. ArrayDeque

3. PriorityQueue

Set

• 말 그대로 '집합'과 역할이 같다.
• 크게 두가 가지 특징이 있다. 첫 번째로 '데이터를 중복해서 저장할 수 없다'
• 두 번째로 '데이터의 순서가 없다.'
• 예외적으로 LinkedHashSet은 데이터를 중복 저장할 수 없으며 데이터의 순서가 있다.

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

1. HashSet

2. LinkedHashSet

3. TreeSet
   
   

아래는 상황에 따른 컬렉션 사용의 로드맵을 제공한 알고리즘이다.(출처:http//javaBeans.asia)