📝Array란?

연속적으로 인접한 메모리를 할당시켜 데이터를 저장하는 자료구조

1. Array는 저장공간이 고정되어있으며 앞서 말했듯이 순차적으로 데이터를 저장한다는 특징을 가지고 있다. 저장공간이 고정되어있어 메모리에서 오버헤드가 발생할 수 있다.

2. 혹시 할당받은 크기보다 더 많은양의 데이터를 저장해야하는 경우가 많다면 Dynamic Array를 사용하는것도 하나의 방법이다.

Dynamic Array는 기존보다 더 큰 크기의 메모리가 필요할 때, 더 큰 크기의 Array에 데이터를 옮겨 추가로 데이터를 저장할수 있게 하는 자료구조이다. 언뜻보면 Append 시 모든 기존의 데이터를 옮겨야하기 때문에 O(n)의 시간 복잡도로 보이지만 자주 일어나는 작업이 아니기 때문에 일반적으로 O(1)로 표기 한다.

3. 컴파일 시 Stack Memory 영역에 할당 되며 이를 Static Memory Allocation이라 불린다.

📝Linked List란?

연속적이지 않은 메모리에 데이터를 저장하는 자료구조로 Node는 데이터값과 다음 Node의 주소를 갖는것이 특징이다. 논리적으로는 연속성을 가진 자료구조이다.

1. 데이터를 추가할 때 필요한 만큼 저장공간을 할당받기 때문에 메모리 사용에 오버헤드가 발생하지 않을 수 있다.

2. 보통 입력삭제는 빠르다고 하고 조회가 느리다고 하지만 입력, 삭제를 위해 데이터에 접근하는 과정에서 발생하는 시간복잡도가 있어 실직적으로는 O(n)의 시간복잡도를 갖는다.(메모리 할당 해제 또한 시간복잡도에 포함이 되지않음)

3. 런타임 시 Node가 추가될 때마다 메모리를 Heap 메모리 영역에 할당 받고 이를 Dynamic Memory Allocation이라한다.

🧾Array, Linked List 시간복잡도 표

💡결론

- 데이터의 갯수를 알고 있고, 조회를 많이한다면 Array

- 메모리 사용량의 변동이 심하다면 Linked List