한국어
메뉴

배열과 연결 리스트의 차이: 읽기·삽입과 삭제·메모리 배치·캐시·시간 복잡도 비교

배열은 같은 타입의 요소를 메모리에 빈틈없이 연속해서 늘어놓고, 요소 번호(인덱스)로 위치를 계산해 어느 요소든 일정한 시간에 읽고 쓸 수 있는 자료 구조입니다. 연결 리스트는 각 요소가 값과 다음 요소의 위치를 가리키는 포인터를 가지고, 그것을 따라가며 이어지는 자료 구조로, 요소를 메모리의 떨어진 곳에 둘 수 있습니다. 배열은 읽기가 빠른 대신, 중간에 삽입하거나 삭제할 때는 뒤의 요소를 옮겨야 합니다. 연결 리스트는 위치를 알고 있으면 포인터를 바꾸는 것만으로 삽입과 삭제를 할 수 있는 대신, i번째 요소를 읽으려면 처음부터 차례로 따라가야 합니다. 번호로 읽는 일이 많으면 배열, 정해진 위치에서의 삽입과 삭제가 많으면 연결 리스트라는 것이 기본적인 선택 기준입니다.

비교 항목배열연결 리스트
메모리상의 배치요소가 연속된 영역에 빈틈없이 늘어선다요소는 흩어진 곳에 놓이고 포인터로 이어진다
i번째 요소 읽기O(1). 시작 주소 + i × 요소 크기로 위치를 계산할 수 있다O(n). 처음부터 포인터를 i번 따라간다
값 탐색정렬되어 있지 않으면 O(n)의 선형 탐색. 정렬되어 있으면 이진 탐색으로 O(log n)정렬되어 있어도 O(n). 중간 요소로 한 번에 이동할 수 없으므로 이진 탐색을 쓸 수 없다
중간 삽입·삭제O(n). 뒤의 요소를 하나씩 옮긴다삽입할 위치(바로 앞 요소)를 알고 있으면 O(1). 포인터를 바꾸기만 하면 된다
끝에 추가빈 공간이 있으면 O(1). 가변 길이 배열에서 용량을 2배씩 늘리는 방식은 가끔 전체를 복사하지만, 평균하면 O(1)(분할 상환)끝 요소를 가리키는 포인터를 가지고 있으면 O(1)
크기 변경고정 길이 배열은 만들 때 크기를 정한다. 늘리려면 새 영역을 확보하고 복사한다요소마다 영역을 확보하므로 필요한 만큼만 늘릴 수 있다
사용하는 메모리요소의 몫만으로 충분하다(가변 길이 배열은 예비 용량을 가진다)요소마다 포인터만큼 추가로 든다(이중 연결 리스트라면 2개분)
캐시 효율좋다. 연속해서 늘어서 있으므로 차례로 읽으면 캐시와 프리페치가 잘 작동한다나쁘다. 요소가 흩어지기 쉬워, 같은 O(n) 순회라도 배열보다 크게 느려질 수 있다
주요 용도인덱스로 읽고 쓰는 표, 행렬과 이미지, 정렬이나 이진 탐색의 대상, 스택과 큐의 구현삽입과 삭제가 잦은 열, 해시 테이블의 체이닝, 빈 영역 관리

수치는 대략적인 자릿수 기준이며, 공정 세대와 제품에 따라 달라져요.

상황별 선택 기준

배열
요소를 번호로 읽고 쓰거나 처음부터 차례로 읽는 일이 많을 때 적합합니다. 캐시가 잘 작동하므로 오늘날의 컴퓨터에서는 많은 경우 배열(가변 길이 배열 포함)이 더 빠릅니다.
연결 리스트
중간 삽입과 삭제가 많고 그 위치를 이미 포인터로 가지고 있을 때 적합합니다. 요소를 옮기지 않고 연결을 바꿀 수 있으므로, 요소의 주소가 바뀌면 곤란할 때도 씁니다.

자주 묻는 질문

시간 복잡도로는 연결 리스트의 삽입이 O(1)인데, 실제로는 배열이 더 빠른 경우가 있는 이유는 무엇인가요?

이유는 두 가지입니다. 하나는 삽입할 위치를 처음부터 찾는다면 그 탐색에 O(n)이 걸려, 삽입이 O(1)이라도 전체로는 배열과 같은 O(n)이 된다는 점입니다. 다른 하나는 배열의 요소를 옮기는 처리는 연속된 메모리의 복사여서 캐시가 잘 작동해 매우 빠른 반면, 연결 리스트를 따라가는 처리는 요소마다 떨어진 주소를 읽으므로 캐시에 적중하기 어렵다는 점입니다. 시간 복잡도는 데이터가 많아질 때의 증가 방식을 나타내는 것이므로, 실제 속도는 측정해서 확인합니다.

