링크드 리스트(Linked list)

: 노드들의 집합

노드는 연결 리스트의 각 자료
연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 데이터를 저장하는 자료구조
제일 마지막 노드는 NULL 포인터

장점: 길이가 가변적이다 (배열의 단점을 보완)
단점: 원하는 노드나 데이터를 찾을 때 일일이 탐색해야된다, 메모리 누수에 주의해야된다

단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트 중에서
단순 연결 리스트로 구현을 할 것이다

---

구현 조건

+) 2주차 스터디
동적할당과 구조체를 이용해 정수형 변수를 저장하는 단방향 링크드 리스트를 구현합니다.
원소의 삽입, 검색, 수정, 삭제 (CRUD)를 구현해주세요
1주차와 마찬가지로 할당한 메모리를 해제할 수 있는 로직이 있어야 합니다

추가과제

• 연결 리스트와 배열의 차이와 장단점 생각해보기
• 더블리 링크드 리스트 구현
• 다른 언어에서 구현되어있는 연결 리스트를 가져오는 방법 찾아보기 -> 이게 무슨말이지?

---

사용할 함수

• init_list()
  : 초기화하는 함수
  헤더에는 데이터를 저장하지 않는다

• add_first_node()
  : head 바로 뒤에 새로운 노드를 생성(할당)한다
  데이터를 받아서 생성한 노드에 저장한다

• add_last_node()
  : 리스트의 가장 뒷쪽에 새로운 노드를 생성(할당)한다
  데이터를 받아서 생성한 노드에 저장한다

• insert_node()
  : 현재 위치에서 새로운 노드를 생성(할당)하여 삽입한다
  데이터를 받아서 생성한 노드에 저장한다
  add_first_node, add_last_node를 호출한다
  새로운 노드의 next가 이전 노드의 next를 가리키도록
  이전 노드의 next가 새로운 노드를 가리키도록

• read_node_idx()
  : 노드를 인덱스로 찾는다
  순회용 포인터를 하나 만든다

• read_node_data()
  : 노드를 데이터로 찾는다
  순회용 포인터를 하나 만든다

• edit_node()
  : 노드의 데이터를 수정한다

• delete_first_node()
  : 첫번째 노드를 제거한다
  head의 next를 첫번째 노드의 next를 가리키도록
  첫번째 노드의 next는 NULL을 가리키도록
  첫번째 노드 메모리 할당 해제

• delete_node()
  : 현재 위치의 노드를 제거한다
  prev의 next가 현재 포인터의 next를 가리키도록
  현재 포인터의 next가 NULL을 가리키도록
  메모리 할당 해제

• delete_all_node()
  : 모든 노드를 제거한다
  메모리 할당 해제

• print_all_node()
  : 모든 노드를 출력한다

---

소스코드

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

typedef struct listNode
{
    struct listNode *next;
    int data;
}listNode;

listNode *init_list()
{
    listNode *head;
    head = (listNode *)malloc(sizeof(listNode));
    head->next = NULL;

    return (head);
}

listNode *find_end(listNode *h)
{
    listNode *cur;
    cur = h;

    while (cur->next != NULL)
    {
        cur = cur->next;
    }
    return (cur);
}

int node_len(listNode *h)
{
    int cnt;
    listNode *cur;
    cur = h;

    cnt = 0;
    while (cur->next != NULL)
    {
        cnt++;
        cur = cur->next;
    }
    return (cnt);
}

listNode *read_node_idx(listNode *h, int num)
{
    int i;
    listNode *cur;
    cur = h;

    i = 0;

    if (num < 1 || num > node_len(h))
    {
        printf("wrong data\n");
        return (h);
    }
    while (i < num)
    {
        cur = cur->next;
        i++;
    }
    return (cur);
}

listNode *read_node_data(listNode *h, int data)
{
    listNode *cur;
    cur = h;

    while (cur->data != data && cur->next != NULL)
    {
        cur = cur->next;
    }
    if(cur->next == NULL)
    {
        printf("wrong data\n");
        return (h);
    }

    return (cur);
}

void add_first_node(listNode *h, int data)
{
    listNode *newNode;
    newNode = (listNode *) malloc(sizeof(listNode));
    newNode->data = data;
    newNode->next = h->next;
    h->next = newNode;
}

void add_last_node(listNode *h, int data)
{
    listNode *end;
    end = find_end(h);
    listNode *newNode;
    newNode = (listNode *) malloc(sizeof(listNode));
    newNode->data = data;
    end->next = newNode;
    newNode->next = NULL;

}

void insert_node(listNode *h, int n, int data)
{
    if (n == 1)
        add_first_node(h,data);
    else if (n == node_len(h))
        add_last_node(h, data);
    else if (n < 1 && n > node_len(h))
    {
        printf("wrong range\n");
        return ;
    }
    else
    {
        int i;
        listNode *prev;
        prev = h;
        i = 0;
        while (i < n - 1)
        {
            prev = prev->next;
            i++;
        }
        listNode *newNode;
        newNode = (listNode *) malloc(sizeof(listNode));
        newNode->data = data;
        newNode->next = prev->next;
        prev->next = newNode;
    }
}

void edit_node(listNode *h, int search, int modify)
{
    listNode *s;
    s = read_node_idx(h, search);
    //s = read_node_data(search);
    if(s == h)
    {
        return ;
    }
    s->data = modify;
}

void delete_first_node(listNode *h)
{
    listNode *cur;
    cur = h->next;
    h->next = cur->next;
    cur->next = NULL;

    free(cur);
}

void delete_node(listNode *h, int n)
{
    if (n == 1)
        delete_first_node(h);
    else if (n < 1 && n > node_len(h))
    {
        printf("wrong range\n");
        return ;
    }
    else
    {
        int i;
        listNode *prev;
        prev = h;
        i = 0;
        while (i < n - 1)
        {
            prev = prev->next;
            i++;
        }
        listNode *cur;
        cur = prev->next;
        prev->next = cur->next;
        cur->next = NULL;

        free(cur);
    }
}

void delete_all_node(listNode *h)
{
    listNode *cur;
    cur = h;

    listNode *nxt;
    while(cur != NULL)
    {
        nxt = cur->next;

        free(cur);
        cur = nxt;
    }
    free(h);
}

void print_all_node(listNode *h)
{
    listNode *cur;
    cur = h->next;

    if(cur != NULL)
    {
        while (1)
        {
            printf("%d", cur->data);
            if (cur->next == NULL)
            {
                printf("\n");
                break;
            }
            else
                printf("->");
            cur = cur->next;
        }
    }
    else
    {
        printf("No data\n");
    }
}

코드는 이렇고

int main()
{
    listNode *h;
    h = init_list();

    add_last_node(h, 555);
    print_all_node(h);
    add_first_node(h, 777);
    print_all_node(h);
    add_first_node(h, 214);
    print_all_node(h);
    add_last_node(h, 7891);
    print_all_node(h);

    delete_first_node(h);
    print_all_node(h);
    delete_node(h, 2);
    print_all_node(h);

    edit_node(h, 777, 1234567);
    print_all_node(h);
    edit_node(h, 1, 90001);
    print_all_node(h);

    delete_all_node(h);

    return (0);
}

테케 메인은 이렇고

그에 따른 출력은 다음과 같다