[Java] 컬렉션 프레임워크 (1)

남궁성님의 '자바의 정석 기초편' 유튜브 강의를 보고 정리한 내용입니다.

https://www.youtube.com/playlist?list=PLW2UjW795-f6xWA2_MUhEVgPauhGl3xIp 

자바의 정석 기초편(2020최신)

 

컬렉션 프레임워크에 대해서 세 개의 포스팅으로 나눠서 올릴 예정입니다.

첫 포스팅에선 컬렉션 프레임워크의 전체적인 내용과 List, Stack/Queue 에 대해 다뤄보겠습니다.

 

컬렉션 프레임워크란?

컬렉션 프레임워크의 '컬렉션'은 여러 객체(데이터)를 모아놓은 것을 말하고, '프레임워크'는 표준화/정형화된 프로그램 방식을 말합니다.

프레임워크를 사용하면 생산성과 유지보수성이 향상되는 장점이 있습니다.

따라서 이를 풀어서 말하면, 코드의 생산성과 유지보수성을 향상시키기 위한 여러 객체를 모아놓는 표준화된 프로그램 방식입니다.

JDK 1.2 버전부터 표준화되어 제공되었으며, 다수의 데이터를 쉽고 편리하게 다룰 수 있는 다양한 클래스를 제공합니다.

 

컬렉션 프레임워크의 구조

그림처럼 컬렉션 프레임워크의 핵심 인터페이스는 List, Set, Map 세가지 입니다.

1. List
   • 순서가 있고 중복 허용
   • 대표 구현 클래스: ArrayList, LinkedList, Vector
2. Set
   • 순서가 없고 중복 불가
   • 대표 구현 클래스: HashSet, TreeSet
3. Map
   • Key와 Value의 쌍으로 이루어진 데이터의 집합
   • 순서가 없고 Key는 중복 불가지만 Value는 중복 허용
   • 대표 구현 클래스: HashMap, TreeMap, HashTable, LinkedHashMap

---

ArrayList

ArrayList는 List의 대표 구현 클래스입니다.

배열을 기반으로해서 ArrayList안에 연속적으로(순서대로) 저장되고 중복을 허용합니다.

처음에 객체를 생성할 때 고정된 길이로 생성하지만, 배열의 크기를 데이터의 개수 만큼 자동으로 늘렸다 줄였다 할 수 있는 가변 배열입니다.

늘렸다 줄였다라고 표현했지만 사실 내부적으로 빈 배열을 생성하고(1) 그 안에 기존 배열의 내용을 복사하고(2) 다시 참조를 복사된 배열로 변경하는(3) 세가지 과정을 거칩니다.

 

또한 동기화를 지원하는 Vector 클래스와 다르게 ArrayList는 동기화를 지원하지 않습니다.

동기화는 멀티스레드 환경에서 하나의 자원을 여러 스레드가 지원할 때 자원에 접근하는 순서에 따라 결과가 달라지는 race condition이 발생하는데 이를 해결하는 방법입니다.

 

Collections 클래스

Collections는 Collection의 자손 타입 객체를 다루기 위한 각종 메서드를 지원하는 유틸 클래스입니다.

자세한 메서드들은 Java API 공식 문서를 참고 바랍니다.

https://docs.oracle.com/javase/8/docs/api/?xd_co_f=dfa207c4-5f97-40f7-8cef-05a352e2b7bf 

Java Platform SE 8

 

ArrayList에 데이터 삽입하기

1. 삽입할 데이터 크기 만큼 배열의 사이즈 늘림
2. index 3 부터 값들을 한 칸씩 이동
3. 빈칸에 연속적으로 데이터 삽입

 

ArrayList에 저장된 데이터 삭제하기

1. index 3 이후 값들을 왼쪽으로 한 칸씩 이동(복사후 덮어쓰기)
2. 마지막 데이터를 null로 변경
3. 삭제한 데이터수 만큼 배열의 사이즈 감소

ArrayList의 데이터를 삭제할 때 맨 마지막 값을 지워나가야 성능 저하가 일어나지 않습니다.
왜냐하면 데이터를 한 칸씩 이동시키는 부가 작업이 없기 때문에...

---

배열의 장단점

ArrayList는 배열을 기반으로 했지만 LinkedList는 배열의 단점을 보완한 자료구조입니다.

따라서 LinkedList를 알아보기 전에 배열의 장단점에 대해서 먼저 알아보겠습니다.

 

장점

배열은 구조가 단순하고 데이터가 연속적인 것이 특징입니다.

