배열와 리스트 - 메모

Array(배열) : 연속된 메모리 공간에 요소를 저장
모든 요소에 동일한 데이터 형식과 메모리 다른 위치에 존재할 수 없다.
ex) [1, 2, 3, 4, 5]

List(리스트) : 요소를 연결된 노드(분기)로 저장하며, 각 노드는 데이터와 다음 노드에 대한 참조(포인터)를 가지고 있다.
ex) [1] - [2] - [3] - [4] - [5]

'Array'는 index를 사용하여 직접 접근해 빠르게 요소를 찾을 수 있지만 'List'의 경우 선형으로 이루어져있기 때문에 [5]를 찾기 위해선 선형 노드에 분기로 영향을 미친다.

'Array'의 index 값을 알고있는 경우 시간복잡도 O(1)
모르는 경우는 O(n)
'List'의 경우 선형 구조 이므로 절대적으로 O(n)

마지막. 배열의 경우가 시간 복잡도를 최적화할 수 있는 방법이 다양하다.

'ArrayList'와 'LinkedList' 나중에..

자바에서 ArrayList와 LinkedList는 List 인터페이스를 구현한 구현체이다.