[C | WEEK05] 연결리스트 구현 - 추가예정

2022년 11월 27일 20시 32분 49초에 업로드 된 글입니다.

작성자: nickhealthy

C 언어로 연결 리스트 구현

정글에서 5주차가 진행되고 RB-Tree를 구현하는 과제가 주어졌다.
그것도 C 언어를 이용해서 RB-Tree의 자료구조를 구현해야 하는데, C 언어에 대한 문법도 익숙치 않을 뿐더러 RB-Tree 자료구조 구현 자체가 쉽지 않다기에 비교적 쉬우면서도 선수지식으로 알아야 할 '연결 리스트'와 '이진 검색 트리'를 C 언어를 구현해 봄으로써 C 언어를 익히고, RB-Tree를 구현하고자 한다.

Operator

1. 연결리스트 구조체 만들고 사용하기

연결 리스트에서 노드를 추가하는 규칙

노드에 메모리 할당
next 멤버에 다음 노드의 메모리 주소 저장
data 멤버에 데이터 저장
마지막 노드라면 next 멤버에 NULL 저장

아래 이미지는 사용자가 정의한 구조체를 이용해 연결리스트를 구현한 것을 의미한다.
각각의 박스는 각각의 노드들을(구조체) 의미하며, 각 노드들에는 next, data의 멤버변수가 들어있다.
마지막 노드의 next 멤버 변수는 NULL를 가리키고 있음(연결리스트의 마지막을 알리며 종료)

구현 코드

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

/* 1. 연결리스트 구조체 만들고 사용하기*/

typedef struct NODE // 연결 리스트의 노드 구조체
{
    struct Node *next; // 다음 노드의 메모리 주소를 저장할 포인터
    int data;          // 데이터를 저장할 멤버
} Node;

/* 연결리스트 구현 */

int main()
{
    Node *head = malloc(sizeof(Node)); // head 노드는 연결리스트의 기준점만 잡기 때문에, 데이터를 추가하지 않음

    Node *node1 = malloc(sizeof(Node)); // node1 구조체 변수에 Node 구조체 자료형 사이즈 추가
    head->next = node1;                 // head 구조체 변수가 가리키는 *next 멤버변수에 node1 포인터 주소값을 저장
    node1->data = 10;                   // node1 구조체 변수가 가리키는 data 멤버변수에 10 정수값을 저장

    Node *node2 = malloc(sizeof(Node));
    node1->next = node2;
    node2->data = 20;

    node2->next = NULL; // node2 구조체 변수가 가리키는 next 포인터 변수에는 NULL 추가(마지막 위치)

    // Node 구조체 자료형을 가지는 curr 포인터 변수에, head 변수가 가지고 있는 next주소 값 대입
    // 즉, 구조체 node1 변수의 멤버변수 next의 주소값을 가짐
    // 순회용 포인터 head->next 값 저장
    Node *curr = head->next;

    while (curr != NULL) // NULL 위치가 나올 때까지 반복
    {
        printf("%d\n", curr->data); // node1위치부터 시작해서 data를 출력
        // curr 포인터 변수는 현재 구조체 node1를 가지고 있고, while 구문이 실행될 때마다 nodeN번->next 를 수행하라는 뜻
        // 즉, 다음 턴에는 node1->next 인 node2를 가르칠 것이고, 다음 while 구문 수행 시 node2->next인 NULL 값을 가르킬 것임
        curr = curr->next;
    }

    free(node2);
    free(node1);
    free(head);
}

/* (정리)연결 리스트에서 노드를 추가하는 규칙 */
/*
    1. 노드에 메모리 할당
    2. next 멤버에 다음 노드의 메모리 주소 저장
    3. data 멤버에 데이터 저장
    4. 마지막 노드라면 next 멤버에 NULL 저장
*/

2. 노드 추가 함수 만들기

위의 이미지와 코드는 연결리스트의 노드를 개별적으로 생성해서 노드를 연결해주려니까 비효율적이다.

지금 구현해 볼 함수는 노드를 새로 만들어서 연결리스트에 자동으로 이어붙일 수 있도록 하는 함수이다.
새로운 노드를 만드는 함수는 다음과 같다.

