Array vs Linked List

Array

가장 기본적인 자료구조

논리적 저장 순서와 물리적 저장 순서가 일치한다.

• 따라서 인덱스로 해당 원소에 접근이 가능하다.
• 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1) 시간 내에 해당 원소에 접근가능하다.
• Random Access가 가능하다.

하지만, 삭제 또는 삽입 과정에서 해당 원소에 접근 후(O(1)), 또 한 가지의 작업을 추가로 해줘야한다.

• 시간이 더 소요
• 배열의 원소 삭제 시 , 배열의 연속적인 특징이 깨지고, 빈 공간 발생
• 삭제한 원소의 빈 공간을 채우기위해 큰 인덱스의 원소들을 shift해야한다. 이럴경우 시간 복잡도는 O(n)이 된다.

Linked List

각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다.

해당 부분만 다른 값으로 변경하면 삭제와 삽입을 O(1) 만에 해결할 수 있다.

하지만, 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search과정에 있어 첫번 째 원소부터 다 확인해야함

• Array와 달리 논리적 , 물리적 저장 순서가 일치하지 않음
• 어떠한 원소를 삭제 or 추가시, 그 원소를 찾기 위해 O(n)의 시간이 추가적으로 발생