List
-
특징
요소들이 정렬되어 있다.
일반적으로 중복을 허용한다.
인덱스를 통해 요소에 접근한다. -
List를 구현하는 클래스들
AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack,Vector
많은 구현 클래스들이 있지만 그중에서도 많이 사용하는 ArrayList, Vector, LinkedList, Stack에 대해 알아보자.
ArrayList
리스트이지만 내부적으로는 배열을 사용한다. 개념적인 배열에 가깝다. 배열은 크기가 정적이기 때문에 가득 차면 확장하는 과정을 거친다.
조회는 O(1), 입력과 삭제는 중간에 삽입하거나, 배열을 확장해야 할 때 최대 O(n)의 시간 복잡도를 가진다.
Vector
ArrayList와 같이 내부 구현이 배열로 된 리스트이다. ArrayList와 달리 모든 작업이 동기화 되어있다.
- ArrayList의 add 메소드
- Vector의 add 메소드
ArrayList와 같이 조회는 O(1), 입력과 삭제는 O(n)의 시간 복잡도를 가진다.
LinkedList
내부적으로 양방향 노드를 사용하여 구현했다. 개념적인 리스트에 가깝다. 하지만 직접 노드에 접근하지 못하기 때문에 조회, 입력, 삭제을 할 때 리스트를 순회하면서 노드를 찾는 과정을 거치기 때문에 O(n)의 시간 복잡도를 가진다.
Stack
Vector를 확장하여 사용하기 때문에 내부적으로 배열을 이용한다.
중간에 있는 요소를 입력하거나 삭제하는 경우가 없기 때문에 조회, 입력, 삭제에 대해서 O(1)의 시간 복잡도를 가진다.
참조
https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/List.html