addFirst 함수

해당 함수는 새로운 노드를 만들고 연결리스트에 새롭게 만든 노드를 추가 시켜줄 때마다 head(첫 번째 노드) 뒤에 새로운 노드가 연결되고, 새로운 노드는 다음 노드를 바라볼 수 있도록 구현된 함수이다.

아래의 이미지는 이전에 생성했던 head, node1, node2를 가지고 있는 연결리스트임

구현 코드

/* 2. 노드 추가 함수 만들기(연결리스트의 첫 부분을 계속 추가함) */
void addFirst(NODE *target, int data) // 기준 노드의 포인터, 새 노드의 data를 매개변수로 받음
{
    NODE *newNode = malloc(sizeof(NODE)); // 새로운 newNode 포인터 변수에 메모리 할당
    // 새 노드는 기준 노드의 포인터를 받도록 만듬
    // 즉, 새 노드의 다음 노드에(newNode->next) 기준 노드의 다음 노드를 할당함(target->next)
    newNode->next = target->next;
    newNode->data = data; // 새 노드에 매개변수로 받은 data 대입

    target->next = newNode; // 기준 노드에 방금 만든 새 노드의 위치를 대입
}

함수 코드 설명

newNode->next = target->next;
해당 부분은 새로운 노드가 기준 노드가(target) 바라보던 next 값을 추가시켜 다음 노드를 바라볼 수 있도록 해주는 부분

newNode->data = data; 새로운 노드에 data를 대입
target->next = newNode; 기준 노드는 새로운 노드를 바라볼 수 있도록(연결할 수 있도록) 해주는 부분

전체 구현 코드

addFirst 함수를 구현해 새로운 노드를 만들어 삽입하고, 메모리를 할당해제 하는 부분까지의 코드는 다음과 같다.

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

/* 1. 연결리스트 구조체 만들고 사용하기*/

typedef struct NODE // 연결 리스트의 노드 구조체
{
    struct NODE *next; // 다음 노드의 메모리 주소를 저장할 포인터
    int data;          // 데이터를 저장할 멤버
} NODE;

/* 2. 노드 추가 함수 만들기(연결리스트의 첫 부분을 계속 추가함) */
void addFirst(NODE *target, int data) // 기준 노드의 포인터, 새 노드의 data를 매개변수로 받음
{
    NODE *newNode = malloc(sizeof(NODE)); // 새로운 newNode 포인터 변수에 메모리 할당
    // 새 노드는 기준 노드의 포인터를 받도록 만듬
    // 즉, 새 노드의 다음 노드에(newNode->next) 기준 노드의 다음 노드를 할당함(target->next)
    newNode->next = target->next;
    newNode->data = data; // 새 노드에 매개변수로 받은 data 대입

    target->next = newNode; // 기준 노드에 방금 만든 새 노드의 위치를 대입
}

/* 연결리스트 구현 */

