💡 자료구조란?
여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.
Array & Linked List
1. Array
- 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조입니다.
1-1. Array의 특징
- 고정된 저장 공간 (fixed-size)
- 순차적인 데이터 저장 (order)
Array의 장점은 lookup과 append가 빠르다는 점 입니다.
조회를 자주 해야되는 작업에서 Array 자료구조가 많이 쓰입니다.
Array의 단점은 fixed-size 특성상 선언 시에 Array의 크기를 미리 정해야한다는 점 입니다. 이는 메모리 낭비나 추가적인 overhead가 발생할 수 있습니다.
시간복잡도
2. Dynamic Array
-
Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다 많은 갯수의 data가 추가되면 저장할 수 없습니다. 이해 반해 Dynamic Array는 저장공간이 가득 차게되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조 입니다.
-
Array의 특징 중에 fixed-size의 한계점을 보완하고자 고완된 자료구조라고 볼 수 있습니다.
3. Linked List
- Linked list는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 그 다음 Node address를 저장합니다. Linked list는 물리적인 메모리상에서는 비연속적으로 저장이 되지만, Linked list를 구성하는 각각의 Node가 next Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조입니다.
3-1. 물리적 메모리 관점에서 본 Linked list - 비연속적
3-2. 논리적 연속성
- 각 Node들은 next address 정보를 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결되어있습니다.
- Array의 경우 연속성을 유지하기 위해 물리적 메모리 상에서 순차적으로 저장하는 방법을 사용하였고, Linked list에는 메모리에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유로운 대신, Next address를 추가적으로 저장해야하기 때문에 데이터 하나당 차지하는 메모리가 더 커지게 됩니다.
아래 [image 1]에서 Linked list가 연속적으로 저장된 것 처럼 보이지만, 실제 메모리상에서는 [image 2]와 같습니다.
[image 1] 논리적 연속성
[image 2] 물리적 불연속성
4. Array vs Linked List
Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조 입니다. Linked lists는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로써 논리적 연속성을 유지합니다.
그래서 각 operation의 시간복잡도가 다릅니다. 데이터 조회는 Array의 경우 O(1), Linked list는 O(n)의 시간 복잡도를 갖습니다. 삽입/삭제는 Array O(n), Linked list O(1)의 시간복잡도를 갖습니다.
-
따라서 얼마만큼의 데이터를 저장할지 미리 알고 있고, 조회를 많이 한다면 Array를 사용하는 것이 좋습니다.
-
반면에 몇 개의 데이터를 저장할지 불확실하고 삽입/삭제가 잦다면 Linked list를 사용하는 것이 유리합니다.
💡 [꼬꼬무 문답]
Q. 어느 상황에 Linked list를 쓰는게 Array보다 나을까요?
- O(1)으로 삽입/삭제를 자주 해야할 때
- 얼마만큼의 데이터가 들어올지 예측할 수 없을 때
- 조회 작업을 별로 하지 않을 때
Q. 어느 상황에 Array를 쓰는게 Linked list보다 나을까요?
- 조회 작업을 자주 해야할 때
- Array를 선언할 당시 데이터 갯수를 미리 알고 있을 때
- 데이터를 반복문을 통해 빠르게 순회할 때
- 메모리를 적게 쓰는게 중요한 상황일 때
- Linked list보단 Array가 메모리를 적게 차지하기 때문에 미리 들어올 데이터의 양만 알고 있다면 Array가 메모리를 더 효율적으로 사용합니다.
