자바 리스트
Collection 인터페이스
Java.util 패키지 내 컬렉션 프레임워크의 핵심 인터페이스 중 하나로
자바에서 다양한 컬렉션(데이터 그룹)을 다루기 위한 메서드를 정의한다
List, Set, Queue 등 다양한 하위 인터페이스와 함께 사용되며
이를 통해 데이터를 리스트, 세트, 큐 등의 형태로 관리할 수 있다
List 인터페이스
java.util 패키지 내 컬렉션 프레임워크의 일부로
객체들의 순서가 있는 컬렉션을 나타내며, 중복을 허용한다
배열과 비슷하지만 크기가 동적으로 변화하는 데이터를 다룰 때 유연하게 새용할 수 있다
ArrayList, LinkedList 와 같은 여러 구현 클래스를 가지고 있으며
각 클래스는 List 인터페이스의 메서드를 구현한다
자바의 ArrayList
java.util.ArrayList
- DEFAULT_CAPACITY = 10
- CAPACITY 를 초과하면 배열 크기(CAPACITY)를 50% 정도 늘린다
- System.arraycopy() 를 통해 시스템 레벨에서의 배열 고속 복사 연산으로 배열을 늘린다
- 배열 내의 값을 삭제하더라도 배열의 전체 크기를 줄이지 않는다 (크기를 줄이는 메서드는 제공 함)
- 배열을 명시적으로 늘리는 메서드를 제공한다
배열 고속 복사 연산
ArrayList 의 맨 앞에 값을 추가/삭제 시 대략 10배 이상,
평균적인 위치에 추가/삭제 시에도 대략 10배 이상의 성능 향상을 준다
왜 배열 크기를 다시 회수하지 않는지
배열의 값이 줄어들더라도 배열의 크기를 다시 줄이지 않는 이유는
어떤 서비스가 지속된다고 가정했을 때
데이터가 줄어드는 일보다는 늘어날 확률이 높고
줄어든다 하더라도 언젠가 늘어난 현재 크기 만큼은
다시 사용할 것으로 기대되기 때문에
줄였다 다시 늘리는 비용을 들이기 보다는
다시 늘어날 날을 기다리며 메모리를 확보해 두는 것이다
가용 메모리 용량이 늘어난 현재의 웹에서는 그게 더 비용이 저렴하기 때문
배열 고속 복사 연산을 사용하더라도 용량이 커지면 연산 비용이 매우 커진다
자바의 LinkedList
java.util.LinkedList
- 이중 연결 리스트 구조 (첫번째 노드와 마지막 노드 둘 다 참조)
- next 와 prev 를 함께 가지고 있어 앞/뒤로 이동할 수 있다
- 메모리를 조금 희생하여 성능을 향상 시킨 LinkedList
- 값을 뒤에 추가시 O(n) 만큼의 성능 향상이 있다
시간 복잡도와 실제 성능
이론적으로는 LinkedList 가 ArrayList 보다 중간 삽입이 빠를 것 같지만
실제 성능은 요소에 접근하는 속도, 메모리 할당 및 해제 비용,
CPU 캐시 활용도 등 다양한 요소에 영향을 받는다
ArrayList 는 메모리 내 데이터의 위치가 연속적이기 때문에
위에서 설명한 모든 것들이 상대적으로 빠르다
대부분의 경우 ArrayList 의 성능이 우세하지만
주로 데이터를 앞쪽에서 추가하거나 삭제할 일이 있다면 연결 리스트를 사용한다
