💡 [자료구조] Array vs. LinkedList

Array(배열)

데이터 접근에 유리. 데이터 size가 정해져 있을 때 유리.

• 정적인 자료구조로, 컴파일 타임에 크기가 결정된다.
• 인덱스를 통해 데이터에 빠른 접근이 가능하다. O(1)
• 데이터의 삽입/제거 시 O(N)
• 사용할 자료의 사이즈가 명확할 때, 데이터의 삽입/제거가 아주 빈번한 게 아니라면 LinkedList보다 효율적이다.

Linked List(연결리스트)

데이터 추가/삭제에 유리.

• 동적인 자료구조로, 런타임에 크기가 계속해서 변한다.
• 인덱스를 사용하지 않기 때문에 데이터의 조회가 느리다. O(N)
• 트리 구조의 근간이 되는 자료구조이다.
• 양측 끝에 데이터의 삽입/제거 시 O(1), 중간 삽입/제거 시 O(N). 이 경우에도 Array보다 빠르다.
• 논리 구조상 Linked List가 Array보다 효율적인 경우가 많지만, 일반적으로 Array를 사용하는게 더 빠른 경우가 많다. 이는 Linked List가 동적으로 크기가 변하기 때문인데, 메모리를 할당하고 해제할 때 시스템 콜을 사용하기 때문이다. 시스템 콜은 시간복잡도에 포함되지 않지만 시간이 꽤 걸리는 작업이다.