[C 자/알] 배열, 가변 배열, 링크드리스트

배열, 가변 배열, 링크드리스트는 구현을 하는 과제에서 주로 등장한다

 

배열

배열은 연속적인 메모리 공간에 요소들을 저장하기 때문에

인덱스를 통해 상대적인 위치를 참조할 수 있다

배열을 생성할 때 길이를 지정하고 길이의 변경은 불가능하다

또한, 중간 삽입/삭제가 불가능하다

 

배열 구현 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

enum
{
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    MAX_COUNT = 101
};

typedef struct Array
{
    int Data[MAX_COUNT];
    size_t Count;
} Array_t;

void Insert(Array_t* InArray, size_t InIndex, int InData);
void RemoveOrderly(Array_t* InArray, size_t InIndex);
void RemoveUnorderly(Array_t* InArray, size_t InIndex);
size_t Find(Array_t* InArray, int InData);
void Print(Array_t* InArray);

int main(void)
{
    size_t i;
    Array_t arr = {
        0,
    };

    for (i = 0; i < 5; ++i)
    {
        Insert(&arr, i, (int)i * 2);
    }
    Print(&arr);

    RemoveOrderly(&arr, 2);
    Print(&arr);

    RemoveUnorderly(&arr, 1);
    Print(&arr);

    printf("1 is in %zu", Find(&arr, 6));

    return 0;
}

void Insert(Array_t* InArray, size_t InIndex, int InData)
{
    size_t i;

    assert(InIndex <= InArray->Count);
    assert(InArray->Count < MAX_COUNT);

    for (i = InArray->Count; i > InIndex; --i)
    {
        InArray->Data[i] = InArray->Data[i - 1];
    }
    InArray->Data[InIndex] = InData;
    ++InArray->Count;
}

void RemoveOrderly(Array_t* InArray, size_t InIndex)
{
    size_t i;

    assert(InIndex <= InArray->Count);

    --InArray->Count;
    for (i = InIndex; i < InArray->Count; ++i)
    {
        InArray->Data[i] = InArray->Data[i + 1];
    }
}

void RemoveUnorderly(Array_t* InArray, size_t InIndex)
{
    assert(InIndex < InArray->Count);

    InArray->Data[InIndex] = InArray->Data[--InArray->Count];
}

size_t Find(Array_t* InArray, int InData)
{
    size_t i;

    for (i = 0; i < InArray->Count; ++i)
    {
        if (InData == InArray->Data[i])
        {
            return i;
        }
    }
    return INVALID_INDEX;
}

void Print(Array_t* InArray)
{
    size_t i;

    for (i = 0; i < InArray->Count; ++i)
    {
        printf("[%zu]: %d\n", i, InArray->Data[i]);
    }
}

 

가변 배열

배열은 크기 변경이 불가능했기 때문에 이를 해결하기 위해 등장했다

기본적으로 배열과 동일하게 작동하지만

길이 이상으로 데이터가 삽입을 한다면, 길이의 N배 만큼 동적 할당을 받아

길이를 관리한다

 

가변 배열 구현 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

enum
{
    FALSE = 0,
    TRUE = 1,
    INITIAL_CAPACITY = 8,
    INCREMENT = 2
};

typedef struct VariableLengthArray
{
    int* Data;
    size_t Count;
    size_t Capacity;
} VariableLengthArray_t;

void Destroy(VariableLengthArray_t* InVariableArray);
void Initialize(VariableLengthArray_t* InVariableArray);
void Reallocate(VariableLengthArray_t* InVariableArray);
void Insert(VariableLengthArray_t* InVariableArray, int InDara);
void Print(VariableLengthArray_t* InVariableArray);

int main(void)
{
    int Input;
    VariableLengthArray_t VLA;

    Initialize(&VLA);

    while (TRUE)
    {
        printf("[Stop with -1]Data: ");
        
        scanf("%d", &Input);
        if (-1 == Input)
        {
            break;
        }

        Insert(&VLA, Input);

        Print(&VLA);
    }

    Destroy(&VLA);

    return 0;
}

void Destroy(VariableLengthArray_t* InVariableArray)
{
    free(InVariableArray->Data);
    InVariableArray->Data = NULL;
}

void Initialize(VariableLengthArray_t* InVariableArray)
{
    InVariableArray->Data = (int*)malloc(INITIAL_CAPACITY * sizeof(int));
    InVariableArray->Capacity = INITIAL_CAPACITY;
    InVariableArray->Count = 0;
}

void Reallocate(VariableLengthArray_t* InVariableArray)
{
    int* Temp = NULL;
    size_t i;

    Temp = (int *)malloc(InVariableArray->Capacity * INCREMENT * sizeof(int));
    for (i = 0; i < (InVariableArray->Count); ++i)
    {
        Temp[i] = InVariableArray->Data[i];
    }

    Destroy(InVariableArray);
    InVariableArray->Data = Temp;
    InVariableArray->Capacity *= INCREMENT;
}

