C Data Structure - 연결 리스트

하 코딩해놓고 묵혀뒀다가 포스팅하느라 다시 보고 시간 버리는게 너무 아깝다 앞으로는 정말 열심히 바로바로 정리해서 올려야겠다.

그래도 다시 복습할 기회가 되었으니 의미있는 시간이라 생각하고 일반 연결 리스트에 대한 기록이다.

내가 (윤성우 교수님의 자료구조 책의 ADT를 보고) 코딩한 연결 리스트는 살짝 형태가 다르다. 그러므로 특징에 대해서 그림과 글의 적절한 특징 설명 이후 코드와 실행결과를 기록 하겠다.

일단,

단순 연결 리스트란?

구조체와 주소 값을 이용하여 현재 노드 내부에 다음 순서 노드의 주소 값이 저장되어 있는 형태로 이 이어진 연결을 통해 값을 순회할 수 있는 자료 구조이다.

노드 내부에 다음 순서 노드의 주소 값이 저장되어 있다는 것은 이러한 경우를 뜻한다.

구조

원래는 아래 그림과 같은 형식으로 리스트가 구성되어졌어야 했는데 

원래 이런 형식으로 초기 구성되어야 하는데

머리 회전이 덜 된 관계로 아래 처럼 다른 리스트를 만들어버렸다. 그건 뭐 그거대로 기록할 것임.

이렇게 해버렸음. 이걸로 설명을 적는다

노드를 추가한 형태

일단 위 구조로 생겨먹었고, 노드 구조체와 그 노드들을 담고 관리하는 자료구조 구조체가 있다

새 노드가 항상 헤드 다음 즉, 실질 데이터 노드 맨 앞에 항시 존재해야만 한다. 값을 추가할 때, 값과 링크 값만 변경하고 사용한다. 위와 같은 특성 때문에 리스트를 초기화할 때 다음 그림과 같이 꼭 -1 값으로 초기화 한다.

초기화 및 추가

값을 추가할 때에는 빈 노드의 값을 변경하여 사용하지만, 그래도 어찌됐던 빈 노드를 헤드 다음, 데이터 노드들 맨 앞에 두는 것이 원칙이기 때문에 데이터를 추가할 때 빈 노드 또한 추가해 놓아야 한다.

순회
다음은 순회이다.

삭제 
다음은 삭제이다. 내가 따로 만든 함수들이 있기 때문에 간단하게 설명한다.

 

코드 및 실행 결과

----

#include <stdio.h>
#include <stdlib.h>
 
struct ListNode {
    int data;
    struct ListNode* link;
};
 
struct ListManager
{
    struct ListNode* head;
    struct ListNode* ci; // current index; 
    struct ListNode* pi; // previous index;
 
    int node_count; // data 값이 유효한 node의 수
    int malloc_count; // 할당된 수
};
 
void ListInit(struct ListManager* lm);
void LInsert(struct ListManager* lm, int data);
int LFirst(struct ListManager* lm, int* data);
int LNext(struct ListManager* lm, int* data);
int LCount(struct ListManager* lm);
int LRemove(struct ListManager* lm);
 
void* CreateNodeMemory(struct ListManager* lm, int len);
void ShowList(struct ListManager* lm);
void DeleteNode(struct ListManager* lm, struct ListNode* target);
void DeleteList(struct ListManager* lm);
 
 
 
