Array의 O(1)의 검색시간의 이점을 가지면서 Linked List의 유연성을 가질 수는 없는가?

1. 두 자료구조체의 비교
--------------------------------------------------
Array
Array의 장점은 우선 O(1)의 검색시간을 갖아 자료구조 중에 가장 빠릅니다. 대신 단점으로 크기가 고정되어 적은 크기를 잡을 경우 새롭게 메모리를 할당하고 기존 메모리의 내용을 새로운 메모리로 복사한 후 기존 메모리를 지워야 하는 문제가 발생합니다. c의 realloc 함수는 아마 이런 식으로 구현되어 있을 것입니다. 반대로 크기를 크게 잡을 경우 사용하지 않는 메모리 부분에 대한 낭비가 발생합니다. 다음 단점으로 Array의 중간에 데이터를 삽입할 경우 삽입데이터 뒤의 내용들을 모두 뒤로 복사해야 하는 문
제가 발생합니다. 메모리 복사 시간을 소모하게 됩니다.

Linked List
Linked List의 장점은 메모리가 고정되어 있지 않아 Array가 가진 메모리 부족시 메모리 할당에 대한 문제가 발생하지 않습니다. 다음으로 중간에 삽입시 Array처럼 삽입 이후의 데이터를 뒤로 복사하는 문제가 발생하지 않습니다. 이런 유연함이 Linked List의 장점입니다. 하지만 단점으로 연결관계를 가지기 위하여 데이터당 포인터(32bit 4byte, 64bit 8byte) 메모리를 낭비하게 됩니다. 다음으로 검색시 O(N)시간으로 O(1)시간에 비하여 상당히 느립니다.


2. 두 자료구조체의 선택
--------------------------------------------------
결과적으로 Array는 검색시간의 장점을 Linked List는 삽입, 삭제와 같은 연산에 장점을 가지게 됩니다. 이 장점들은 동전의 앞면과 뒷면과 같아 한면 만을 장점으로 취할 수 있습니다. 기본적으로는 삽입 및 삭제 연산이 많이 일어나는가? 아니면 검색이 많이 일어나는 가 하는 시간 비용과 예상 사용 메모리양과 허용 가능 메모리양을 고려하여 자료구조를 선택해야 합니다. 다음으로 H/W의 진화에 따라 메모리 복사비용이 점점 줄어든다는 것입니다. 그렇기 때문에 실제적인 것은 Profiling을 하여 이론적으로 생각한 것처럼 실제 동작 H/W에서 메모리 복사비용이 많이 소모되는 가를 고민해야 합니다. 또한 Linked List의 포인터에 대한 메모리 비용은 사용하는 구조체의 크기가 클경우 상대적으로 적은 비용일 수 있습니다.


3. Array의 O(1)의 검색시간의 이점을 가지면서 Linked List의 유연성을 가질 수는 없는가?
--------------------------------------------------
3가지로 나누어서 생각해봐야 합니다.

우선 Array의 데이터가 Sort 되어서 저장되어야 할 경우입니다.
 이럴 경우에는 Tree를 구현하는 것이 메모리 복사 비용을 상대적으로 적게 가져가면서 O(logN)의 비용으로 검색을 할 수 있게 합니다. 또한 O(logN)의 검색비용을 보장하기 위하여 Balanced Tree를 써야 합니다. 또한 삽입 및 삭제에 대한 비용도 O(logN)으로 가져갈 수 있습니다. 이게 DBMS에서 내부구조체로 Balanced Tree의 일종인 B+트리를 사용하는 이유입니다. 참고적으로 Tree는 사용 데이터 크기에 따라 Array와 Linked List 중의 구현 기반을 선택할 수 있습니다. Array기반이 메모리 사용량이 적습니다.

다음으로 Array의 데이터가 Sort 되어야 저장되며 Key값을 가지는 경우 입니다.
 이럴 경우에는 Key값에 대해서 별도의 Index을 만들고 데이터는 Array에 넣을 수 있습니다. 이럴 경우는 검색시나 삽입과 삭제시 Index를 Balanced Tree로 만들 경우 O(logN)의 시간이 소모되며 일반적으로 Linked List로 구현할 경우 O(N)의 시간이 소모됩니다. DB나 데이터 파일의 Index가 이런 구조를 가지고 있습니다. Index없는 경우와의 차이는 여러개의 Key값으로 Index를 만들 수 있다는 점입니다.

마지막으로 Array의 데이터가 Sort되어 있을 필요가 없을 경우 입니다. 
 이럴 경우에는 별도의 남는 메모리의 Linked List인 FreeList를 사용하여 삽입시 FreeList에서 메모리를 가져와 사용하고 삭제시 삭제한 메모리를 FreeList에 넣어야 합니다. 이럴 경우에는 FreeList에 대한 별도의 메모리 비용과 삽입과 삭제시 O(1)의 별도의 처리 비용을 소모하게 됩니다. 또한 FreeList의 포인터들의 메모리 소모 비용을 낭비해야 한다면 반대로 Array에 들어가는 구조체의 크기는 이 메모리 비용을 작게 만들만큼 충분히 커야 합니다. 이런 방법은 OS가 Heap을 관리하거나 우리가 MemoryPool을 구현할 때 흔희 사용하는 방법입니다. 이 방법은 O(1)의 검색시간은 의미가 없습니다. 하는 작업자체가 검색을 하지 않은체로 단순히 메모리 사용의 효율을 높일 때 쓸 수 있기 때문입니다. 추가적으로 Array 중간의 빈공간은 쓰레기 값이 들어 있기 때문에 정렬과 같은 Array를 기반으로 통째로 연산하는 일을 하기 위해서는 문제의 복잡도가 올라가 이 방법은 좋지 못합니다.