Array
- 연속된메모리 공간 사용
-> index를 통해 각 요소에 접근 가능,탐색에 필요한 시간복잡도는 O(1) 삽입이나삭제의 경우에는 다른 요소들을 이동(shift)해야 하므로 O(n)의 시간복잡도를 가짐- 크기가 고정적 (컴파일시 정적으로 메모리 할당)
정리: 추가, 삭제 연산이 적고, 탐색이 많은 연산에 유리
Linked List
- 연속되지 않은 메모리 공간 사용
->탐색의 경우 O(n) 시간복잡도를 가짐 삽입과삭제를 노드 간의 연결을 변경하는 방식으로 수행하므로 O(1)의 시간복잡도를 가짐- 크기가 가변적 (런타임에 동적으로 메모리 할당)
정리: 탐색 연산이 적고, 추가, 삭제 연산이 많을 때 사용하면 유리
ArrayList
- Array와 List의 장점을 합쳐놓은 것
-> 배열의 index 식별자 사용 가능, 리스트의 동적 할당 가능 - 배열의 크기를 초과하면, 새로운 더 큰 배열을 생성하고 기존 데이터를 복사해서 옮기는 방식으로 크기를 늘린다(성능 저하)
- 제네릭 사용 가능 (다양한 타입의 데이터 저장)
추가) List와 ArrayList, LinkedList의 차이
List는인터페이스이고, ArrayList와 LinkedList는 이 List를 구현한클래스이다.
Java의 다형성에 의해 아래와 같이 list를 List 자료형으로 선언한 경우, 그 구현체를 ArrayList로 구현할 수 있지만 LinkedList로 구현할 수도 있다.List<Integer> list = new ArrayList<Integer>(); list = new LinkedList<Integer>();
ref.
[기술면접/자료구조] Array & Linked List
[CS 정리] 기술 면접 질문 정리 - 자료구조
