1. 개념

1.1. 배열

고정 크기의 연속적인 메모리 공간에 같은 타입의 데이터가 저장된 자료구조

• 고정 크기 : 프로그램 실행 전 크기가 결정되고 배열이 메모리에 할당된 이후에 크기는 변하지 않는다.
• 연속적인 공간 : 배열의 원소를 위한 공간은 메모리에 연속적인 형태로 할당된다.
• 같은 데이터 타입 : 배열의 모든 원소는 같은 타입의 데이터다. 즉 모든 원소의 데이터 크기가 같다.

1.2. 연결 리스트

동적으로 할당된 불연속적인 메모리 공간에 데이터와 다음 노드의 포인터로 구성된 노드들이 연결된 자료구조

• 동적 할당 : 메모리 할당이 동적으로 이루어진다. 이것은 연결 리스트의 크기를 프로그램 실행 중 늘리거나 줄일 수 있다는 것을 의미한다.
• 불연속적인 공간 : 동적 할당은 힙 메모리에서 이루어지는데 순서 상관 없이 비어있는 공간에 할당된다.
• 노드 연결 : 불연속적인 상황에선 다음 데이터의 위치를 알 수 없으므로 연결 리스트는 데이터와 다음 데이터의 위치를 함께 저장하는 노드(node) 형태로 데이터를 연결한다.

2. 비교

1. 크기 : 배열은 크기는 고정 크기이다. 크기가 고정돼 있는 이유는 배열에 할당된 메모리 공간을 넘어서는 공간이 이미 사용되고 있는 공간일 수 있기 때문이다. 이것을 무시하고 실행 시간 중 배열의 크기를 늘려버리면 기존에 있던 데이터를 덮어 쓸 위험(buffer overflow)이 있다. 반대로 연결 리스트의 크기는 언제든지 변할 수 있다.
2. 할당 : 배열은 프로그램 실행 전 컴파일 시간 동안 스택 메모리에 정해진 크기만큼 할당된다. 연결 리스트는 프로그램 실행 중 필요할 때 마다 비어있는 힙 메모리에 동적으로 할당된다.
3. 메모리 사용량 : 원소의 개수가 같을 때, 배열보다 연결 리스트가 더 많은 메모리 공간을 사용한다. 배열의 각 원소는 데이터만 저장하지만 연결 리스트는 데이터 외에 다음 노드의 주소를 저장하기 위한 공간이 추가로 필요하기 때문이다.
4. 연속성 : 배열은 메모리에 연속적으로 할당된다. 연속적으로 할당된다는 것은 공간적 지역성(spatial locality)이 높다는 것을 의미하는데, 공간적 지역성이 높을수록 캐시를 효율적으로 사용할 수 있다. 캐시는 참조의 지역성(locality of reference)을 고려하여 메모리에서 데이터를 가져올 때 인접 데이터도 함께 가져온다. 배열의 경우 모든 원소가 인접해 있기 때문에 한번에 많은 원소를 캐시에 가져온다. 반면, 연결 리스트는 불연속적으로 할당되므로 공간적 지역성이 낮다. 따라서 캐시 효율성은 떨어진다.
5. 접근 : 배열은 첫 번째 원소의 메모리 주소만 알면 어느 원소든 메모리 주소를 계산하여 탐색 시간없이 임의 접근(random access)할 수 있다. 첫 번째 원소를 base value라 하고, 특정 원소까지 메모리 상에서의 거리를 offset이라 하는데, base value에 offset을 더하는 방법으로 특정 인덱스에 해당하는 원소의 메모리 주소를 계산한다. 연결 리스트는 임의 접근이 불가능하다. 메모리에 불연속적으로 저장돼 있기 때문에 특정 원소에 접근 할때는 순차 접근(sequential access)만 가능하다. 시간 복잡도로 분석해보면 배열은 임의 접근을 하므로 $O(1)$, 연결 리스트는 순차 접근을 하므로 $O(n)$의 시간 복잡도를 갖는다.
6. 삽입과 삭제 : 배열에서 특정 인덱스에 원소를 삽입하거나 삭제할 경우 순서를 유지해야 하므로 삽입, 삭제가 일어난 인덱스 이후의 모든 원소를 이동시켜야 한다. 따라서 배열의 삽입, 삭제 연산은 $O(n)$의 시간 복잡도를 갖는다. 다만, 마지막 원소 뒤에 삽입하거나 마지막 원소를 삭제한다면 이동시킬 원소가 없으므로 $O(1)$의 시간 복잡도를 갖는다. 연결 리스트의 경우 삽입, 삭제 연산 자체만 봤을 때는 노드를 만들고 인접 노드만 수정하면 되므로 $O(1)$의 시간 복잡도를 갖는 것 같지만 연산하기 전에 삽입, 삭제시킬 노드의 위치까지 순차 접근해야하기 때문에 $O(n)$의 시간 복잡도를 갖는다. 연결 리스트도 예외가 있다. 첫 번째 노드는 바로 접근할 수 있기 때문에 첫 번째 노드의 삽입, 삭제는 $O(1)$의 시간 복잡도가 된다. 만약 마지막 노드를 가리키는 포인터가 있다면 마지막 노드의 삽입, 삭제도 $O(1)$의 시간 복잡도가 된다.

3. 결론

• 배열 : 메모리 공간의 효율성이 중요하거나 접근 빈도가 높을 때 배열이 더 적합하다.
• 연결 리스트 : 할당 크기의 유연성이 중요하거나 삽입과 삭제의 빈도가 높을 때 연결 리스트가 더 적합하다.