void Insert(VariableLengthArray_t* InVariableArray, int InDara)
{
    if (InVariableArray->Capacity <= InVariableArray->Count)
    {
        Reallocate(InVariableArray);
    }

    *(InVariableArray->Data + InVariableArray->Count) = InDara;
    ++InVariableArray->Count;
}

void Print(VariableLengthArray_t* InVariableArray)
{
    size_t i;

    for (i = 0; i < InVariableArray->Capacity; ++i)
    {
        printf("[%zu]: %d\n", i, *(InVariableArray->Data + i));
    }

    printf("\n");
}

 

링크드리스트

배열과 가변 배열은 중간 삽입/삭제가 불가능하기 때문에 이를 해결하기위해 등장했다

연속된 메모리 구조가 아닌 노드라는 데이터 단위를 사용하고

노드에는 데이터와 다음 노드 시작 주소를 보관한다

 

링크드리스트 구현 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

enum
{
    FALSE = 0,
    TRUE = 1,
};

typedef struct Node
{
    int Data;
    struct Node* NextNode;
    /* struct Node_t* 라고 적으면 안됨. */
} Node_t;

void Destroy(Node_t* RootNode);
void DestroyRecursively(Node_t* CurrentNode);
void InsertFront(Node_t** InPtrToRootNode, int InData);
void InsertFrontOrderly(Node_t** InPtrToRootNode, int InData);
void InsertRear(Node_t** InPtrToRootNode, int InData);
void Remove(Node_t** InPtrToRootNode, int InData);
void Print(Node_t* RootNode);

int main(void)
{
    Node_t* LinkedList = (Node_t*)malloc(sizeof(Node_t));
    LinkedList->Data = 0;
    LinkedList->NextNode = NULL;

    InsertFront(&LinkedList, 1);
    InsertFront(&LinkedList, 9);

    Print(LinkedList);
    printf("\n\n");

    InsertRear(&LinkedList, 8);
    InsertRear(&LinkedList, 3);
    Print(LinkedList);
    printf("\n\n");

    InsertFrontOrderly(&LinkedList, 4);
    InsertFrontOrderly(&LinkedList, 10);
    Print(LinkedList);
    printf("\n\n");

    InsertRear(&LinkedList, 100);
    InsertRear(&LinkedList, 120);
    Print(LinkedList);
    printf("\n\n");

    Remove(&LinkedList, 4);
    Print(LinkedList);
    printf("\n\n");

    Destroy(LinkedList);

    return 0;
}

void Destroy(Node_t* InRootNode)
{
    printf("Destroy() has been called. -> ");
    DestroyRecursively(InRootNode);
    printf("Close to Destroy.\n\n");
}
void DestroyRecursively(Node_t* CurrentNode)
{
    if (NULL == CurrentNode)
    {
        return;
    }
    DestroyRecursively(CurrentNode->NextNode);
    printf("[%d] has been Deleted. -> ", CurrentNode->Data);
    free(CurrentNode);
}

void InsertFront(Node_t** InPtrToRootNode, int InData)
{
    Node_t* NewNode = (Node_t*)malloc(sizeof(Node_t));
    NewNode->Data = InData;
    NewNode->NextNode = (*InPtrToRootNode)->NextNode;
    (*InPtrToRootNode)->NextNode = NewNode;
}

void InsertFrontOrderly(Node_t** InPtrToRootNode, int InData)
{
    Node_t** CurrentNode = InPtrToRootNode;
    Node_t* NewNode = (Node_t*)malloc(sizeof(Node_t));
    NewNode->Data = InData;

    while (NULL != *CurrentNode)
    {
        if (NewNode->Data <= (*CurrentNode)->Data)
        {
            break;
        }
        CurrentNode = &((*CurrentNode)->NextNode);
        /* *CurrentNode = ((*CurrentNode)->NextNode); 하면 안됨. */
    }
    NewNode->NextNode = *CurrentNode;
    *CurrentNode = NewNode;
    /* pp = &NewNode; 하면 안됨. */
}

void InsertRear(Node_t** InPtrToRootNode, int InData)
{
    Node_t** CurrentNode = InPtrToRootNode;
    Node_t* NewNode = (Node_t*)malloc(sizeof(Node_t));
    NewNode->Data = InData;
    NewNode->NextNode = NULL;

    while (NULL != *CurrentNode)
    {
        CurrentNode = &((*CurrentNode)->NextNode);
    }
    *CurrentNode = NewNode;
}

void Remove(Node_t** InPtrToRootNode, int InData)
{
    Node_t** CurrentNode = InPtrToRootNode;
    while (NULL != *CurrentNode)
    {
        if (InData == (*CurrentNode)->Data)
        {
            Node_t* pTempNode = *CurrentNode;
            *CurrentNode = (*CurrentNode)->NextNode;
            free(pTempNode);
            break;
        }
        CurrentNode = &(*CurrentNode)->NextNode;
    }
}

void Print(Node_t* InRootNode)
{
    Node_t* CurrentNode = InRootNode;
    while (NULL != CurrentNode)
    {
        printf("[%d:%p]->", CurrentNode->Data, (void*)CurrentNode->NextNode);
        CurrentNode = CurrentNode->NextNode;
    }
    printf("[NULL]\n");
}