int main(void)
{
    struct ListManager lm;
    int data;
    ListInit(&lm);
 
    // 11, 11, 22, 22, 33 삽입
    LInsert(&lm, 11);
    LInsert(&lm, 11);
    LInsert(&lm, 22);
    LInsert(&lm, 22);
    LInsert(&lm, 33);
 
    printf("[11, 11, 22, 22, 33] 값 삽입 후 연결 리스트에 저장된 수 : (%d)\n", LCount(&lm));
    ShowList(&lm);
    fputc('\n', stdout);
 
    // 22, 22 삭제
    if (LFirst(&lm, &data))
    {
        if (data == 22)
            LRemove(&lm);
        while (LNext(&lm, &data))
        {
            if (data == 22)
                LRemove(&lm);
        }
    }
    printf("[22, 22] 값 삭제 후 연결 리스트에 저장된 수 : (%d)\n", LCount(&lm));
    ShowList(&lm);
    fputc('\n', stdout);
 
    // 나머지 11, 11, 33 삭제
    if (LFirst(&lm, &data))
    {
        if (data == 11 || data == 33)
            LRemove(&lm);
        while (LNext(&lm, &data))
        {
            if (data == 11 || data == 33)
                LRemove(&lm);
        }
    }
 
    printf("[11, 11, 33] 값 삭제 후 연결 리스트에 저장된 수 : (%d)\n", LCount(&lm));
    ShowList(&lm);
    fputc('\n', stdout);
 
    // 원래대로 삽입 복원
    LInsert(&lm, 11);
    LInsert(&lm, 11);
    LInsert(&lm, 22);
    LInsert(&lm, 22);
    LInsert(&lm, 33);
 
    printf("원래 [11, 11, 22, 22, 33] 값 삽입 후 연결 리스트에 저장된 수 : (%d)\n", LCount(&lm));
    ShowList(&lm);
    fputc('\n', stdout);
 
    printf("완전 리스트 자체 삭제 이후 : (%d)\n", LCount(&lm));
    DeleteList(&lm);
    ShowList(&lm);
 
    printf("\n\n");
    return 0;
}
 
 
void ListInit(struct ListManager* lm)
{
    // count 초기화
    lm->node_count = 0;
    lm->malloc_count = 0;
 
    // head 다음으로 항상 유지하는 빈 노드 생성
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    new_node->data = -1;
    new_node->link = NULL; // 제일 끝이므로 무조건 NULL을 갖는다.
 
    // 연결리스트 헤드 초기화
    lm->head = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    lm->head->data = -1;
    lm->head->link = new_node;
 
    // 인덱스 초기화
    lm->ci = NULL;
    lm->pi = NULL;
 
    return;
}
 
void LInsert(struct ListManager* lm, int data)
{
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
 
    // head 다음의 빈 노드에 값을 반영, 링크는 건들지 않는다.
    lm->head->link->data = data;
 
    // empty_node 설정
    new_node->data = -1;
    new_node->link = lm->head->link;
    lm->head->link = new_node;
 
    lm->node_count++;
    return;
}
 
int LFirst(struct ListManager* lm, int* data)
{
    if (lm->node_count == 0)
    {
        printf("순회할 노드가 없습니다.\n");
        return false;
    }
    lm->ci = lm->head->link->link;
    lm->pi = lm->head->link;
 
    *data = lm->ci->data;
    return true;
}
 
int LNext(struct ListManager* lm, int* data)
{
    if (lm->ci->link == NULL)
        return false;
 
    lm->pi = lm->ci;
    lm->ci = lm->ci->link;
    *data = lm->ci->data;
    return true;
}
 
int LCount(struct ListManager* lm)
{
    return lm->node_count;
}
 
int LRemove(struct ListManager* lm)
{
    int remove_value = lm->ci->data;
    struct ListNode* rtarget = lm->ci;
 
    lm->pi->link = rtarget->link;
    lm->ci = lm->pi;
 
    DeleteNode(lm, rtarget);
    return remove_value;
}
 
void* CreateNodeMemory(struct ListManager* lm, int len)
{
    lm->malloc_count++;
    return (void*)malloc(len);
}
 
void ShowList(struct ListManager* lm)
{
    struct ListNode* index_node = NULL;
 
    if (lm->malloc_count == 0)
    {
        printf("head와 new node 및 일반 node들까지 모두 존재하지 않습니다.");
        return;
    }
    else if (lm->node_count == 0)
        printf("추가된 노드는 모두 제거된 상태이지만, head와 new node가 존재하고 추가 가능한 상태입니다.\n");
 
    for (index_node = lm->head; index_node != NULL; index_node = index_node->link)
    {
        printf("[%d|%p]", index_node->data, index_node);
        if (index_node->link != NULL)
            printf("->");
    }
    fputc('\n', stdout);
    return;
}
 
void DeleteNode(struct ListManager* lm, struct ListNode* target)
{
    if (target->data != -1)
        lm->node_count--;
 
    free(target);
    lm->malloc_count--;
 
    return;
}
 
void DeleteList(struct ListManager* lm)
{
    struct ListNode* index_node = NULL;
    struct ListNode* next_node = NULL;
    for (index_node = lm->head; index_node != NULL; index_node = next_node)
    {
        next_node = index_node->link;
        DeleteNode(lm, index_node);
    }
    if (lm->malloc_count != 0)
        printf("메모리 해체에 문제가 있습니다\n");
    return;
}
 
 

----

메모리 관리가 중요한 것 같다.ㅋ