단일 연결 리스트와 이중 연결 리스트는 어떻게 다른가요?

단일 연결 리스트는 각 요소가 다음 요소로의 포인터만 가지므로, 앞에서 뒤로만 따라갈 수 있습니다. 이중 연결 리스트는 이전 요소로의 포인터도 가지므로 뒤에서 앞으로도 따라갈 수 있고, 어떤 요소로의 포인터만 있으면 그 요소를 O(1)로 삭제할 수 있습니다. 그 대신 요소마다 포인터가 1개 늘고, 바꿔야 할 포인터도 늘어납니다.

가변 길이 배열(동적 배열)이란 무엇인가요?

요소가 늘어 용량이 부족해지면 더 큰 영역을 확보해 전체를 복사함으로써 크기를 바꿀 수 있게 한 배열입니다. 용량을 2배씩 늘리면 복사의 총수가 요소 수의 약 1배로 끝나므로, 끝에 추가하는 것은 평균하면 O(1)이 됩니다. 번호로 읽는 것은 보통 배열과 마찬가지로 O(1)입니다.

이해도 확인

배열과 비교했을 때 연결 리스트(각 원소가 다음 원소의 위치를 가리키는 포인터를 가진 리스트)의 특징으로 올바른 것은?

  1. A삽입할 위치 바로 앞의 원소를 알고 있으면 다른 원소를 옮기지 않고 포인터를 바꿔 다는 것만으로 삽입할 수 있지만, i번째 원소를 읽으려면 앞에서부터 차례로 따라가야 한다
  2. Bi번째 원소의 위치를 계산으로 구할 수 있으므로, 어느 원소든 일정한 시간 O(1)로 읽을 수 있다
  3. C원소가 메모리 위에 빈틈없이 연속해서 늘어서므로, 차례로 읽을 때 캐시나 프리페치가 잘 듣는다
정답과 해설 보기

정답: A. 삽입할 위치 바로 앞의 원소를 알고 있으면 다른 원소를 옮기지 않고 포인터를 바꿔 다는 것만으로 삽입할 수 있지만, i번째 원소를 읽으려면 앞에서부터 차례로 따라가야 한다

연결 리스트에서는 삽입이나 삭제할 위치를 알고 있으면 앞뒤의 포인터를 바꿔 쓰기만 하면 되므로 O(1)로 끝납니다. 한편 i번째 원소를 읽으려면 맨 앞에서부터 i번 포인터를 따라가야 하므로 O(n)이 걸립니다. 배열은 시작 주소와 원소의 크기로 i번째 주소를 계산할 수 있으므로 O(1)로 읽을 수 있지만, 중간에 삽입하려면 뒤쪽 원소를 밀어내는 O(n)의 수고가 듭니다. 또한 배열은 원소가 연속해서 늘어서므로 캐시나 프리페치가 잘 듣고, 메모리 위에 흩어지기 쉬운 연결 리스트는 같은 O(n)의 순회라도 훨씬 느려지는 경우가 있습니다.

가변 길이 배열에서, 용량이 가득 찼을 때 원소를 추가하면 2배 용량의 영역을 새로 확보하여 모든 원소를 복사한다. 용량 1인 빈 배열에 원소를 하나씩 1,000개 추가했을 때, 복사되는 원소의 총수는?

  1. A10
  2. B1,023
  3. C499,500
정답과 해설 보기

정답: B. 1,023

용량은 1, 2, 4, …, 512로 가득 찰 때마다 2배가 되고, 그때마다 그 시점의 원소를 복사하므로 복사의 총수는 1 + 2 + 4 + … + 512 = 1,023입니다. 1,000개의 추가에 대해 복사는 원소 수의 약 1배이므로 추가 1회당 수고는 평균하면 일정, 즉 분할 상환 O(1)이 됩니다. 용량을 1씩만 늘리면 복사는 1 + 2 + … + 999 = 499,500이 되어 O(n²)입니다. 10은 영역을 다시 확보한 횟수이며, 복사되는 원소의 수가 아닙니다.

해시 테이블의 충돌을 처리하는 방법으로 체이닝(같은 위치의 원소를 연결 리스트로 잇는다)과 개방 주소법(표 안의 비어 있는 다른 위치를 찾는다)을 비교한 설명으로 올바른 것은? 적재율은 저장한 원소 수를 표의 크기로 나눈 값으로 한다.

  1. A체이닝에서는 적재율이 1을 넘어도 저장할 수 있지만, 개방 주소법에서는 표의 크기를 넘어 저장할 수 없고, 적재율이 1에 가까워지면 탐색 횟수가 급격히 늘어난다
  2. B개방 주소법에서는 충돌이 일어나지 않으므로, 적재율과 관계없이 탐색은 1회로 끝난다
  3. C체이닝에서는 적재율이 아무리 높아져도 탐색의 수고는 변하지 않는다
