1. Arrays vs Linked List

Array

 

Array는, 인덱스와 인덱스에 대응하는 데이터들도 이루어진 자료구조이다.

 

따라서 인덱스로 해당 원소에 접근할 수 있다. 따라서 해당 원소의 인덱스 값을 알고 있으면 O(1)에 접근 할 수 있다.

즉, Random Access가 가능하다는 장점이 있다.

 

하지만, 삭제 또는 삽입의 과정에서 해당 원소에 접근해 작업을 완료한 후 (O(1)의 시간복잡도 발생) 추가적인 작업이 필요하다.

 

삭제의 경우, 삭제한 원소를 기준으로 더 큰 인덱스를 가지고 있는 원소들을 오른쪽으로 이동시켜야 하므로 최악의 경우 O(n)의 시간복잡도가 발생한다.

 

삽입의 경우, 삽입한 원소를 기준으로 더 큰 인덱스를 가지고 있는 원소들을 오른쪽으로 이동시켜야 하므로 최악의 경우 O(n)의 시간복잡도가 발생한다.

 

Linked List

 

Linked List는, 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

데이터를 담고있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 

따라서 노드의 포인터만 다른 노드로 변경해준다면 삭제와 삽입을 O(1) 만에 해결할 수 있다.

 

하지만, Search 과정에서 Linked List는 Array와 다르게 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문에 

해당 원소를 찾기 위해 최악의 경우 O(n)의 시간복잡도가 발생한다.