배열(Array)과 연결 리스트(Linked List) 차이
배열(Array)과 연결 리스트(Linked List)는 여러 데이터를 순서대로 관리하는 대표적인 선형 자료구조입니다. 겉보기에는 비슷하지만 데이터를 메모리에 저장하는 방식이 달라 접근, 탐색, 삽입, 삭제 성능에서 차이가 납니다.
배열 (Array)
배열은 입력된 데이터가 메모리의 연속된 공간에 저장되는 자료구조입니다. 각 데이터에는 순서를 나타내는 인덱스(index)가 있으며, 인덱스를 이용하면 원하는 요소에 바로 접근할 수 있습니다.
- 데이터가 메모리 공간에 연속적으로 저장됩니다.
- 인덱스를 통한 임의 접근이 빨라 시간 복잡도는 O(1)입니다.
- 일반적인 배열은 선언할 때 크기를 정하며, 이후 크기를 변경하기 어렵습니다.
- 중간에 데이터를 삽입하거나 삭제하면 뒤의 요소들을 이동해야 하므로 O(n)이 걸립니다.
- 연속된 메모리를 사용하므로 캐시 효율이 좋은 편입니다.
JavaScript의
Array처럼 크기가 자동으로 늘어나는 자료형은 일반적인 고정 길이 배열과 다르게 동적 배열로 구현될 수 있습니다.
연결 리스트 (Linked List)
연결 리스트는 여러 개의 노드(node)가 다음 노드를 가리키는 방식으로 순차적으로 연결된 자료구조입니다. 각 노드는 데이터와 다른 노드를 가리키는 링크를 가지며, 첫 번째 노드를 head, 마지막 노드를 tail이라고 합니다.
- 노드들이 메모리의 연속된 공간에 저장될 필요가 없습니다.
- 필요한 만큼 노드를 추가하거나 제거할 수 있어 크기가 동적입니다.
- 삽입하거나 삭제할 위치의 노드를 이미 알고 있다면 링크만 변경하면 되므로 O(1)이 걸립니다.
- 원하는 요소에 접근하려면 head부터 노드를 따라가야 하므로 접근과 탐색에 O(n)이 걸립니다.
- 각 노드가 링크 정보를 추가로 저장하므로 배열보다 더 많은 메모리를 사용할 수 있습니다.
연결 리스트는 구조에 따라 다음과 같이 나눌 수 있습니다.
- 단일 연결 리스트: 각 노드가 다음 노드만 가리킵니다.
- 이중 연결 리스트: 각 노드가 이전 노드와 다음 노드를 모두 가리킵니다.
- 원형 연결 리스트: 마지막 노드가 첫 번째 노드를 가리킵니다.
연결 리스트의 삽입과 삭제가 항상 O(1)인 것은 아닙니다. 대상 위치를 먼저 찾아야 한다면 탐색에 O(n)이 필요하므로 전체 연산도 O(n)이 됩니다.
배열과 연결 리스트의 차이점
| 구분 | 배열 | 연결 리스트 |
|---|---|---|
| 메모리 배치 | 연속된 공간 | 떨어진 공간의 노드를 링크로 연결 |
| 크기 | 일반적으로 고정 | 동적으로 변경 가능 |
| 데이터 접근 | 인덱스로 바로 접근, O(1) | head부터 순차 접근, O(n) |
| 데이터 탐색 | 정렬되지 않았다면 O(n) | 순차 탐색, O(n) |
| 중간 삽입·삭제 | 요소 이동이 필요해 O(n) | 위치를 알고 있다면 O(1) |
| 추가 메모리 | 상대적으로 적음 | 링크 저장 공간이 필요함 |
배열은 특정 위치의 데이터를 자주 조회할 때 유리하고, 연결 리스트는 데이터의 개수가 자주 변하거나 중간 삽입·삭제가 빈번할 때 유리합니다. 다만 연결 리스트도 삽입하거나 삭제할 위치를 찾는 과정이 필요하다면 배열보다 반드시 빠르다고 할 수는 없습니다.
한 줄 요약
배열은 연속된 메모리와 인덱스를 이용해 빠르게 접근하는 자료구조이고, 연결 리스트는 노드를 링크로 연결해 크기를 유연하게 바꾸고 삽입·삭제하기 좋은 자료구조입니다.