정답과 해설 보기

정답: A. 체이닝에서는 적재율이 1을 넘어도 저장할 수 있지만, 개방 주소법에서는 표의 크기를 넘어 저장할 수 없고, 적재율이 1에 가까워지면 탐색 횟수가 급격히 늘어난다

체이닝은 같은 위치의 원소를 리스트로 이으므로 원소 수가 표의 크기를 넘어도 저장할 수 있지만, 리스트의 평균 길이는 적재율에 비례하여 늘어나고 탐색의 수고도 늘어납니다. 개방 주소법은 표 안에만 저장하므로 원소 수는 표의 크기까지이며, 적재율이 1에 가까워지면 빈자리를 찾는 횟수가 급격히 늘어납니다. 어느 방법이든 적재율이 정해 둔 값(예를 들어 0.5~0.75 정도)을 넘으면 표를 키워서 모든 원소를 다시 넣는(재해싱) 것이 보통입니다. 개방 주소법에서도 충돌은 일어나며, 빈 위치를 찾는 것으로 대처하고 있습니다.

  1. 원소 수가 많고 적재율을 0.5 정도로 유지한 해시 테이블에서, 선형 탐사의 개방 주소법이 체이닝(연결 리스트로 잇는 방법)보다 빨라지기 쉬운 이유로 가장 적절한 것은?
  2. 배열 가운데의 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 이진 탐색을 사용하기 위한 전제 조건으로 올바른 것은?

자료 구조와 알고리즘 문제 풀기

주요 용어 설명

배열(Array)
같은 형의 값을 나란히 기억하고, 인덱스(첨자)로 개별 요소를 지정하는 데이터 구조. 메모리상에 연속으로 놓이므로 인덱스로부터 위치를 계산하여 어느 요소든 일정한 시간에 읽고 쓸 수 있다. 인덱스가 0부터 시작하는 언어와 1부터 시작하는 작성법이 있다.
연결 리스트(Linked List)
각 원소가 값과 다음 원소의 위치를 가리키는 포인터를 가지며, 그것을 따라가며 이어지는 자료 구조. 위치를 알고 있으면 삽입이나 삭제는 포인터를 바꿔 다는 것으로 O(1)이지만, i번째 원소를 읽으려면 앞에서부터 따라가는 O(n)이 필요하다. 원소가 메모리 위에 흩어지기 쉬워 배열보다 캐시가 잘 듣지 않는다.
포인터(Pointer)
변수나 배열의 요소, 함수 등이 놓여 있는 메모리의 주소를 값으로 갖는 변수. C 언어에서는 int *p처럼 선언하고, &x로 x의 주소를 꺼내며, *p로 p가 가리키는 곳의 값을 읽고 쓴다. 포인터에 정수를 더하면 가리키는 형의 크기를 단위로 하여 나아간다. 배열의 이름은 대부분의 식에서 첫 요소에 대한 포인터로 변환되며, a[i]는 *(a + i)와 같은 의미가 된다. 아무 곳도 가리키지 않음을 나타내는 값을 NULL 포인터라고 한다.
시간 복잡도(Time Complexity)
알고리즘에 필요한 수고(시간 복잡도)나 기억 영역(공간 복잡도)이 데이터의 수 n에 대해 어떻게 늘어나는지를 나타낸 것. O(n)이나 O(n log n), O(n²) 같은 점근 표기법(빅오 표기법)으로, 계수나 낮은 차수의 항을 생략하여 쓴다.
이진 탐색(Binary Search)
정렬된 데이터에서 가운데 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 탐색 방법. n개의 데이터에서 최대 ⌊log₂ n⌋ + 1회의 비교로 찾을 수 있으며, 시간 복잡도는 O(log n). 데이터가 정렬되어 있는 것이 전제가 된다.
해시 테이블(Hash Table)
키로부터 해시 함수로 저장할 위치를 계산하여, 평균 O(1)로 탐색·삽입·삭제를 할 수 있는 자료 구조. 서로 다른 키가 같은 위치가 되는 충돌을 체이닝이나 개방 주소법으로 처리한다. 해시 표라고도 한다.
공간적 지역성(Spatial Locality)
어떤 주소에 접근하면 그 근처 주소에도 곧 접근하기 쉬운 성질. 배열을 순서대로 읽는 처리가 예이며, 캐시 라인 단위로 묶어 읽어 들이는 이유가 된다.

관련 비교