리스트(List)
리스트(List)는 순서를 가지고 원소를 저장하는 자료구조이다. sequence라고도 불린다.
구현방법으로는 ArrayList로 구현할 수 있고, LinkedList로 구현할 수 있다.
ArrayList
배열을 기반으로 구성된 List 자료구조이다. Static Array로 구현할 수 있고,
Dynamic Array로도 구현할 수 있다.
배열 Static Array
- 고정된 저장 공간(fixed-size)
- 순차적인 데이터 저장(order)
배열은 선언 시에 size를 정하여 해당 size만큼의 연속된 메모리를 할당 받아 data를
연속적/순차적으로 저장하는 자료구조이다.
위 사진처럼 배열의 size를 5로 정하면 int형 데이터(4byte) 5개를 저장한 메모리 공간인 20byte를 미리 할당 받습니다. 이처럼 고정된 size를 갖게 되기 때문에 Static Array라고 부르기도 한다.
Random Access
배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능하다. 아무리 긴 배열이더라도 한번의 연산으로 원하는 데이터에 바로 접근할 수 있기 때문에 O(1)의 시간 복잡도를 갖는다.
고정된 저장 공간
데이터의 갯수가 정해져 있는 경우에 Static Array를 사용하는 것이 매우 효율적이다.
하지만 정한 size보다 더 많은 데이터를 저장해야 하는 경우 공간이 남아있지 않아 문제가 발생한다.
그렇다고 매번 크기가 엄청 큰 배열을 선언한다면 그만큼 메모리 비효율이 발생한다.
이런 문제점을 해결할 수 있는 것이 바로 Dynamic Array이다.
동적 배열 Dynamic Array
선언 이후에 size를 변경할 수 없는 Static Array와 다르게 Dynamic Array는 size를 늘릴 수 있다.
동적배열(Dynamic Array)에 데이터를 계속 추가하다가 기존에 할당된 size를 초과하게 되면, size를 늘린 배열을
새로 선언하고 그곳으로 모든 데이터를 옮긴다. 그리고 기존 배열은 메모리에서 삭제한다. 이 과정을 resize라고 한다.
resize를 한칸씩 늘린다면 비효율적이므로 일반적으로 2배 큰 크기로 resize한다. 이를 더블링(Doubling)이라고 한다.
Dynamic Array 사용법
선언 시에 배열의 크기를 정하지 않아도 되기 때문에 코딩테스트에서 Dynamic Array를 자주 사용한다.
| Static Array | Dynamic Array | |
|---|---|---|
| access | O(1) | O(1) |
| insert_back | O(1) | amortized O(1) |
| delete_back | O(1) | O(1) |
| insert_at | O(n) | O(n) |
| delete_at | O(n) | O(n) |
Linked List
Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조이다.
⤷ Node는 데이터 값(Value)와 다음 주소 값(Next)로 구성되어 있다.
물리적 비연속적, 논리적 연속적
Linked List는 메모리상에서 비연속적으로 저장이 되어 있지만, 각각의 node가 다음 노드의 메모리 주소 값을 가르킴으로써 논리적으로 연속성을 갖게 된다.
ArrayList의 경우 연속성을 유지하기 위해 메모리 상에서 순차적으로 데이터를 저장하는 방식을 사용하였지만,
Linked List에는 메모리 상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유롭습니다.
📝 정리하기
일반적으로는 대부분의 상황에서 ArrayList를 사용하는 것이 성능 면에서 더 유리하지만
특정 상황(데이터 추가/삭제가 많은 경우 등)에서 Linked List가 더 적합하다.
