List Interface

List는 순서가 있는 컬렉션이고 중복을 허용한다.

인덱스로 모든 요소에 접근할 수 있다.

 

ArrayList

크기가 고정되어 있는 Array를 개선한 크기 조절 가능한 Array이다.

Array이기 때문에 index를 통한 엑세스가 빠르다.

비동기식이기 때문에 여러 개의 스레드에서 동시에 접근할 수 있다.

 

LinkedList

List 및 Deque 인터페이스를 구현

ArrayList와 마찬가지로 비동기식

내부적으로 연결 리스트를 이용하여 저장한다.

 

Stack

LIFO 구조

Vector의 5가지 메서드만 상속받아 사용

• boolean empty()
• E peek() - 스택의 최상단 요소를 반환
• E pop() - 스택의 최상단 요소를 반환하며 제거함
• push(E e) - 스택의 최상단에 요소를 삽입
• int search(Object o) 객체의 위치 반환, 최상단부터 0이 아닌 1부터 시작 

ArrayList vs Array

• Array는 원시 타입이나 Object 둘 다 가능하지만, ArrayList는  Object만 가능
• Array는 길이 고정, ArrayList는 동적 길이 변경
• Array는 List상속이 아니므로 다양한 기능을 제공하지 않음
• 리스트 크기가 고정된 경우, 값을 저장하거나 탐색 용도로만 쓸 경우, 원시 타입일 경우 Array가 좋다.

ArrayList vs LinkedList

• ArrayList는 Array이기 때문에 O(1) 원소 접근이 가능하다. LinkdedList는 처음부터 데이터를 검색하기 때문에 O(n)
• ArrayList는 중간 데이터 삽입, 삭제 시 다른 데이터를 옮겨야 하며 시간 복잡도는 O(n)이다. LinkedList는 다른 데이터를 옮길 필요가 없으며 시간 복잡도는 O(1)인 것 같지만, 최악의 경우 처음부터 원소를 검색하며 찾아가야 하기 때문에 O(n)의 시간이 추가로 발생한다.
• 추가, 삭제 요구가 많으면 LinkdedList, 검색 요구가 많으면 ArrayList 사용