int main()
{
    NODE *head = malloc(sizeof(NODE)); // head 노드는 연결리스트의 기준점만 잡기 때문에, 데이터를 추가하지 않음
    head->next = NULL;                 // 초기 연결리스트는 비어있기 때문에 head->next는 NULL를 가리키게 함
    addFirst(head, 10);                // newNode 10를 만들고, head는 10를 가리키게 함, newNode(10)은 NULL를 가리키게 함
    addFirst(head, 20);                // newNode 20를 만들고, head는 20를 가리키게 함, newNode(20)은 newNode(10)를 가리키게 함
    addFirst(head, 30);                // newNode 30를 만들고, head는 30를 가리키게 함, newNode(30)은 newNode(20)를 가리키게 함
    // 위의 총 순서는 다음과 같음.
    // head -> 30 -> 20 -> 10 -> NULL

    // NODE 구조체 자료형을 가지는 curr 포인터 변수에, head 변수가 가지고 있는 next주소 값 대입
    // 즉, 구조체 node1 변수의 멤버변수 next의 주소값을 가짐
    // 순회용 포인터 head->next 값 저장
    NODE *curr = head->next;

    // 값 출력용 while 문
    while (curr != NULL) // NULL 위치가 나올 때까지 반복
    {
        printf("%d\n", curr->data); // node1위치부터 시작해서 data를 출력
        // curr 포인터 변수는 현재 구조체 node1를 가지고 있고, while 구문이 실행될 때마다 nodeN번->next 를 수행하라는 뜻
        // 즉, 다음 턴에는 node1->next 인 node2를 가르칠 것이고, 다음 while 구문 수행 시 node2->next인 NULL 값을 가르킬 것임
        curr = curr->next;
    }

    // 메모리 할당 해제 while 문
    curr = head->next; // 현재 curr의 값은 30임
    while (curr != NULL)
    {
        // 제일 처음 while문 반복 시, curr은 현재 30이니까 curr->next가 가리키는 값은 20임
        // tmpNext로 임시 포인터 변수를 지정하는 이유는 curr 포인터 변수를 할당해제하게 되면, 다음 위치 값(next)을 알 수가 없으므로 임시 변수에 저장 후, curr = tmpNext로 curr를 업데이트 해준다.
        NODE *tmpNext = curr->next;
        free(curr);     // 현재 노드의 메모리 할당 해제
        curr = tmpNext; // curr->next 값인 20값을 할당
    }
    free(head); // head 메모리 해제
}

/* (정리)연결 리스트에서 노드를 추가하는 규칙(addFirst) */
/*
    1. addFirst 함수에 newNode에 대한 메모리 할당
    2. newNode는 기존 노드가 바라보던 다음 노드를 바라볼 수 있도록 함
    3. 기존 노드는 newNode를 바라볼 수 있도록 함
*/

/* (정리)노드를 메모리에서 할당해제 */
/*
    1. 연결리스트는 head에서부터 순차적으로 진행되므로, 다음 노드의 값을 임시변수에 저장
    2. 임시변수에 저장하는 이유는 현재 노드를 먼저 메모리 할당 해제할 시, 다음 노드를 찾을 수가 없음
    3. 임시변수에 다음 노드의 값이 저장되어 있는데, 이것을 다시 curr 노드로 업데이트 함
    4. 1~3번을 NULL이 나올 때까지 반복 진행
*/

3. 노드 삭제 함수 구현

removeFirst 함수

해당 함수는 head 앞의 노드부터 차례대로 연결리스트에서 지우고, 이전에 연결되어있었던 이전 노드와 다음 노드를 이어주는 함수이다.

처음 노드의 상태는 아래의 이미지와 같다.
NODE *removeNode = target->next; 은 removeNode 포인터 변수는 삭제될 노드의 대상이다.
여기서 왜 기존 노드의 다음값이냐면(target->next) 아래의 그림처럼 target->next를 지정해주어야 삭제대상인 removeNode를 가리킬 수 있다. 즉, target 자체를 removeNode 포인터 변수에 할당 시 target 자체가 지워지게 됨

구현코드

void removeFirst(NODE *target)
{
    NODE *removeNode = target->next;
    target->next = removeNode->next;

    free(removeNode);
}

다음 그림은 삭제될 대상을 이전 단계에서 removeNode에 저장 후, 삭제될 노드의 next 값을 기존 노드에 저장 시켜주는 역할을 하게 된다.

코드로써는 target->next = removeNode->next; 로 표현할 수 있다. 왜냐하면 removeNode의 값은 삭제될 노드의 대상이고, removeNode의 next 포인터는 그 다음 노드를 가리키고 있기 때문이다.

마지막으로 노드를 free함수로 할당해제하며 노드를 메모리에서 완전히 삭제시킨다.
코드는 free(removeNode); 이다.

위의 과정을 진행하여 아래의 그림처럼 연결리스트가 구성되었다.

연결리스트의 전체 코드

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

/* 1. 연결리스트 구조체 만들고 사용하기*/

typedef struct NODE // 연결 리스트의 노드 구조체
{
    struct NODE *next; // 다음 노드의 메모리 주소를 저장할 포인터
    int data;          // 데이터를 저장할 멤버
} NODE;

