Data Structure - Array vs Linked List

Array(배열)

➤ 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조
➤ 선언할 때 크기와 데이터 타입을 지정해야함
➤ Index를 사용하여 검색이 편함 = O(1)

❗️❗️ 데이터가 계속 늘어날 때 or 최대 사이즈를 알 수 없을 때 사용하기 부적절함
❗️❗️ 데이터를 삽입 / 삭제에 부적절

ArrayList(List)

➤ Array의 문제점을 해결하기 위해서 사용
➤ 크기를 미리 정하지 않지만, 대신 순서가 중요해짐
➤ 크기를 정하지 않아서 데이터를 추가 or 삭제해도 Array가 갖는 문제는 없음

❗️❗️ 다만, 데이터를 추가하고 삭제하는데 시간이 오래걸림 = O(n)

Linked List(연결 리스트)

➤ 중간에 데이터를 삽입 or 삭제하여도 전체를 돌지 않고 주소 값만 수정 후 연결하여 빠르게 진행이 가능함

❗️❗️ 하지만, k번째 원소에 접근할 때는 Array, ArrayList에서는 index를 검색하여 빠르지만, Linked List는 처음부터 연결 순서대로 살펴봐야함 따라서, Time Complexity = O(n)