자료구조 Array VS Linked List - mapc-team/document GitHub Wiki

Array

• 논리적 저장 순서와 물리적 저장 순서가 일치 -> 인덱스(Index)로 해당 원소(Element)에 접근가능
• 찾고자하는 원소의 인덱스 값을 알면 O(1)로 해당 원소에 접근 가능 -> Random Access 가능
• 삭제, 삽입시 작업 완료 후 삭제, 삽입한 원소보다 큰 인덱스를 가지는 원소를 shift해줘야 하기 때문에 시간 복잡도는 O(n)이다.

Linked List

• 논리적 저장 순서와 물리적 저장 순서 불일치 -> 탐색시 O(n)
• 각각의 원소들은 자기 자신 다음에 어떤 원소인지만 기억 -> 삽입, 삭제 자체는 O(1) but 삽입과 삭제를 위해 탐색이 필요하므로 실제로는 O(n)
• Linked List는 Tree 구조의 근간이 되는 자료구조