[Linked List] 학생 정보 Linked List 구현

LINKED LIST란?

Linked List를 구현하기 전 간단히 Linked List가 무엇인지에 대해서 짚고 넘어가겠습니다.

Linked List는 메모리에 흩어진 각각의 node들이 연결되어 구성되는 List를 말합니다. 메모리 내에서부터 연결된 기본적인 List와는 다르게 흩어져있는 정보들을 특정한 방법으로 연결 지어 리스트화해 주어야 비로소 Linked List가 완성됩니다.

 

 일반적인 List로 "hey" 저장: char word[4] = "hey";

(Memory Address)	1000	1001	1002	1003
(Data)	'h'	'e'	'y'	'\0'

 

Linked List로 "hey" 저장

 

 

Linked List는 List와 비교했을 때 아래와 같이 각각 장단이 있습니다. 따라서 상황에 따라 적절하게 사용해 주는 것이 좋습니다.

• 덧붙이거나 삽입하기에 편리하다 
• 어떤 node에 접근하더라도 첫 번째 node부터 접근해야 한다
• node 간 연결을 위해서 추가적인 메모리를 사용해야 한다.

 

학생 정보를 LINKED LIST로 구현하는 프로그램

 [ 프로그램 기본 정보 ] 

그럼 이제 학생 정보를 저장하는 Linked List를 구현해보려 합니다. 구현하려는 프로그램의 기능은 다음과 같습니다.

A [학번] [이름] : 학생을 id 오름차순으로 추가하고, 추가한 후의 Linked List를 출력 (ADD 기능)
F [학번]            : 해당되는 학번의 학생을 검색하여 학생의 학번과 이름을 출력 (FIND 기능)
D [학번]            : 해당되는 학번의 학생을 삭제하고, 삭제한 후의 Linked List를 출력 (DELETE 기능)

 

 

따라서 Input 파일을 아래와 같이 생성하고

A 10003 Mike
A 10000 Alice
A 10010 Tom
A 10010 Tim
F 10001
F 10000
A 10103 Sam
D 10003
D 10003
A 10112 Lily

 

실행하면 아래와 같은 Output 파일이 생성됩니다. 

10003 Mike 
10000 Alice 10003 Mike 
10000 Alice 10003 Mike 10010 Tom 
Addition Failed
Search Failed
10000 Alice
10000 Alice 10003 Mike 10010 Tom 10103 Sam 
10000 Alice 10010 Tom 10103 Sam 
Deletion Failed
10000 Alice 10010 Tom 10103 Sam 10112 Lily 

 

 

 [ 프로그램 코드 ]  

구현을 위한 코드를 기능별로 쪼개어 보겠습니다. 전체 코드는 너무 길어 마지막에 배치했으니 참고해 주세요.

 

 구조체 및 기본 적인 함수 

첫 번째로, Linked List를 구현하기 위해서 C에서는 구조체를 필요로 합니다. 데이터와 가리킬 다음 노드의 주소를 하나의 노드로 묶어야 하기 때문입니다. 따라서  STUDENT 라는 구조체를 하나 생성하여, 우리가 담을 데이터(id, name)와 다음 노드의 주소를 가리키는 변수(next)를 추가해 줍니다.

다음으로 COURSE 구조체는 단순히 Linked List 중 head를 가리키기 위한 구조체로, main 함수 설명에서 그 쓰임을 더 정확히 알 수 있습니다. Linked List는 탐색, 추가 등의 거의 모든 기능을 head로부터 시작하기 때문에, head를 기록해 놓는 것은 매우 중요합니다.

기본 기능을 담은 첫 번째 함수인 isEmpty()  함수는 head를 기록해 둔 COURSE 구조체를 인자로 받아, head가 존재하는지 확인하여, Linked List가 빈 리스트인지 아닌지를 리턴합니다. 

두 번째 함수인  print_linked()  함수는 마찬가지로 head를 기록해 둔 COURSE 구조체를 인자로 받아, head부터 tail까지 Linked List 전체를 output 파일에 출력합니다. 

// Linked List의 Node에 해당하는 STUDENT 구조체
typedef struct STUDENT
{
    int id;
    char name[20];
    struct STUDENT *next;
} Student;

// Linked List의 head를 기록하는 COURSE 구조체
typedef struct COURSE
{
    Student *head;
} Course;

// Linked List가 비어있는지 head를 통해 확인하는 isEmpty 함수
int isEmpty(Course *c)
{
    return (c->head == NULL);
}

// Linked List를 head부터 tail까지 output 파일에 입력하는 print_linked 함수
void print_linked(Course *c, FILE *out)
{
    Student *h = c->head;
    while (h)
    {
        fprintf(out, "%d %s ", h->id, h->name);
        h = h->next;
    }
    fputc('\n', out);
}

 

 ADD 기능 

