0Pricing
C Academy · 강의

이중 연결 리스트

양방향 연결을 알아봅니다

이중 연결 리스트은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

양방향 연결

이중 연결 목록에서는 각 노드가 두 개의 포인터를 가집니다. 하나는 next 노드를 가리키고, 다른 하나는 prev(이전) 노드를 가리킵니다.

따라서 목록을 양방향으로 순회할 수 있고 삭제도 간단해집니다.

#include <stdio.h>

struct Node {
    int value;
    struct Node *prev;
    struct Node *next;
};

int main(void) {
    printf("Each node links forward and backward\n");
    return 0;
}

노드 정의하기

구조체에 next와 함께 prev 포인터를 추가합니다. 목록의 양 끝에서는 둘 다 NULL입니다.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 1; n->prev = NULL; n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

생성 도우미

앞에서와 마찬가지로 도우미 함수에서 할당을 한곳에서 처리합니다. prev와 next를 모두 NULL로 설정합니다.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v; n->prev = NULL; n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(42);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

양방향으로 노드 연결하기

두 노드를 연결할 때는 양쪽 방향을 모두 갱신해야 합니다. 첫 번째 노드의 next와 두 번째 노드의 prev를 설정합니다.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b;
    b->prev = a;
    printf("forward %d, back %d\n", a->next->value, b->prev->value);
    free(a); free(b);
    return 0;
}

앞쪽에 삽입하기

앞쪽에 추가할 때는 새 노드의 next를 기존 헤드로 설정하고, 기존 헤드의 prev를 새 노드로 설정한 다음, 헤드를 새 노드로 이동합니다.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void push(struct Node **head, int v) {
    struct Node *n = make(v);
    n->next = *head;
    if (*head) (*head)->prev = n;
    *head = n;
}

int main(void) {
    struct Node *head = NULL;
    push(&head, 2); push(&head, 1);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

앞으로 순회하기

앞으로 순회하는 방법은 단일 연결 목록과 같습니다. NULL에 도달할 때까지 next를 따라갑니다.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    for (struct Node *p = a; p; p = p->next) printf("%d ", p->value);
    printf("\n");
    free(a); free(b);
    return 0;
}

뒤로 순회하기

가장 큰 장점은 어떤 노드에서든 prev 포인터를 따라 헤드에 도달할 때까지 뒤로 순회할 수 있다는 것입니다.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next = b; b->prev = a; b->next = c; c->prev = b;
    for (struct Node *p = c; p; p = p->prev) printf("%d ", p->value);
    printf("\n");
    free(a); free(b); free(c);
    return 0;
}

더 쉬운 삭제

각 노드가 이전 노드를 알고 있으므로 이전 노드를 찾지 않고도 해당 노드를 삭제할 수 있습니다.

node->prev와 node->next를 양방향으로 연결하기만 하면 됩니다.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void del(struct Node **head, struct Node *n) {
    if (n->prev) n->prev->next = n->next; else *head = n->next;
    if (n->next) n->next->prev = n->prev;
    free(n);
}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next=b; b->prev=a; b->next=c; c->prev=b;
    struct Node *head = a;
    del(&head, b);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

양쪽 이웃 갱신하기

노드를 제거할 때는 이전 노드의 next와 다음 노드의 prev를 모두 수정해야 합니다.

각 끝에서 NULL인지 확인하여 존재하지 않는 이웃을 역참조하지 않도록 하세요.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    a->next = NULL;
    free(b);
    printf("now only %d remains\n", a->value);
    free(a);
    return 0;
}

꼬리 포인터 유지하기

많은 이중 연결 목록은 마지막 노드를 가리키는 꼬리 포인터도 저장합니다. 따라서 O(1)로 뒤에 추가할 수 있고 끝에서부터 뒤로 순회할 수 있습니다.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1), *tail = head;
    struct Node *n = make(2);
    tail->next = n; n->prev = tail; tail = n;
    printf("tail = %d\n", tail->value);
    free(head); free(n);
    return 0;
}

절충점

이중 연결 목록은 노드마다 포인터를 하나 더 사용하므로 메모리가 추가로 필요하며, 변경할 때마다 두 연결을 갱신해야 합니다.

그 대신 양방향 순회와, 알고 있는 노드를 O(1)에 삭제하는 기능을 얻습니다. 필요에 따라 선택하세요.

#include <stdio.h>

int main(void) {
    printf("Singly: less memory, one-way\n");
    printf("Doubly: more memory, two-way + easy delete\n");
    return 0;
}

빠른 확인

이중 연결 목록에 대한 이해도를 확인해 보세요.

복습

이중 연결 목록을 배웠습니다.

  • 각 노드는 prev와 next 포인터를 모두 가집니다.
  • 연결하려면 양쪽 방향을 모두 갱신해야 합니다.
  • 앞뒤로 순회할 수 있고, 알고 있는 노드를 O(1)에 삭제할 수 있습니다.
  • 추가 메모리와 더 많은 포인터 갱신이 비용으로 발생하지만, 꼬리 포인터를 사용하면 O(1)에 뒤에 추가할 수 있습니다.

자주 묻는 질문

“이중 연결 리스트” 강의는 무료인가요?

네 — “이중 연결 리스트” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“이중 연결 리스트”에서 뭘 배우나요?

양방향 연결을 알아봅니다 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

C Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

“이중 연결 리스트” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 단일 연결 리스트
  2. 삽입과 삭제
  3. 순회와 검색
  4. 이중 연결 리스트
← C Academy(으)로 돌아가기