c언어 연결 리스트 생성 방법에 대하여 알아보기

c언어 연결 리스트 생성 방법에 대하여 알아보기

네 안녕하세요, 이번 포스팅에서는 연결 리스트를 직접 생성해서 알아보는 시간을 가져보도록 하겠습니다.

이전 포스팅에서는 연결 리스트가 무엇인지 알아보는 시간을 가졌다면,

이번 포스팅에서는 직접 사용을 할 것입니다.

그럼 지금부터 시작하도록 하겠습니다.

 

1. 자기 참조 구조체

연결 리스트를 구현하려면 자기 참조 구조체라는 것을 알아야 합니다.

자기 참조 구조체는 일반 구조체와는 다른 조금은 특별한 구조체인데,

구조체를 구성하는 멤버들 중에 같은 타입의 구조체를 가리키는 포인터가 존재하는 구조체를 말합니다.

자기 참조 구조체는 이렇게 생겼습니다.

struct NODE
{
    int data;
    struct NODE *link; // 구조체 자기 자신을 가리킬 수 있는 포인터
};

이런 식으로 생겼습니다.

여기서 link는 구조체 자기 자신의 이름인 NODE를 가리키므로, 자기 자신을 참조하는 구조체 포인터가 됩니다.

그리고 이 자기 참조 구조체는 포인터를 이용하여 다른 구조체와도 연결이 가능하므로,

연결 리스트나 트리형 자료 구조를 구현할 때 많이 씁니다.

일반적으로 항목의 개수가 불분명할 때 자기 참조 구조체를 정의를 해두고서 동적으로 메모리를 할당받은 뒤,

이들을 포인터로 연결하여 자료 구조를 구성하게 됩니다.

그래서 이 자기 참조 구조체를 이용하면 중간에 새로운 데이터를 삽입하기가 쉬워집니다.

또한, 자기 참조 구조체는 이런 식으로 쓰는 것이 일반적입니다.

typedef struct NODE
{
    int data;
    struct NODE *link;
}NODE;

이런 식으로 이름을 간략하게 만들기 위해서 typedef를 이용하여 선언하게 됩니다.

반응형

 

2. 연결 리스트 생성의 예

연결 리스트를 이번에는 직접 구성을 해볼 것입니다.

먼저 연결 리스트를 구성하기 전에 자기 참조 구조체가 하나 정의되었다고 가정을 해봅시다.

이렇게 말이죠.

typedef struct NODE
{
    int data;
    struct NODE *link;
}NODE;

이제 여기서 동적으로 메모리를 할당을 받을 건데,

일반적으로는 연결 리스트에서 필요할 때마다 동적 메모리 할당을 받습니다.

이런 식으로 말이죠.

NODE *p1;
p1 = (NODE *)malloc(sizeof(NODE));

이렇게 하게 되면 포인터 변수 p1이 malloc() 함수로 동적 할당을 받게 되었으므로,

이 동적 메모리가 NODE의 노드가 됩니다.

이제 새로 만들어진 노드에 데이터를 저장하고 링크 필드를 NULL로 설정을 합니다.

p1->data = 10;
p1->link = NULL;

이렇게 하게 되면 10이라는 데이터가 동적 메모리에 저장이 되고,

링크 필드는 NULL이 됩니다.

이 방법으로 똑같이 p2라는 포인터 변수를 만들어 할당을 받아 서로 연결을 해보도록 하겠습니다.

NODE *p2;
p2 = (NODE *)malloc(sizeof(NODE));
p2->data = 20;
p2->link = NULL;
p1->link = p2; // 2개의 노드 연결

연결을 할 때에는 NULL로 설정해뒀던 곳을 연결하고자 하는 포인터 변수로 바꿔주면 됩니다.

만일에 연결을 끊고 싶다면 포인터 변수를 쓴 곳을 NULL로 바꿔주면 됩니다.

노드를 더 만들고 싶다면 위의 과정을 반복하면 되고,

동적 메모리 할당을 이용했기 때문에 사용이 끝나면 반드시 메모리를 해제해야 합니다.

이런 식으로 말이죠.

free(p1);
free(p2);

우리는 두 개의 포인터 변수를 사용했기 때문에 2개를 반납해야 합니다.

그리고 요렇게 연결 리스트에 삽입 및 삭제하는 함수를 따로 작성해서

이 함수를 호출하여 위 과정을 수행하는게 일반적입니다.

 

여기까지 연결 리스트를 생성하는 방법에 대하여 알아보았는데요,

다음 포스팅에서는 이를 응용하는 방법을 알아보도록 하겠습니다.

긴 글 읽어주신 독자분들께 진심으로 감사드립니다~