ArrayList는 내부적으로 크기를 조절할 수 있는 배열을 사용하고, LinkedList는 각 노드가 이전 노드와 다음 노드를 참조하는 이중 연결 리스트 구조를 사용합니다.
ArrayList는 인덱스로 배열의 위치에 바로 접근할 수 있기 때문에 조회 시간복잡도가 O(1)입니다. 반면 LinkedList는 원하는 인덱스까지 노드를 따라 이동해야 하므로 조회에 O(n)이 걸립니다.
삽입과 삭제의 경우 ArrayList는 중간 요소를 변경하면 뒤의 요소들을 이동시켜야 하므로 O(n)이 걸립니다. 다만 마지막에 요소를 추가하는 작업은 일반적으로 O(1)이고, 배열의 크기를 확장하는 경우까지 고려하면 분할 상환 O(1)입니다.
LinkedList는 첫 번째나 마지막 노드를 변경하거나, 대상 노드를 이미 알고 있다면 참조만 변경하면 되므로 O(1)입니다. 하지만 인덱스로 삽입하거나 삭제하면 먼저 해당 위치를 찾는 데 O(n)이 필요하기 때문에 전체 시간복잡도 역시 O(n)입니다.
따라서 인덱스를 이용한 조회가 많다면 ArrayList가 적합하고, 양 끝에서 삽입과 삭제가 자주 발생한다면 LinkedList를 고려할 수 있습니다.