ArrayList vs LinkedList

• 인덱스 기반 접근을 하기 때문에 조회 성능은 O(1)로 나타난다.
• 배열 기반으로 요소들이 메모리 상 연속적으로 배치된다.
• 만일 크기 조절이 일어난다면 크기 변경마다 새로운 배열을 생성하고 데이터를 복사하는 작업을 진행한다 -> O(n)의 시간 복잡도를 가진다.
• 중간에 요소를 삽입, 삭제 시간이 오래걸린다.(중간에 요소 추가, 삭제 시 배열 요소들을 이동 시켜줘야 하기 때문이다.) -> O(n)의 시간복잡도를 가진다.

LinkedList : 메모리 공간을 연속적으로 사용하지 않고, 이전과 다음 노드를 연결해주는 별도의 메모리 공간을 사용하며 구현한 리스트(배열 기반x)

• 크기 조절이 빠르다(노드의 참조만 변경해주면 됨)
• 중간에 요소를 삽입, 삭제 시 빠르다(노드의 참조만 변경) -> O(1) - 탐색시간 제외
• 인덱스 기반 접근이 느리다(인덱스를 찾아가기 위해서는 순차 탐색 해야함) -> O(n) -> 이전, 이후 노드의 정보만 가지고 있으니깐 계속 타고 이동해야 함
• 메모리 사용이 비효율적이다(이전 노드, 다음 노드를 각 노드마다 참조 정보를 저장하고 있기 때문 -> 추가 메모리 사용)

요약 : 요소의 추가와 삭제가 빈번할 경우 LinkedList를 활용하고, 인덱스 기반 빠른 데이터 접근이 필요할 때는 ArrayList를 사용하는 것이 적합하다.