[자료구조/C언어] 배열(Array)과 연결 리스트(Linked List) 차이점 및 장단점 완전 정리 (시험 단골 주제)

자료구조 과목이나 기술 면접, 정보처리기사 시험에서 "선형 자료구조" 관련 서술형 문제 1순위로 출제되는 주제가 있습니다. 바로 배열(Array)과 연결 리스트(Linked List)의 차이점입니다.

두 자료구조 모두 여러 개의 데이터를 순서대로 저장하지만, 메모리에 할당되는 방식이 결정적으로 다릅니다. 개념부터 장단점, 시간 복잡도, C언어 코드 구조까지 한눈에 보기 쉽게 정리해 드립니다.

1. 메모리 구조의 결정적 차이

배열과 연결 리스트를 구분 짓는 핵심은 "데이터가 메모리에 연속해서 붙어 있느냐, 떨어져 있느냐"입니다.

2. 배열 (Array) 이란?

배열(Array)은 동일한 타입의 데이터들을 메모리의 연속된 공간에 순서대로 저장하는 고정 크기 자료구조입니다.

• 특징:
  • 생성할 때 크기를 미리 지정해야 합니다. (정적 할당)
  • 각 데이터는 인덱스(Index)를 가지며, arr[0], arr[1]처럼 인덱스를 통해 데이터에 바로 접근할 수 있습니다.
• 장점:
  • 빠른 데이터 읽기 (조회): 인덱스만 알면 $O(1)$의 시간 복잡도로 즉시 접근할 수 있습니다. (임의 접근, Random Access)
• 단점:
  • 크기 변경 불가: 선언한 후에는 크기를 늘리거나 줄일 수 없습니다.
  • 삽입/삭제의 비효율성: 중간에 데이터를 추가하거나 삭제할 경우, 뒤에 있는 데이터들을 한 칸씩 밀거나 당겨야 하므로 $O(N)$의 시간이 걸립니다.

C

 

// C언어 배열 선언 및 접근 예시
int arr[5] = {10, 20, 30, 40, 50};
printf("%d\n", arr[2]); // 30에 바로 접근 (O(1))

3. 연결 리스트 (Linked List) 란?

연결 리스트(Linked List)는 데이터와 다음 노드를 가리키는 '포인터(Pointer)'를 하나의 노드(Node)로 묶어, 메모리의 여러 위치에 흩어져 있는 노드들을 포인터로 연결한 동적 자료구조입니다.

• 특징:
  • 크기가 정해져 있지 않고, 필요할 때마다 메모리를 동적으로 할당받아 확장합니다.
  • 물리적으로는 떨어져 있지만 포인터 화살표를 통해 논리적으로 연속되어 있습니다.
• 장점:
  • 동적 크기 조절: 메모리가 허용하는 한 원하는 만큼 데이터를 계속 추가할 수 있습니다.
  • 빠른 삽입/삭제: 위치만 알고 있다면 포인터 주소값만 바꾸면 되므로 $O(1)$ 만에 데이터를 추가하거나 삭제할 수 있습니다.
• 단점:
  • 느린 데이터 읽기 (조회): 특정 위치의 데이터를 찾으려면 헤드(Head) 노드부터 포인터를 타고 순차적으로 찾아가야 하므로 $O(N)$의 시간이 걸립니다. (순차 접근, Sequential Access)
  • 추가 메모리 소모: 데이터 값 외에도 다음 주소를 저장할 포인터 변수용 메모리가 추가로 필요합니다.

C

 

// C언어 연결 리스트 노드 구조체 예시
typedef struct Node {
    int data;           // 데이터 영역
    struct Node* next;  // 다음 노드의 주소를 가리키는 포인터
} Node;

4. 한눈에 비교하는 차이점 & 시간 복잡도 (시험 핵심 요약)

시험 문제나 면접 질문에 답할 때 가장 유용한 비교표입니다!

구분	배열 (Array)	연결 리스트 (Linked List)
메모리 할당	연속적 (컴파일 시점 또는 정적 할당)	불연속적 (실행 시점 동적 할당)
크기	고정적 (Change 불가)	가변적 (자유롭게 확장/축소)
조회 (Access)	$O(1)$ (인덱스로 즉시 접근)	$O(N)$ (첫 노드부터 포인터 탐색)
삽입/삭제 (Insert/Delete)	$O(N)$ (데이터 들을 shift 해야함)	$O(1)$ (포인터 연결만 변경, 위치 파악 시)
메모리 효율	데이터만 저장 (상대적으로 효율적)	데이터 + 포인터 저장 (포인터 오버헤드 발생)

5. 시험 단골 출제 유형 체크

1. Q. 데이터의 읽기(조회) 작업이 빈번하게 일어나는 시스템에 적합한 자료구조는?
2. 👉 배열(Array)입니다. 인덱스를 통한 $O(1)$ 빠른 접근이 가능하기 때문입니다.
3. Q. 데이터의 추가 및 삭제가 매우 빈번하고, 데이터의 개수를 예측하기 어려운 경우 적합한 자료구조는?
4. 👉 연결 리스트(Linked List)입니다. 크기를 동적으로 조절할 수 있고, 포인터 재연결만으로 $O(1)$ 삽입/삭제가 가능하기 때문입니다.
5. Q. 배열에서 중간에 요소를 삭제할 때 시간 복잡도가 $O(N)$인 이유는?
6. 👉 삭제된 빈자리를 채우기 위해 뒤에 있는 요소들을 한 칸씩 앞으로 이동(Shift)시키는 작업이 필요하기 때문입니다.