/* 2. 노드 추가 함수 만들기(연결리스트의 첫 부분을 계속 추가함) */
void addFirst(NODE *target, int data) // 기준 노드의 포인터, 새 노드의 data를 매개변수로 받음
{
    NODE *newNode = malloc(sizeof(NODE)); // 새로운 newNode 포인터 변수에 메모리 할당
    // 새 노드는 기준 노드의 포인터를 받도록 만듬
    // 즉, 새 노드의 다음 노드에(newNode->next) 기준 노드의 다음 노드를 할당함(target->next)
    newNode->next = target->next;
    newNode->data = data; // 새 노드에 매개변수로 받은 data 대입

    target->next = newNode; // 기준 노드에 방금 만든 새 노드의 위치를 대입
}

void removeFirst(NODE *target)
{
    NODE *removeNode = target->next;
    target->next = removeNode->next;

    free(removeNode);
}

/* 연결리스트 구현 */

int main()
{
    NODE *head = malloc(sizeof(NODE)); // head 노드는 연결리스트의 기준점만 잡기 때문에, 데이터를 추가하지 않음
    head->next = NULL;                 // 초기 연결리스트는 비어있기 때문에 head->next는 NULL를 가리키게 함
    addFirst(head, 10);                // newNode 10를 만들고, head는 10를 가리키게 함, newNode(10)은 NULL를 가리키게 함
    addFirst(head, 20);                // newNode 20를 만들고, head는 20를 가리키게 함, newNode(20)은 newNode(10)를 가리키게 함
    addFirst(head, 30);                // newNode 30를 만들고, head는 30를 가리키게 함, newNode(30)은 newNode(20)를 가리키게 함
    // 위의 총 순서는 다음과 같음.
    // head -> 30 -> 20 -> 10 -> NULL

    removeFirst(head);

    // NODE 구조체 자료형을 가지는 curr 포인터 변수에, head 변수가 가지고 있는 next주소 값 대입
    // 즉, 구조체 node1 변수의 멤버변수 next의 주소값을 가짐
    // 순회용 포인터 head->next 값 저장
    NODE *curr = head->next;

    // 값 출력용 while 문
    while (curr != NULL) // NULL 위치가 나올 때까지 반복
    {
        printf("%d\n", curr->data); // node1위치부터 시작해서 data를 출력
        // curr 포인터 변수는 현재 구조체 node1를 가지고 있고, while 구문이 실행될 때마다 nodeN번->next 를 수행하라는 뜻
        // 즉, 다음 턴에는 node1->next 인 node2를 가르칠 것이고, 다음 while 구문 수행 시 node2->next인 NULL 값을 가르킬 것임
        curr = curr->next;
    }

    // 메모리 할당 해제 while 문
    curr = head->next; // 현재 curr의 값은 30임
    while (curr != NULL)
    {
        // 제일 처음 while문 반복 시, curr은 현재 30이니까 curr->next가 가리키는 값은 20임
        // tmpNext로 임시 포인터 변수를 지정하는 이유는 curr 포인터 변수를 할당해제하게 되면, 다음 위치 값(next)을 알 수가 없으므로 임시 변수에 저장 후, curr = tmpNext로 curr를 업데이트 해준다.
        NODE *tmpNext = curr->next;
        free(curr);     // 현재 노드의 메모리 할당 해제
        curr = tmpNext; // curr->next 값인 20값을 할당
    }
    free(head);
}

Ref

코딩도장 - 연결 리스트 구조체 만들고 사용하기

코딩도장 - 노드 추가 함수 만들기

코딩도장 - 노드 삭제 함수 만들기

다음글이 없습니다.

이전글이 없습니다.

C 언어로 연결 리스트 구현

Operator

1. 연결리스트 구조체 만들고 사용하기

연결 리스트에서 노드를 추가하는 규칙

구현 코드

2. 노드 추가 함수 만들기

addFirst 함수

구현 코드

함수 코드 설명

전체 구현 코드

3. 노드 삭제 함수 구현

removeFirst 함수

구현코드

연결리스트의 전체 코드

Ref

티스토리툴바