배열과 연결 리스트
배열과 연결 리스트 (Array vs Linked List)
배열(Array)과 연결 리스트(Linked List)는 데이터를 순차적으로 저장하고 관리하는 가장 기본적인 선형 자료구조입니다. 두 자료구조의 가장 핵심적인 차이는 메모리상에 데이터를 저장하는 방식에 있으며, 이로 인해 각기 다른 장단점과 사용 사례를 가집니다.
📦 배열 (Array)
- 개념 (Concept) : 동일한 타입의 데이터 여러 개를 연속된 메모리 공간에 저장하는 자료구조입니다.
- 메모리 구조
> * 데이터의 논리적 순서와 물리적 순서가 일치합니다. > * 인덱스(index)를 통해 원소의 메모리 주소를 바로 계산할 수 있어, 특정 위치의 데이터에 즉시 접근이 가능합니다. (`address(arr[i]) = address(arr[0]) + i * sizeof(type)`)
- 장점
> * 빠른 접근 속도 : 인덱스를 통한 임의 접근(Random Access)이 O(1)으로 매우 빠릅니다.
- 단점
> * 크기 고정 : 생성 시 크기를 정해야 하며, 변경이 어렵습니다. (정적 배열의 경우) > * 느린 삽입/삭제 : 중간에 데이터를 삽입하거나 삭제할 경우, 해당 지점 이후의 모든 원소를 이동시켜야 하므로 O(n)의 시간이 소요됩니다.
🔗 연결 리스트 (Linked List)
- 개념 (Concept) : 여러 개의 노드(Node)가 포인터(pointer)로 연결되어 순서를 유지하는 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
- 메모리 구조
> * 데이터가 메모리상에 흩어져서 비연속적으로 저장됩니다. > * 각 노드가 다음 노드의 주소를 가리키는 포인터로 연결되어 논리적인 순서를 유지합니다.
- 장점
> * 동적 크기 : 크기가 정해져 있지 않아 유연하게 노드를 추가/삭제할 수 있습니다. > * 빠른 삽입/삭제 : 특정 노드를 알고 있을 때, 해당 노드의 앞/뒤 포인터만 변경하면 되므로 O(1)의 빠른 속도를 가집니다. (단, 해당 노드를 찾는 데는 O(n)이 걸릴 수 있습니다.)
- 단점
> * 느린 접근 속도 : 특정 위치의 데이터에 접근하려면 첫 노드부터 순차적으로 탐색(Sequential Access)해야 하므로 O(n)의 시간이 소요됩니다. > * 추가 공간 필요 : 데이터 외에 다음 노드를 가리키는 포인터를 위한 추가적인 메모리 공간이 필요합니다.
💡 개발자 핵심 Point
- 언제 무엇을 사용할까?
> * 배열 : 데이터의 크기가 정해져 있고, 데이터 접근(조회)이 빈번할 때 유리합니다. > * 연결 리스트 : 데이터의 추가/삭제가 빈번하고, 데이터의 크기를 예측하기 어려울 때 유리합니다.
- 이중 연결 리스트 (Doubly Linked List) : 각 노드가 이전 노드와 다음 노드를 모두 가리키는 포인터를 가집니다. 단일 연결 리스트보다 메모리를 더 사용하지만, 양방향 탐색이 가능하고 노드 삭제 시 더 편리합니다.
- 원형 연결 리스트 (Circular Linked List) : 마지막 노드가 첫 노드를 가리키는 구조로, 순환적인 작업에 유용합니다.
