Array & Linked list

자료구조의 종류 중 하나인 Array와 Linked list의 차이를 알아보겠습니다.

1. Array

먼저 Array는 논리적 저장 순서와 물리적 저장 순서가 일치합니다. 즉, index로 해당 element에 접근할 수 있다는 것입니다. 그렇기 때문에 찾고자 하는 원소의 index값을 알고 있다면 Big-O(1)에 해당 원소로 접근할 수 있습니다. (random access가 가능하다는 장점)

 But, 삭제 혹은 삽입 과정에서는 해당 원소에 접근해 작업을 완료한 뒤(O(1)), 또 한가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸립니다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을때, 배열의 연속적 특징이 깨져 빈 공간이 생기게 됩니다. 따라서 삭제한 원소보다 큰 indedx를 갖는 원소들을 shift해야하는 cost가 발생하고 이 경우 시간 복잡도가 O(n)가 됩니다. 여기서 Array 자료구조에서 삭제 기능에 대한 시간복잡도의 worst case는 O(n)이 됩니다.

 삽입의 경우도 마찬가지로, 만약 첫 번째 자리에 새로운 element를 추가하고자 한다면 모든 원소들의 indeex를 1씩 shift 해줘야 하기 때문에 O(n)의 시간을 요구하게 됩니다.

 

 

2. Linked List

 위에 상기된 문제점을 해결하기 위한 자료구조가 Linked list 입니다. 각 element들은 자기 자신 다음에 어떤 element인지만을 기억하고 있습니다. 따라서 이 부분만 다른 값으로 바꿔주면 삭제, 삽입을 O(1)만에 해결할 수 있습니다. 

 But, 원하는 위치에 삽입을 하고자 하면 원하는 위치를 탐색하는 과정에 있어 첫 원소부터 다 확인해봐야 합니다. 이는 Array와는 달리 논리적 저장순서와 물리적 저장순서가 일치하지 않기 때문입니다. 이것은 일단 삽입하고 정렬하는 것과 마찬가지입니다.

 이 과정때문에 어떠한 element를 삭제 or 추가하고자 했을 때, 그 element를 찾기 위해 O(n)의 시간이 추가적으로 발생합니다. 

 

 결국 Linked list 자료 구조는 탐색에도 O(n)의 시간 복잡도를 갖고 삽입, 삭제에 대해서도 O(n)의 시간 복잡도를 갖습니다. 

 목적과 상황에 따라 다르지만 Linked list는 데이터 삽입/삭제가 자주 일어나야 할 때 사용하고, Array는 데이터 삽입/삭제가 많이 없는 대신 데이터의 접근이 자주 일어나야 한다면 사용하는 구조라고 보면 됩니다.