자료구조) array와 Linked-List

array와 Linked-List 모두 기본적인 자료구조입니다. 하지만 둘은 memory에 적재되는 방법의 차이로 여러 차이점이 생깁니다. 

Array

array는 정해진 크기의 메모리에 연관된 데이터를 연속적으로 적재합니다. 

물리 메모리 상에 봤을때, array의 데이터들이 하나의 4bit씩 차지하며 연달아 있는 것을 볼 수 있습니다. 

 

연달아 붙어 있기 때문에 특정 데이터에 접근하는 것이 굉장히 빠릅니다.

array의 첫 데이터 시작부터 접근하고자 하는 데이터의 인덱스(offset)를 산술적으로 더하면 바로 데이터를 찾을 수 있습니다.(O(1), random Access)

마지막의 데이터를 추가(append)하거나 데이터를 삭제하는 것도 마찬가지 입니다. (O(1))

하지만 중간에 데이터를 삽입(insertion)하거나 데이터를 삭제하는 경우는 O(n)으로 다소 느립니다. array가 정해진 크기의 메모리에 연달에 데이터가 있기 때문에 중간에 삽입/삭제가 일어났을 경우, 뒤의 데이터들을 이동(shift)시켜줘야 합니다.

또한 어떤 조건을 가진 데이터를 찾기 위해서는 모든 데이터를 한번씩 확인해야 하기 때문에 O(n)의 시간 복잡도가 걸립니다.

 

array는 complie 단계에 stack 위치에 메모리가 할당됩니다. 이를 Static memory allocation이라 합니다. 

그렇기 때문에 array가 생성될 당시보다 큰 데이터를 저장할 수 없습니다.

 

그렇다면 어떻게 array에 할당된 메모리보다 더 큰 데이터를 적재할 수 있을까요? 

방법은 Dynamic Array나 Linked-List를 이용하는 방법이 있습니다. 

 

Dynamic Array

Dynamic Array는 처음에 할당된 Memory보다 더 큰 데이터가 들어오게 될때, 메모리를 resize하는 array입니다.

여기서 resize를 보다 정확히 설명해 드리자면,

할당된 size보다 더 큰 size를 가진 array를 만들어 기존 array의 데이터를 옮기고 나서(O(n)) 기존의 array를 삭제(메모리에서 지우는 ) 것입니다. 

resize 하는 방법으로는 대표적으로 Doubling이 있습니다. Doubling은 array의 크기를 2배씩 늘리는 것입니다. 

 

앞선 Array에서는 데이터를 append할때 시간복잡도가 O(1)이라고 했는데, resize할때는 O(n)이 걸립니다. 

그렇다면 Dynamic Array에서 append할 때의 시간 복잡도는 어떻게 될까요? 

일반적으로 append는 자주, resize는 가끔 일어나기 때문에 resize의 시간을 append가 나누어 가질 수 있어서 amortized(분할상환) O(1)이라고 얘기할 수 있습니다. 

확실히 resize가 시간이 오래 걸리다 보니까, 애초에 array 사이즈를 많이 할당받기도 하는데, 이렇게 될 경우 메모리 낭비도 발생할 가능성이 있습니다. 

 

Linked List

링크드 리스트는 array의 size가 한정되있다는 점의 보완책으로 볼 수 있습니다. 

링크드 리스트는 Node 구조로 이루어져 있는데, 데이터와 다음 Node를 가르키는 주소(Pointer)의 8bit로 구성되어 있습니다. 

링크드 리스트는 Array와 달리 메모리 상에서 연달아 위치해 있지 않아 물리적 연속성은 없지만, Node 구조로 다음 Node를 가르키다 보니, 논리적 연속성을 가지고 있습니다. 

 

LinkedList는 runtime에서 새로운 node가 생길때 메모리를 할당 받습니다. Dynamic memory Allocation이라고 하며, Heap 영역에 할당받습니다. 

 

Linked리스트는 중간에 데이터 삽입/ 삭제가 빠릅니다. Pointer를 새로운 주소로 바꿔 끼워주기만 하면 되기 때문에 O(1)의 시간복잡도를 갖습니다. 

반면 특정 요소에 접근할때, 처음부터 순차적으로 Node를 거쳐가며 접근하기 때문에 O(n)의 시간 복잡도를 갖습니다. 

(search 도 O(n)의 시간 복잡도를 갖습니다)

 

양방향  Linked List

Linked List 중에 양방향 Linked리스트도 있습니다. 

일반 LinkedList는 뒤에 있는 요소의 주소만 node에 기록해 놓는데, 양방향 Linked List는 앞, 뒤의 요소 모두 node에 기록해 놓습니다. 

즉 12bit를 사용해서 Linked List를 구현하는 셈입니다. 

양방향으로 연결되어있어서 노드 탐색이 양방향으로 가능합니다. 

 

Array v.s. Linked List

메모리에 적재하는 방식의 차이점으로 인한 특징들로 메모리에 데이터를 적재하려고 하면, 둘의 장점이 극대화 되는 방식으로 방식을 선택하면 됩니다. 

Array

- 적재할 데이터의 개수를 명확히 알고 있을때

- 데이터 참조할 일이 많을 때

- 메모리 크기 관리가 중요할때(4bit)

Linked List

- 적재할 데이터의 개수가 정확하지 않을때

- 데이터 삽입/삭제가 빈번하게 일어날때 

 

이상으로 Array와 LinkedList 정리였습니다.