[자료구조/C언어] 단일 연결 리스트 vs 이중 연결 리스트 차이점 완전 정리 (시험 단골 주제)

지난 포스팅에서 배열(Array)과 연결 리스트(Linked List)의 기본적인 차이에 대해 알아보았습니다. 이번에는 연결 리스트의 대표적인 두 가지 형태인 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List)를 비교해 보겠습니다.

자료구조 중간·기말고사나 정보처리기사, 손코딩 면접에서 "포인터 연결 방식"과 "양방향 탐색" 관련 단골 문제로 자주 등장하니 꼭 챙겨두시기 바랍니다!

1. 단일 연결 리스트 (Singly Linked List) 란?

단일 연결 리스트는 각 노드가 '데이터(Data)'와 '다음 노드를 가리키는 포인터(Next)' 단 하나만을 가지고 있는 가장 단순한 형태의 연결 리스트입니다.

• 특징:
  • 한쪽 방향(앞 $\rightarrow$ 뒤)으로만 이동할 수 있는 단방향 구조입니다.
  • 마지막 노드(Tail)의 next 포인터는 NULL을 가리킵니다.
• 장점:
  • 노드 구조가 단순하고 메모리를 상대적으로 적게 차지합니다.
• 단점:
  • 이전 노드로 되돌아갈 수 없습니다. (이전 노드의 위치를 알 수 없음)
  • 특정 노드를 삭제하려면 선행 노드(이전 노드)의 포인터를 알아야 하므로 헤드(Head)부터 다시 탐색해야 할 수 있습니다.

C

 

// C언어 단일 연결 리스트 노드 구조체
typedef struct Node {
    int data;           // 데이터
    struct Node* next;  // 다음 노드를 가리키는 포인터 (단방향)
} Node;

2. 이중 연결 리스트 (Doubly Linked List) 란?

이중 연결 리스트는 단일 연결 리스트의 단점을 보완하기 위해 각 노드가 '데이터(Data)', '다음 노드를 가리키는 포인터(Next)', 그리고 '이전 노드를 가리키는 포인터(Prev)' 2개의 포인터를 갖는 구조입니다.

• 특징:
  • 앞뒤 양쪽 방향(앞 $\leftrightarrow$ 뒤)으로 모두 이동할 수 있는 양방향 구조입니다.
  • 첫 번째 노드의 prev는 NULL, 마지막 노드의 next는 NULL을 가리킵니다.
• 장점:
  • 양방향 탐색이 가능하여 특정 노드를 기준으로 앞/뒤 노드에 쉽게 접근할 수 있습니다.
  • 특정 노드의 포인터만 주어졌을 때, 선행 노드의 포인터(prev)를 즉시 알 수 있어 노드 삭제 연산이 훨씬 쉽고 빠릅니다.
• 단점:
  • 포인터 변수가 2개 필요하므로 추가 메모리 공간(오버헤드)이 발생합니다.
  • 삽입/삭제 시 next와 prev 포인터를 모두 재연결해야 하므로 코드가 복잡해지고 연산량이 늘어납니다.

C

 

// C언어 이중 연결 리스트 노드 구조체
typedef struct Node {
    int data;           // 데이터
    struct Node* prev;  // 이전 노드를 가리키는 포인터
    struct Node* next;  // 다음 노드를 가리키는 포인터 (양방향)
} Node;

3. 노드 삭제 연산의 결정적 차이 (시험 단골 포인트)

시험 문제에서 C언어 코드로 가장 많이 출제되는 부분이 바로 노드 삭제 연산입니다.

① 단일 연결 리스트에서 노드 삭제

삭제하려는 노드 target이 있을 때, target 이전 노드(prev)의 next 포인터를 target->next로 바꿔줘야 합니다. 하지만 단일 연결 리스트는 이전 노드를 직접 알 수 없기 때문에 Head부터 순회하면서 prev 노드를 찾아야 하는 번거로움이 있습니다.

② 이중 연결 리스트에서 노드 삭제

삭제하려는 노드 target만 알고 있어도 target->prev를 통해 이전 노드에 즉시 접근할 수 있으므로, 별도의 순회 과정 없이 포인터 연결만 재설정해 주면 됩니다.

C

 

// 이중 연결 리스트에서 target 노드 삭제 시 포인터 재연결 핵심 코드
target->prev->next = target->next;
target->next->prev = target->prev;
free(target);

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

시험 직전 한눈에 정리하는 비교표입니다!

구분	단일 연결 리스트 (Singly)	이중 연결 리스트 (Doubly)
포인터 개수	1개 (next)	2개 (prev, next)
탐색 방향	단방향 (앞 $\rightarrow$ 뒤)	양방향 (앞 $\leftrightarrow$ 뒤)
메모리 사용량	상대적으로 적음	포인터 변수 1개 추가로 메모리 소모 더 큼
구현 난이도	비교적 단순함	포인터 재연결이 많아 상대적으로 복잡함
노드 삭제 효율	이전 노드를 찾기 위해 Head부터 탐색 필요	prev 포인터로 선행 노드 즉시 접근 가능

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

1. Q. 단일 연결 리스트와 비교했을 때 이중 연결 리스트의 가장 큰 장점은?
2. 👉 양방향 탐색이 가능하며, 특정 노드가 주어졌을 때 선행 노드(prev)의 위치를 $O(1)$ 만에 파악하여 삭제/삽입 작업을 효율적으로 수행할 수 있습니다.
3. Q. 이중 연결 리스트의 단점 2가지를 적으시오.
4. 👉 1) 포인터 변수를 2개 유지해야 하므로 메모리가 더 많이 소모됩니다. 2) 삽입/삭제 시 수정해야 할 포인터가 늘어나 알고리즘 구현이 복잡해집니다.