데이터가 연속적이어서 배열 맨 뒤에 연속적으로 데이터를 추가/삭제하는 과정이 빠릅니다.(이를 순차적인 데이터라고 합니다.)

 

또한 데이터를 읽는데 걸리는 시간이 짧습니다.

그이유는 배열의 n 번째 요소의 주소 = (배열의 메모리 주소 + 데이터 타입 크기 * n)으로 빠르게 찾을 수 있기 때문입니다.

배열을 아래 그림과 같이 선언했을 때,

참조 변수 i에는 배열 객체의 메모리 주소값이 저장됩니다. 

예를 들어 0x100이라고 하겠습니다.

int의 데이터 타입 크기는 4 Byte이므로 n 번째 요소의 주소는 (0x100 + (4 * n)B)가 됩니다.

 

단점

배열의 단점은 크기가 고정이라서 변경이 불가하다는 것입니다.

더 큰 배열을 생성하려면 새로운 배열을 생성(1) 후 복사하고(2) 참조 변경(3)의 번거로운 과정을 거쳐야 합니다.

 

또한 비순차적인 데이터를 추가, 삭제할 때 시간이 오래 걸립니다.

ArrayList에서 중간에 데이터를 삽입하는 과정만 봐도 삽입할 공간을 확보하고 데이터를 한 칸씩 이동시키고 하는 번거로운 과정을 거쳐야 합니다.

---

LinkedList

LinkedList는 배열의 단점을 보완한 자료구조입니다.

Array와 다르게 불연속적으로 존재하는 데이터를 연결시킨 것입니다.

그러나 비순차적인 데이터가 저장되있어서, 데이터를 찾고 싶으면 List의 Head부터 순차적으로 탐색해야해서 Array보다 탐색 속도가 느립니다.

LinkedList에서 데이터 하나의 단위를 Node라고 부르며, Node안에는 현재 Node의 값과 다음 Node의 주소값을 멤버로 가집니다.

class Node{
	Object data;
	Node next;
}

 

LinkedList의 데이터 삽입

1. Node 생성
2. 생성된 Node 이전의 Node의 참조를 생성된 Node로 변경
3. 생성된 Node의 참조를 설정

 

LinkedList의 데이터 삭제

1. Node 삭제
2. 삭제된 Node의 이전 Node의 참조 변경

 

Doubly LinkedList

탐색 속도가 느린 LinkedList의 단점을 보완하기 위해, Node에 앞뒤 주소 정보(prev, next)를 저장하여 탐색 속도를 보완한 자료구조입니다.

탐색시 List의 맨 앞과 맨 뒤에 포인터를 각각 둬서 좀더 빠르게 탐색합니다.

 

 

Doubly Circular LinkedList

Doubly LinkedList는 head Node의 prev에는 null, tail Node의 next는 null이었습니다.

Doubly Circular LinkedList는 head Node의 prev에는 tail Node의 주소값을 가리키고, tail Node의 next에는 head Node의 주소값을 가리켜서 원형으로 연결한 자료구조입니다.

 

 

ArrayList 와 LinkedList 성능 비교

List 인터페이스의 대표적인 두 자료구조의 성능을 비교하면 다음과 같습니다.

• 순차적 데이터 삽입/삭제: ArrayList > LinkedList
• 비순차적 데이터 삽입/삭제: LinkedList > ArrayList
• 접근 시간(탐색 시간): ArrayList > LinkedList

---

Stack

Stack은 나중에 들어온 값이 가장 먼저 빠져나가는 LIFO(Last In First Out) 자료구조입니다.

push() 함수로 데이터를 추가하고, pop() 함수로 데이터를 삭제합니다.

Stack같이 순차적 데이터를 다룰 때는 Array로 구현하는게 유리합니다.

Stack stack = new Stack();

스택은 수식 계산, 괄호 검사, 워드의 undo/redo, 웹 브라우저의 뒤로가기/앞으로가기 할 때 사용합니다.

 

 

Queue

Queue는 먼저 들어온 데이터가 가장 먼저 빠져나가는 FIFO(First In First Out) 자료구조입니다.

Offer()함수로 데이터를 추가하고, poll() 함수로 데이터를 삭제합니다.

Queue 같은 비순차적 데이터를 다룰 때는 LinkedList로 구현하는게 유리합니다.

Queue queue = new LinkedList();  //Queue는 interface라서 객체 생성 불가

큐는 최근 사용 문서, 인쇄 대기 목록, Buffer 등을 구현할 때 자주 사용합니다.

 

 

 

Ref.

https://coding-factory.tistory.com/550

https://www.nextree.co.kr/p6506/

https://backgomc.tistory.com/31

https://habr.com/en/post/506660/

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)