Java Collection Framework - Collection interface - List

안녕하세요.

 

오늘은 Collection interface에 대해 알아보는 첫 시간입니다. 

 

Collection Interface는 List, Queue, Set 등을 상속하는 실질적 최상위 컬렉션 타입입니다. 

 

다형성을 활용하여 다양한 컬렉션 자료형을 받아 자료를 삽입, 삭제, 탐색 등의 기능을 수행할 수 있습니다. 

 

 

그를 위해 다양한 메서드들을 지원하는데요. 지원되는 메서드는 아래의 표를 참고해주세요.

 

 

오늘은 그중에 List Interface에 대해 알아보고 예제 문제까지 풀어보도록 하겠습니다.

 

List Interface의 경우 아래와 같은 특징을 가지고 있습니다. 

• 1. 저장 순서가 유지되는 컬렉션.
• 2. 같은 요소의 중복을 허용함.
• 3. 배열과 같이 Index로의 접근이 가능함.
• 4. 자료형의 크기가 고정되어 있는 것이 아닌 데이터 양에 따라 동적으로 조절.
• 5. 자료형 사이의 공백을 허용하지 않아 삽입 및 삭제 시 배열의 이동이 발생.

 

List Interface를 상속받고 있는 클래스는 4개가 있습니다. 하나하나 알아보도록 하겠습니다.

• ArrayList
• LinkedList
• Vector
• Stack

 

LIST Interface에서 지원하는 메서드입니다. 

 

먼저 ArrayList를 알아볼까요? 

 

ArrayList는 다음과 같은 특징을 가지고 있습니다.

• 배열을 이용하여 만든 리스트 자료 구조.
• 데이터의 저장 순서가 유지되며 중복을 허용함 
• 데이터 양에 따라 공간을 자동으로 줄이고 늘리며 자동 할당을 수행함.
• 단방향 포인터 구조를 통해 자료에 대한 순차 접근에 강점을 가지며 조회 속도가 빠름.
• 삽입 및 삭제가 느리다. -> 순차적으로 삽입, 삭제하는 경우는 가장 빠름. 

 

그럼 LinkedList에 대해서도 알아볼까요?

 

LinkedList는 다음과 같은 특징을 가지고 있습니다. 

• 노드(객체)를 이용하여 리스트처럼 구현한 자료 구조입니다. -> ArrayList와의 차이 
• 데이터를 중간의 삽입, 삭제가 빈번한 경우 ArrayList 대비 빠른 성능을 보장한다는 장점이 있습니다.
• 중간에 임의의 요소에 접근하는 경우 성능이 좋지 않다는 특징이 있습니다. 
• 자바의 LinkedList는 양방향 포인터 구조로 구성되어 있어 스택, 큐, 트리 등의 근간 자료 구조입니다. 

 

그럼 언제 ArrayList를 사용하고 언제 LinkedList를 사용해야 하는 걸까요? 

삽입 및 삭제가 빈번한 경우에는 LinkedList, 조회가 빈번한 경우에는 ArrayList를 사용하는 것이 유리할 것입니다. 

 

그럼 알고리즘 문제를 기반으로 비교해 볼까요? 

백준 10871x보다 작은 수라는 문제를 확인해 보겠습니다. 

 

해당 문제의 경우 문제의 경우 인덱스 접근이 필수적이며 빈번하게 이루어지고 있습니다. 

 

이런 경우 같은 코드를 사용하고 LinkedList, ArrayList 자료 구조만을 변경하여 테스트를 진행하게 되면 보시는 것과 같이 약 2배 정도의 속도 차이가 발생합니다. 

 

LinkedList는 매번 순차적으로 해당 인덱스까지의 접근이 이루어지기 때문에 조회 성능이 다소 아쉬운 부분을 확인할 수 있습니다. 

 

LinkedList, ArrayList의 차이점을 아시겠죠? 

 

 

 

이어서 Vector Class에 대해 알아보도록 하겠습니다.

 

Vector class의 경우 ArrayList의 구 버전입니다.

다만, 스레드의 접근을 제어하여 Thread-Safe 하다는 장점을 가지고 있습니다. 

현 자바 버전에서는 ArrayList 사용을 권장하고 있으며 동기화가 필요한 경우 Collection.synchronizedList()를 사용하여 ArrayList의 동기화를 권장합니다. 

해당 Class는 구 버전과의 호환성을 유지하기 위해 남겨져 있는 상태입니다.

 

 

마지막으로 Stack에 대해서 알아보도록 하겠습니다. 

• 후입 선출 구조 -> 마지막 원소가 가장 먼저 나감 

Stack의 경우 Vector를 상속받아 사용되고 있어 잘 사용하지 않는 자료 구조로 ArrayDeque를 통한 구현을 권장합니다. 

 

그럼 Stack를 사용하는 문제를 예시로 마무리해 보도록 하겠습니다. 

 

백준 9093 단어뒤집기 

 

풀이의 경우 굉장히 간단하기에 그림으로 대체하도록 하겠습니다. 

또한, ArrayDeque의 경우 양방향으로 삽입, 삭제가 가능하다는 특징을 가지고 있기 때문에 아래와 같이 Stack과 비슷한 형태로 구현이 가능합니다.

 

다음 시간에는 Collection Interface를 상속받고 있는 Queue 자료 구조에 대해 알아보도록 하겠습니다.