Java의 List 컬렉션에 대해 알아보자

wnajsldkf·2022년 10월 7일

Java

목록 보기

9/19

List 컬렉션 클래스

요소의 저장 순서가 유지된다.
같은 요소의 중복 저장을 허용한다.

List 컬렉션 클래스

ArrayList<E>
LinkedList<E>
Vector<E>
Stack<E>

ArrayList< E >

내부적으로 배열을 이용하여 요소를 저장한다.

인덱스를 이용해 배열 요소 접근
크기를 변경할 수 없으므로, 크기를 늘리기 위해 새로운 배열을 생성하고 기존의 요소를 옮기는 복잡한 과정을 거친다.
- 자동으로 수행되나, 요소의 추가 및 삭제 작업에 걸리는 시간이 매우 길다.

시간 복잡도

get/set
배열의 index를 통해 빠르게 접근한다.
=> 상수 시간의 시간 복잡도를 갖는다.

add
ArrayList는 기본적으로 배열이다. 따라서 중간에 값을 끼워넣는 연산이 불가능하다.
새로운 값을 추가할 때, List의 크기가 생성되어 있는 배열의 size(default: size = 10)보다 커지면 이전 크기의 2배가 되는 배열을 생성해 배열 전체를 복사하여 새로운 배열에 복사하고 제일 뒤에 값을 추가한다.
즉, 기존에 있던 배열에서 추가하고 싶은 index부터 마지막 index까지 배열을 한칸씩 뒤로 미룬다.
=> 해당하는 인덱스를 찾아가는 시간(O(1)) + 배열을 복사하는 시간(O(n)) = O(n)

매우 작은 값인 O(1)은 무시

remove
삭제된 index + 1부터 마지막 index까지 한 칸씩 앞으로 당긴다.
=> O(n)의 시간 복잡도

get/set을 자주 사용하는 경우(index를 통해 접근할 때) 유용하다.
공간 복잡도의 경우 연속된 메모리안에 저장되어 낭비되는 공간이 없어 속도가 빠른 경우가 발생한다.

LinkedList< E >

연결 리스트를 이용하여 요소를 저장한다.

배열은 저장된 요소가 순차적으로 저장되나, 연결 리스트는 저장된 요소가 비순차적으로 분포되며, 이러한 요소 사이를 링크(link)로 연결하여 구성한다.

단일 연결 리스트(singly linked list)
다음 요소를 가리키는 참조만을 가지는 연결리스트를 말한다.

저장과 삭제 작업이 다음 요소를 가리키는 참조만 변경한다.
단, 현재 요소에서 이전 요소로 접근하기 어렵다.

이중 연결 리스트(doubly linked list)
이전 요소를 가리키는 것이 어려운 단일 연결 리스트의 단점을 극복한다. 이전 요소를 가리키는 참조를 함께 갖는다.

시간 복잡도

get/set
비순차적으로 저장되어 있다. 해당하는 index에 대한 값을 얻어올 때 시작이나 끝에서부터 해당 index까지 순차적으로 접근하여 확인하고 값을 얻는다.
=> 시간 복잡도는 O(n)이다.

add

일반적인 경우
추가를 원하는 index에 도달할 때까지 순차 접근을 하여 O(n)이 발생한다. 연결하는 작업은 next와 prev를 연결하므로 상수 시간이 O(1)의 복잡도이다.
=> 시간 복잡도는 O(n)이다.
시작이나 끝에 요소를 추가하는 경우
head(시작)와 tail(끝)을 갖는 구조이다. 각각을 찾아가는데 O(1)이라는 시간 복잡도를 갖는다.
=> 시간 복잡도는 O(1)이다.