자바 자료구조 학습 중 궁금한 점

1. 배열은 왜 콜렉션에 없는가?

콜렉션 프레임워크는 기본적으로 동적으로 크기가 조절되고, 제네릭을 통해 타입 안정성을 강화하고, 다양한 유틸리티 메서드를 제공해 개발자가 데이터를 보다 효율적으로 처리할 수 있게 돕는 걸 목표로 한다.

 

그런데 배열이 동적 크기 조절이 되나?

배열은 만들어질 때 크기가 고정된다.

한 번 생성된 후에는 크기를 변경할 수 없다.

데이터를 동적으로 추가하고 제거할 수 있는 유연성을 제공하는 자바 콜렉션 프레임워크에 있는 게 더 이상한 거다.

게다가 배열은 고급 기능이나 메서드를 제공하지도 않는다. 

배열에는 메서드가 없다(Arrays 말하는 거 아니다. int[] 이런 거 말하는 거다.).

 

기본 데이터 타입 배열을 가지고 할 수 있는 건 고작 해 봐야 length를 사용해서 길이를 알거나

for 또는 for each문을 사용해서 각 요소에 접근하고 조작하는 거다.

 

2. 그럼 스택은 왜 없는가?

콜렉션에 스택이 없지만 java.util.Stack은 있다(이는 Vector를 상속).

스택 기능을 사용하고 싶으면 Deque(덱, 데크, no 디큐) 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 된다.

ArrayDeque 클래스는 스택과 큐의 기능을 모두 제공하고 Vector 기반 Stack보다 성능이 우수하다.

라고 하는데...

 

내가 간단하게 살펴 본 바 push하면 데이터가 밑에서 위로 쌓이는 게 아니고

head를 기점으로 아래로 쌓인다(???).

pop하면 위에서부터 데이터가 나가고.

그래도 offer하면 데이터가 앞을 기준으로 뒤로 쌓이고 poll하면 맨 앞 데이터가 제거되면서 pointer(?)가 뒤로 간다.

https://www.baeldung.com/java-array-deque

그리고 무슨 add, addFirst, addLast, push, offer 등 별별 메서드가 다 있다.

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html

 

쨌든 스택이 콜렉션엔 없지만 다양한 형태로 쓸 수 있다는 걸 알았으니 이 부분은 여기까지 하자.

 

3. 그럼 큐는 왜 콜렉션에 포함됐는가?

이에 대해 내가 조사를 좀 해 봤는데 알면 알수록 잘 모르겠다.

가장 그럴 듯한 설명은 큐가 프로그래밍에서 일반적으로 필요로 하는 데이터 처리 패턴을 잘 반영하고 있기 때문이라는 설명이다.

이벤트 처리, 작업 스케줄링, 자원 관리 등에서 실제로 큐가 기본적으로 쓰이고 있다(맞죠? 아직 운영체제 과목 안 들음.).

---

그럼 일차적인 궁금증은 약간 해소가 된 것 같으니 다음 궁금증으로 넘어간다.

 

ADT에 대해 얘기하기 전에 정리하고 갈 것이 있다.

지금 나는 코테를 준비 중이다.

코테를 치려면 알고리즘을 짤 줄 알아야 한다.

알고리즘을 짤 수 있으려면 자료구조를 알아야 한다.

그 자료구조는 ADT로부터 비롯된다.

 

ADT는 인터페이스다.

나는 이걸 일종의 pseudo code처럼 생각한다.

정확히 어떤 식으로 돌아갈 지는 자료구조에서 구현이 될 것이다.

ADT는 그저 '이런 스타일이야' 하는 식으로만 설명이 된다.

 

주요 ADT는 다음과 같다.

1. 리스트(List)
   1. 연속적으로 연결된 데이터 요소의 모음이다.
   2. 요소에는 순서가 있으며, 중복을 허용한다.
   3. 예: 배열 리스트, 연결 리스트 (단일 연결 리스트, 이중 연결 리스트)
2. 스택(Stack)
   1. LIFO (Last In, First Out) 원칙에 따라 데이터를 저장한다.
   2. 데이터는 '한 쪽 끝'에서만 추가되거나 제거된다.
   3. 예: 함수 호출 스택, 수식의 괄호 검사, 역순 문자열 생성
3. 큐(Queue)
   1. FIFO (First In, First Out) 원칙에 따라 데이터를 저장한다.
   2. 한 쪽 끝에서는 데이터가 추가되고, 반대쪽에서는 데이터가 제거된다.
   3. 예: 프린터 작업 대기열, BFS(너비 우선 탐색)
4. 우선순위 큐(Priority Queue)
   1. 각 요소가 우선순위를 가지고 있으며, 우선순위가 가장 높은 요소가 가장 먼저 제거된다.
   2. 일반적으로 힙(heap)을 사용하여 구현된다.
   3. 예: 데이크스트라 알고리즘(Dijkstra's algorithm)의 최소 비용 탐색
5. 딕셔너리(Dictionary) / 맵(Map)
   1. 키(key)와 값(value)의 쌍으로 데이터를 저장한다.
   2. 키는 유일하며, 주어진 키에 대해 값을 빠르게 검색할 수 있다.
   3. 예: 해시테이블, 트리 맵
6. 그래프(Graph)
   1. 노드(node)들과 이 노드들을 연결하는 에지(edge)의 집합으로 구성된다.
   2. 방향성(유향, 무향)과 가중치(가중, 무가중)의 특성을 가질 수 있다.
   3. 예: 네트워크 라우팅, 사회 네트워크 분석
7. 트리(Tree)
   1. 계층적인 관계를 표현하는 비선형 데이터 구조다.
   2. 하나의 루트 노드와 여러 개의 자식 노드가 있으며, 각 자식 노드 역시 여러 개의 자식 노드를 가질 수 있다.
   3. 예: 이진 검색 트리, AVL 트리, B-트리
8. 집합(Set)
   1. 중복을 허용하지 않는 데이터 요소의 모음이다.
   2. 집합 간의 연산(합집합, 교집합, 차집합)을 지원합니다.
   3. 예: 해시 집합, 트리 집합

이가 구체적으로 구현된 자료구조 중에서도, 자바의 자료구조를 앞으로 지겹도록 볼 것이니

이 편은 여기서 마무리한다.

 

* 스트림에 대해서는 다음에 자세히 다룬다.