[자료구조] 배열과 리스트

배열 (Array)

Array는 연관된 데이터를 메모리상에 연속적이고 순차적으로 저장하며, 미리 할당된 크기만큼 저장되는 자료구조입니다.

Array의 장점은 조회(lookup)와 추가(append)가 빠르다는 것입니다. 따라서 조회를 자주 해야하는 작업에서는 Array를 사용합니다.

Array의 단점은 고정된 저장 공간을 사용한다는 특성 상, 선언 시에 배열의 크기를 미리 정해야 한다는 것입니다. 이로인해 메모리 낭비나 추가적인 오버헤드가 발생할 수 있습니다.

 

시간복잡도

접근(access), 추가(append), 마지막 원소 삭제(delete) : O(1)

삽입(insertion), 삭제(deletion), 검색(search) : O(n)

 

미리 예상한 것보다 더 많은 수의 데이터를 저장하느라 배열 크기를 넘어버렸을 때 어떻게 해결할 수 있나요?

1. 기존의 size보다 더 큰 배열을 선언하여 데이터를 옮기는 방법이 있습니다.

모든 데이터를 옮겼다면 기존 배열은 메모리에서 삭제합니다.

2. 다른 방법으로는 Array 대신, 링크드 리스트를 사용함으로써 데이터가 추가될 때마다 메모리 공간을 할당받는 방식을 사용합니다.

 

동적 배열 (Dynamic Array)

동적 배열은 size를 자동적으로 resizing하는 배열입니다. 기존의 고정된 크기를 갖는 정적 배열의 한계점을 보안하고자 고안되었습니다. 동적배열은 데이터를 계속 추가하다가, 기존에 할당된 메모리를 초과하게 되면, 사이즈를 늘린 배열을 선언하고 그곳으로 모든 데이터를 옮김으로써 늘어난 크기의 사이즈를 가진 배열이 됩니다. 따라서 동적배열은 size를 미리 고민할 필요가 없는 장점이 있습니다.

resizing을 하는 여러 방법 중 대표적인 방법으로는 기존 배열의 크기를 2배로 할당하는 Doubling이 있습니다. (시간복잡도 O(n))

 

시간복잡도

append : O(1)

 

동적배열의 장단점을 설명하세요.

동적배열의 장점은 데이터의 접근과 할당이 O(1)의 시간복잡도를 가져 굉장히 빠르다는 것입니다. 또한 맨 뒤에 데이터를 추가하거나 삭제하는 연산도 O(1)의 시간복잡도로 빠릅니다.

(배열은 데이터가 순차적이고 연속적으로 저장되기 때문에 index 접근 방식이 배열의 첫 데이터 주솟값 + offset 만 계산하면 된다.)

 

동적배열은 맨 끝이 아닌 곳에 데이터를 삽입/삭제 할 때 O(n)의 시간복잡도를 가져 느린편입니다.

메모리상에 연속적인 데이터들이 저장되어 있기 때문에, 데이터를 추가/삭제할 때 뒤에 있는 모든 데이터들을 한칸 씩 shift해야하기 때문입니다.

또한, resize를 해야하는 시간이 오래걸리고 필요한 것 이상으로 memory 공간을 할당받아 메모리 낭비가 발생합니다.

 

리스트 (Linked List)

링크드 리스트는 노드라는 구조체로 이루어져 있고, 노드는 데이터 값과 다음 노드의 주솟값을 저장합니다. 링크드 리스트는 물리적인 메모리상에서 비연속적으로 저장되지만, 링크드 리스트를 구성하는 노드가 다음 노드의 주소를 가리킴으로써 논리적인 연속성을 가진 자료구조입니다.

 

시간복잡도

접근, 검색 : O(n)

삽입, 삭제 : O(1)

노드의 다음 주소를 가르키는 부분만 다른 주소 값으로 변경하면 되기 때문에 삽입/삭제 자체는 O(1)의 시간복잡도를 가지지만, 결국 삽입/삭제를 하려는 index까지 도달하는데 O(n)의 시간이 걸리기 때문에 실질적으로 링크드 리스트도 삽입/삭제 시에 O(n)의 시간이 걸린다고 볼 수 있습니다.

 

배열과 링크드 리스트의 차이점

연속성의 구현

배열의 경우엔 연속성을 유지하기 위해 물리적 메모리 상에서 순차적으로 데이터를 저장하는 방법을 사용하였고,

링크드 리스트는 메모리에서 연속성을 유지하지 않아서 메모리 사용이 좀 더 자유로운 대신, 다음 노드의 주소를 추가적으로 저장하기 때문에 데이터 하나 당 차지하는 메모리가 더 커지게 됩니다.

 

삽입/삭제의 시간복잡도

배열은 중간에 데이터를 삽입/삭제 하게 되면 해당 인덱스의 뒤에 있는 모든 원소들은 Shift 해야만 했습니다. 그러다 보니 O(n)의 시간복잡도를 갖습니다.

링크드 리스트는 물리적으로 데이터를 옮길 필요 없이 삽입/삭제 하려는 위치 이전의 노드가 가르키고 있는 다음 노드의 주솟값을 변경하면 되므로 O(1)의 시간복잡도를 갖습니다.

 

메모리 할당

배열은 컴파일 단계에서 메모리 할당이 일어납니다. 이를 정적 할당이라고 하고 이때는 Stack 메모리 영역에 할당됩니다.

링크드 리스트는 런타임 단계에서 새로운 노드가 추가될 때마다 메모리 할당이 일어납니다. 이를 동적 할당이라고 부르며, Heap 메모리 영역에 할당됩니다.

 

정리

따라서 얼마만큼의 데이터를 저장할지 크기를 미리 알고있고, 조회를 많이 한다면 배열을 사용하는 것이 좋습니다. 반면, 몇 개의 데이터를 저장할 지 모르고 삽입/삭제가 잦다면 링크드 리스트를 사용하는 것이 좋습니다.

 

시간복잡도 : O(1) -> O(log N) ->  O(N) -> O(N log N) ->O(N^2) -> O(2^N) -> O(n!)