[JAVA] 17. 컬렉션 프레임워크(List, Set, Map) , ArrayList, LinkedList, Stack&Queue

컬렉션 : 여러 객체(데이터)를 모아놓은 것을 의미한다. 

프레임워크 : 표준화, 정형화된 체계적인 프로그래밍 방식 

컬렉션 프레임워크 : 다수의 객체(컬렉션)을 다루기 위한 표준화된 프로그래밍 방식 

-> 컬렉션을 쉽고 편리하기 다룰 수 있는 다양한 클래스를 제공한다. 

컬렉션 클래스: 다수의 데이터를 저장할 수 있는 클래스 

 

 

1️⃣ 컬렉션 프레임워크의 핵심 인터페이스 

컬렉션 프레임워크에서는 컬렉션 데이터 그룹을 크게 3가지 타입이 존재한다고 인식하고 각 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스를 정의하였다. 

 

List 

: 순서가 있는 데이터의 집합, 데이터의 중복을 허용한다. 

ArrayList, LinkedList, Stack, Vector 등 

 

Set 

: 순서를 유지하지 않는 데이터의 집합, 데이터의 중복을 허용하지 않는다. 

HashSet, TreeSet 등 

 

Map

: 키와 값의 쌍으로 이루어진 데이터의 집합, 순서는 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용한다. 

HashMap, TreeMap, HashTable, Properties 등 

 

List 와 Set 을 구현한 컬렉션 클래스들은 서로 많은 공통부분이 있어서 공통된 부분을 다시 뽑아 Collection 인터페이스를 정의할 수 있었지만 Map 인터페이스는 이들과는 전혀 다른 형태로 컬렉션을 다루기 때문에 같은 상속계층도에 포함되지 못한다.

 

컬렉션 프레임워크의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현하고 있으며, 구현한 인터페이스의 이름이 클래스의 이름에 포함되어 있어서 이름만으로 클래스의 특징을 쉽게 알 수 있도록 되어 있다.

 

Vector나 HashTable과 같은 기존의 컬렉션 클래스들은 호환을 위해 설계를 변경해서 남겨두었지만, 가능하면 사용하지 않는 것이 좋다. 

그 대신 새로 추가된 ArrayList와 HashMap을 사용하자!

 

 

- Collection 인터페이스 

Collection 인터페이스는 컬렉션 클래스에 저장된 데이터를 읽고, 추가하고, 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드들을 정의하고 있다. 

 

 

- List 인터페이스

List 인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다. 

 

 

- Set 인터페이스

Set 인터페이스는 중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용된다. 

 

 

- Map 인터페이스

Map 인터페이스는 키Key 와 값Value 을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는 데 사용된다. 

키는 중복될 수 없지만 값은 중복을 허용한다. 기존에 저장된 데이터와 중복된 키와 값을 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남게된다. 

values()에서는 반환타입이 Collection으로 List, Set 어느 컬렉션 클래스가 와도 되지만, KeySet() 에서는 반환타입이 Set이다!

Map 인터페이스에서 값은 중복을 허용하기 때문에 Collection 타입으로 반환하고, 키는 중복을 허용하지 않기 때문에 Set 타입으로 반환한다. 

 

 

2️⃣ ArrayList 

ArrayList 는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스일 것이다. 

ArrayList 는 List 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징이 있다. 

ArrayList 는 Object 배열을 이용해서 데이터를 순차적으로 저장한다. 

선언된 배열의 타입이 모든 객체의 최고 조상인 Object 이기 때문에 모든 종류의 객체를 담을 수 있다. 

 

-> ArrayList 는 List 인터페이스를 구현했기 때문에 저장된 순서를 유지한다는 것을 알 수 있다. 

-> list2에서 list1에 포함된 객체들을 제거하는 부분이다. 

만일 변수 i 를 증가시켜가면서 삭제하면, 한 요소가 삭제될 때 마다 빈 공간을 채우기 위해 나머지 요소들이 자리이동을 하기 때문에 올바른 결과를 얻을 수 없다. 그래서 제어 변수를 감소시켜가면서 삭제를 해야 자리이동이 발생해도 영향을 받지 않고 작업이 가능하다!!

 

 

3️⃣ LinkedList 

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간(접근 시간)이 가장 빠르다는 장점을 가지고 있다. 

 

배열의 단점  

1. 크기를 변경할 수 없다. 

- 크기를 변경할 수 없기 때문에 새로운 배열을 생성해서 데이터를 복사해야한다. 

- 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.

 

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

- 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,

- 배열의 중간에 데이터를 추가하려면, 빈 자리를 만들기 위해서 다른 데이터들을 복사해서 이동해야 한다. 

 

배열의 단점을 보완하기 위해서 링크드 리스트 LinkedList 라는 자료구조가 고안되었다.

배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다. 

 

링크드 리스트에서 삭제는 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다. 

단 하나의 참조만 변경하면 삭제가 이루어진다!

배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다. 

 

 

새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다. 

 

 

링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.

-> 이점을 보완한 것이 더블 링크드 리스트(이중 연결 리스트, Doubly Liked List) 이다. 

더블 링크드 리스트는 단순히 링크드 리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드 리스트와 같다. 

더블 링크드 리스트는 링크드 리스트보다 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트보다 더 많이 사용한다. 

 

더블 링크드 리스트의 접근성을 보다 향상시킨 것이 더블 써큘러 링크드 리스트(이중 원형 연결리스트, doubly circular linked list) 인데, 단순히 더블 링크드 리스트의 첫번째 요소와 마지막 요소를 서로 연결시킨 것이다. 

 

1. 순차적으로 추가/삭제 하는 경우에는 ArrayList 가 LinkedList보다 빠르다.

2. 중간 데이터를 추가/삭제 하는 경우에는 LinkedList가 ArrayList보다 빠르다.

 

 

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기 

-> 배열의 경우에는 만일 인덱스가 n인 요소의 값을 얻어오고자 하면 단순히 이 식을 계산함으로써 해결된다!!!

 

-> ArrayList 는 배열기반(연속적), LinkedList는 연결기반(불연속적) 

 

 

 

4️⃣ Stack과 Queue

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)으로 되어 있고,

큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 되어 있다. 

 

 

순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하지만,

큐는 데이터를 꺼낼 때 항상 첫번째 저장된 데이터를 삭제하기 때문에 ArrayList 와 같은 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼때 마다 빈 공간을 채우기 위해서 데이터의 복사가 발생하므로 비효율적이다 

그래서 큐는 ArrayList 보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다. 

 

-> 자바에서는 스택을 Stack클래스로 구현하여 제공하고 있지만 큐는 Queue 인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 

대신 Queue 인터페이스를 구현한 클래스들이 있어서 이 들 중 하나를 선택해서 사용하면 된다. 

Queue 인터페이스에 정의된 기능을 사용하고 싶다면 'All known Implementing Classes' 에 적혀있는 클래스들 중에서 적당한 것을 하나 골라 잡아서 Queue q = new LinkedList(); 와 같은 식으로 객체를 생성해서 사용하면 된다.