ADD 기능에서는 학번과 이름을 Input으로 받아 이를 오름차순으로 Linked List에 추가해야 합니다. 따라서 이를 구현한 Add 함수에서는  [head를 기록해 둔 Course 구조체의 객체, 학번, 이름]을 인자로 받게 됩니다. 또한 Integer를 return하게 되는데, 여기서는 0을 False(오류), 1을 True(정상동작)로 사용하여, 함수가 동작한 후 main함수에서 정상 동작 여부를 판단하는 방식으로 사용할 것입니다. 

함수에서는 첫 번째로 Linked List가 비어있는지 먼저 확인한 후, 비어있다면 해당 학생의 정보를 Linked List의 head로 넣습니다. 하지만 Linked List가 비어있지 않다면 입력받은 학번에 맞는 위치에 해당 학생의 정보를 넣어주어야 합니다. 

int Add(Course *c, int id, char *name)
{
    // Linked List가 비어있다면, 현재 인자로 받은 학생을 head로 추가
    if (isEmpty(c))
    {
        c->head = (Student *)malloc(sizeof(Student));
        c->head->next = NULL;
        c->head->id = id;
        strcpy(c->head->name, name);
        return 1;
    }
    
    // 현재 head node와 인자로 받은 id가 일치한다면 0 return으로 오류 처리
    if (c->head->id == id) return 0;
    
    // tail을 찾기 위한 h 변수
    Student *h = c->head;
    
    // 현재 학생 정보를 저장할 s변수
    Student *s = (Student *)malloc(sizeof(Student));
    strcpy(s->name, name);
    s->id = id;
    s->next = NULL;

    // head node의 id가 현재 학생의 id보다 클 경우 (현재 학생 node가 head보다 앞으로 가야 함)
    if (h->id > id)
    {
        s->next = h;
        c->head = s;
        return 1;
    }

    // s가 들어갈 위치 찾아서 s 삽입
    while ((h->next) && (h->next->id < id)) h = h->next; 
    if (h->next)
    {
        if (h->next->id == id)
        {
            free(s);
            return 0;
        }
        s->next = h->next;
        h->next = s;
    }
    else h->next = s;
    return 1;
}

 

 FIND 기능 

FIND 기능에서는 linked list의 head 정보와 학번을 인자로 받아, 해당 아이디를 가진 학생 구조체를 return 합니다. FIND 기능은 간단한 편인데, head부터 차례로 모든 node를 순회하다가 찾으려는 학번과 같은 학번을 가진 학생정보를 찾으면 해당 정보를 리턴하고, 만약 해당 학번을 가진 학생이 없으면 Null 포인터를 return 하면 됩니다. 

Student *Find(Course *c, int id)
{
    // 배열이 비어있다면 Null return
    if (isEmpty(c)) return NULL;

    // h를 head로 지정해놓고, linked list를 순회하면서 id와 동일한 id가 있는지 확인
    Student *h = c->head;
    while (h)
    {
        if (h->id == id) return h;  // 동일한 아이디 찾으면 return
        h = h->next;
    }
    return NULL;  // 검색에 실패한다면 Null return
}

 

 

 

 DELTE 기능

DELETE 기능에서는 linked list의 head 정보와 학번을 인자로 받아, 해당 아이디를 가진 학생 구조체를 linked list에서 삭제하는 함수가 필요합니다. 삭제에 성공한다면 1을 리턴하고, 실패한다면 0을 리턴합니다. ADD 기능에서와 같이 0을 False(오류), 1을 True(정상동작)로 사용하는 것입니다. 배열이 비어있거나, 인자로 주어진 학번을 가진 학생이 존재하지 않는 경우가 0을 return하는 경우입니다. 

여기서 FIND 기능을 사용할 수 있지 않냐고 생각할 수 있지만, 해당하는 node를 삭제한 이후 이전 노드와 그 다음 노드를 다시 연결해줘야 하기 때문에 이전 노드까지 함께 파악해야 하여, 따로 search하는 과정을 만들어줬습니다. head를 삭제하는 경우에는 다른 node를 삭제하는 것과는 다르게 head를 다시 지정해줘야 하므로 따로 if문 안에서 해결해 줍니다. 

 

int Delete(Course *c, int id)
{
    // 배열이 비어있다면, 삭제에 실패한 것이므로 0 return
    if (isEmpty(c)) return 0;

    Student *prev = c->head;
    Student *curr = prev->next;
    
    // head id와 id가 같은 경우 (head node를 삭제해야 하는 경우)
    if (id == prev->id)  
    {
        c->head = curr;
        free(prev);
        return 1;
    }

    // curr id와 id가 다를때까지 순회
    while (curr && (curr->id != id))
    {
        prev = curr;
        curr = curr->next;
    }
    // id를 찾지 못했을 경우 0 return
    if (!curr) return 0;
    else  // 찾았을 경우 현재 node를 삭제하고 이전 node와 현재 node의 다음 node를 연결
    {
        prev->next = curr->next;
        free(curr);
        return 1;
    }
}

 

 main 함수 

main 함수는 각각의 기능을 input 파일로부터 입력받아 알맞은 함수를 실행시키고, output 파일에 적절히 결괏값을 입력하는 기본적인 내용을 담고 있습니다. Linked List와 관련된 주요 내용이 아니기 때문에 자세한 설명을 생략하겠습니다. 

