[C언어] 연결 리스트(Linked list) 구현

[C언어] 연결 리스트(Linked list) 구현

연결리스트는 복잡한 트리 구조를 구현하기 위해 사용되기 때문에 꼭 알고 넘어가야 한다. 이를 위해 구조체, 포인터, 동적 메모리 할당 등의 개념이 사용된다.

 

연결 리스트

연결 리스트란 데이터가 담긴 노드(메모리 공간)를 일렬로 연결하여 리스트화 한 것이다.

 

연결 리스트 특징

• 리스트의 중간 지점에서 노드를 손쉽게 추가하거나 삭제할 수 있다.
• 특정 노드를 찾으려면 노드를 모두 검색해야 한다.(최악의 경우) -> 하나씩 찾아봐야 하기 때문에 원하는 노드를 찾는데 오래 걸린다.
• 크기가 고정되어 있지 않다.

 

연결 리스트 기능

연결 리스트에서는 다음이 가능하다.

 

• 추가
• 삭제
• 찾기

 

노드 간 연결

 

새 노드 추가

 

 

노드 삭제

 

연결 리스트 코드

 

연결 리스트 코드 구현

 

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

struct NODE { // 연결 리스트의 노드 구조체
    struct NODE *next; // 다음 노드의 주소를 저장할 포인터, 구조체 자기 자신의 포인터를 멤버로 가지고 있음
    int data; // 데이터를 저장할 멤버
};

void addFirst(struct NODE *target, int data) // 기준 노드 뒤에 노드를 추가하는 함수
{
    struct NODE *newNode = malloc(sizeof(struct NODE)); // 새 노드 생성
    newNode->next = target->next; // 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정
    newNode->data = data; // 데이터 저장

    target->next = newNode; // 기준 노드의 다음 노드에 새 노드를 지정
}

void removeFirst(struct NODE *target) // 기준 노드의 다음 노드를 삭제하는 함수
{
    struct NODE *removeNode = target->next; // 기준 노드의 다음 노드 주소를 저장
    target->next = removeNode->next; // 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정

    free(removeNode); // 노등 메모리 해제
}


struct NODE *findNode(struct NODE *node , int data)
{
    if (node == NULL) 
        return NULL;

    struct NODE *curr = node->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
    while(curr != NULL)
    {
        if(curr->data == data) // curr의 멤버 data 값이 입력받은 data와 같으면
            return curr; // curr node return
        curr = curr->next;  // 아닌 경우 next

    }
    return NULL;
   
}

int main()
{
    struct NODE *head = malloc(sizeof(struct NODE));

    struct NODE *node1 = malloc(sizeof(struct NODE)); // 첫 번째 노드 생성
    head->next = node1; // 머리 노드 다음은 첫 번째 노드
    node1->data = 10; // 첫 번째 노드에 10 저장

    struct NODE *node2 = malloc(sizeof(struct NODE)); // 두 번째 노드 생성
    node1->next = node2; // 첫 번째 노드 다음은 두 번째 노드
    node2->data = 20; // 두 번째 노드에 20 저장

    node2->next = NULL; // 두 번째 노드 다음은 노드가 없음(NULL)

    addFirst(node2, 50);
    addFirst(node2, 40);
    addFirst(node2, 30);

    removeFirst(head); // head 다음 노드 삭제

    struct NODE *found = findNode(head, 20); // head 다음부터 20 값을 가진 노드 찾기
    printf("데이터 찾음 : %d\n", found->data);

    struct NODE *curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

    while (curr != NULL) 
    {
        printf("%d\n", curr->data); // 현재 노드의 데이터 출력
        curr = curr->next; // 포인터에 다음 노드의 주소 저장
    }

    curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
    while(curr !=NULL) 
    {
        struct NODE *next = curr->next; // 현재 노드의 다음 노드 주소를 임시로 저장
        free(curr);
        curr = next;
    }
    free(head);

    return 0;
}

 

마지막에 모든 노드들을 free하는 것을 잊지 말자!