y-log

Array

가장 기본적인 자료구조
논리적 저장 순서 = 물리적 저장 순서

인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access 가 가능하다는 장점이 있는 것이다.

하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다.

그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 O(n)이 된다.

삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.

Linked List

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

자기 다음에 어떤 원소인지 기억해두기 때문에 그 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1) 만에 해결가능!

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

결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고, 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다. 

그렇지만 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.

전반적으로 리스트의 사용이 훨씬 좋아보인다.

하지만 일반적인 알고리즘 문제를 풀이할 땐 리스트보다 배열이 훨씬 빠르고 좋다.

왜냐하면 대부분의 알고리즘 연습문제들은 그 메모리 공간의 범위를 주어지기 때문에 배열 선언을 그 MAX치로 잡을 수 있다면, 훨씬 더 편리하고 리스트와는 전혀 다른 속도를 보인다.

리스트의 입력은 추가 과정마다 메모리의 할당이 일어나고 삭제에서는 메모리의 해제가 일어난다. 메모리의 할당과 해제는 O() 시간으로 따지지 않지만, 이런 시스템 콜(System Call)을 사용하는 문구는 시간소요가 꽤 걸린다.

배열이든 리스트이든 단순히 이론을 떠나서 자기가 무엇을 하려는지, 그 목적에 따라 선택하는 것이 좋다.