Array vs Linked List

Array

가장 기본적인 자료구조인 Array 자료구조는 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스로 해당 원소에 접근할 수 있다. 이는 인덱스만 알고 있다면 O(1) 시간에 해당 원소에 접근할 수 있음을 의미한다. (Random access가 가능)

그러나 삭제 또는 삽입 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)) 또 한 가지 작업을 추가적으로 해줘야 하기 때문에 시간이 더 걸리게 된다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 빈공간이 생김을 의미한다. 따라서 삭제한 원소 뒤에 위치한 원소들을 shift해야 하는 비용이 발생하고 이 경우 시간 복잡도는 O(n)이 된다. 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity의 worst case는 O(n)이다.

삽입의 경우에도 만약 첫번째 자리에 새로운 원소를 추가하게 되면 다른 모든 원소들이 뒤로 1 shift되어야 하므로 O(n)의 시간이 소요된다.

요약

• 논리적 저장, 물리적 저장 순서 일치
• 인덱스로 바로 접근 가능. O(1) => Random access 가능 (장점)
• 삽입, 삭제 시 다른 원소들의 shift 연산이 필요하여 O(n)의 추가적인 연산이 발생 (단점)

Linked List

Array의 단점을 보완하기 위해 등장한 것이 Linked List이다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이 부분만 수정해준다면 삭제와 삽입을 O(1) 안에 해결할 수 있다.

그러나 Linked List에도 문제점은 존재한다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search하는 과정에 있어서 첫번째 원소부터 다 확인해봐야 한다는 것이다. Array와 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문에 이러한 문제가 존재하게 된다. 이것은 일단 삽입하고 정렬하는 것과 같다. 이 과정으로 인해 어떠한 원소를 삭제 또는 추가하고자 했을 때 그 원소를 찾기 위해 O(n)의 시간이 추가적으로 발생한다.

결국 Linked List 자료구조는 search에도 O(n)의 시간 복잡도가 필요하고 삽입, 삭제에도 O(n)의 시간 복잡도가 필요하다. Linked List는 Tree 구조의 근간이 되는 자료구조이고, Tree에서 사용했을 때 매우 유용하다.

요약

• 각 원소들이 자기 자신 다음의 원소가 어떤 원소인지만 기억
• 맨 앞이나 맨 뒤에 삽입/삭제 시 O(1)에 처리 가능
• 위치를 search하는데에 O(n) 연산 발생, 삽입/삭제에도 O(n) 연산 발생
• Tree 구조에 유용

결론

• 데이터 접근이 주 업무일 경우
  Array 사용
• 데이터 수정이 주 업무일 경우
  Linked List 사용