int main(int argc, char **argv)
{
    if (argc != 3)
    {
        printf("Correct Usage : [program] [intput file] [output file]");
        return 0;
    }

    FILE *input = fopen(argv[1], "r");
    FILE *output = fopen(argv[2], "w");

    if ((input == NULL) || (output == NULL))
    {
        printf("Failed to Open File");
        return 0;
    }

    char ch;
    int id;
    Course *c = (Course *)malloc(sizeof(Course));
    c->head = NULL;
    while ((ch = fgetc(input)) != EOF)
    {
        if (ch == '\n') continue;
        else if (ch == 'A')
        {
            int id;
            fscanf(input, "%d", &id);

            char name[20];
            fscanf(input, "%s", name);

            if (Add(c, id, name)) print_linked(c, output);
            else fputs("Addition Failed\n", output);
        }
        else if (ch == 'D')
        {
            int id;
            fscanf(input, "%d", &id);

            if (Delete(c, id)) print_linked(c, output);
            else fputs("Deletion Failed\n", output);
        }
        else if (ch == 'F')
        {
            int id;
            fscanf(input, "%d", &id);
            Student *q = Find(c, id);
            if (q) fprintf(output, "%d %s\n", q->id, q->name);
            else fputs("Search Failed\n", output);
        }
        else 
        {
            fputs("FUNCTION ERROR\n", output);
            while((ch = fgetc(input)) != '\n') continue;
        }
    }

    fclose(input);
    fclose(output);
    free(c);
}

 

 

 

전체 코드

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

typedef struct STUDENT
{
    int id;
    char name[20];
    struct STUDENT *next;
} Student;

typedef struct COURSE
{
    Student *head;
} Course;

int isEmpty(Course *c)
{
    return (c->head == NULL);
}

int Add(Course *c, int id, char *name)
{
    if (isEmpty(c))
    {
        c->head = (Student *)malloc(sizeof(Student));
        c->head->next = NULL;
        c->head->id = id;
        strcpy(c->head->name, name);
        return 1;
    }
    if (c->head->id == id) return 0;
    

    Student *h = c->head;
    Student *s = (Student *)malloc(sizeof(Student));
    strcpy(s->name, name);
    s->id = id;
    s->next = NULL;

    if (h->id > id)
    {
        s->next = h;
        c->head = s;
        return 1;
    }

    while ((h->next) && (h->next->id < id)) h = h->next; 
    if (h->next)
    {
        if (h->next->id == id)
        {
            free(s);
            return 0;
        }
        s->next = h->next;
        h->next = s;
    }
    else h->next = s;
    return 1;
}

void print_linked(Course *c, FILE *out)
{
    Student *h = c->head;
    while (h)
    {
        fprintf(out, "%d %s ", h->id, h->name);
        h = h->next;
    }
    fputc('\n', out);
}

int Delete(Course *c, int id)
{
    if (isEmpty(c)) return 0;

    Student *prev = c->head;
    Student *curr = prev->next;
    if (id == prev->id)
    {
        c->head = curr;
        free(prev);
        return 1;
    }

    while (curr && (curr->id != id))
    {
        prev = curr;
        curr = curr->next;
    }
    if (!curr) return 0;
    else
    {
        prev->next = curr->next;
        free(curr);
        return 1;
    }
}

Student *Find(Course *c, int id)
{
    if (isEmpty(c)) return NULL;

    Student *h = c->head;
    while (h)
    {
        if (h->id == id) return h;
        h = h->next;
    }
    return NULL;
}

int main(int argc, char **argv)
{
    if (argc != 3)
    {
        printf("Correct Usage : [program] [intput file] [output file]");
        return 0;
    }

    FILE *input = fopen(argv[1], "r");
    FILE *output = fopen(argv[2], "w");

    if ((input == NULL) || (output == NULL))
    {
        printf("Failed to Open File");
        return 0;
    }

    char ch;
    int id;
    Course *c = (Course *)malloc(sizeof(Course));
    c->head = NULL;
    while ((ch = fgetc(input)) != EOF)
    {
        if (ch == '\n') continue;
        else if (ch == 'A')
        {
            int id;
            fscanf(input, "%d", &id);

            char name[20];
            fscanf(input, "%s", name);

            if (Add(c, id, name)) print_linked(c, output);
            else fputs("Addition Failed\n", output);
        }
        else if (ch == 'D')
        {
            int id;
            fscanf(input, "%d", &id);

            if (Delete(c, id)) print_linked(c, output);
            else fputs("Deletion Failed\n", output);
        }
        else if (ch == 'F')
        {
            int id;
            fscanf(input, "%d", &id);
            Student *q = Find(c, id);
            if (q) fprintf(output, "%d %s\n", q->id, q->name);
            else fputs("Search Failed\n", output);
        }
        else 
        {
            fputs("FUNCTION ERROR\n", output);
            while((ch = fgetc(input)) != '\n') continue;
        }
    }

    fclose(input);
    fclose(output);
    free(c);
}