C Data Structure - 단순 배열 리스트

공부하고 나면 그 때 그 때 정리해야한다는 것을 뼈저리게 느끼는 시작이다..

이번에 정리할 내용은 단순 배열 리스트이다. 다만, 그냥 배열을 쫘르륵 순회하고, 삭제 띡 하고, 추가하고 그러면 일반 배열 사용법을 정리하는 것과 다를 바가 없으므로, 약간 형식이 있는 리스트 틱한 배열로 만들어 정리한다ㅋㅋ

일단은 정의와 특징, 장 단점을 간단하게 상기시키며 넘어가도록 하겠다.

단순 배열 리스트란?

말 그대로 단순한 배열이다. 그런데 리스트라는 자료구조 형태이므로 메모리 공간 뿐만 아니라 삽입, 삭제, 탐색에 대한 함수를 추가 보완함으로써 하나의 자료 구조로 완성을 시킬 셈이다.

배열

배열 리스트의 장점

Random Access, 임의 접근이 인덱스를 기반으로 가능하기 때문에 데이터의 참조가 쉽다.  O(1) <- 개쩐다ㄷㄷ

배열 리스트의 단점

배열의 길이가 초기에 결정되며, 이 길이는 변경이 불가능하다.
삭제 과정에서 데이터의 이동이 매우 많이 일어난다.
탐색할 경우 최악의 경우에는 O(n)이다. <- 매우 성능이 나오지 않는 것이다. 데이터의 수에 매우 정비례하여 시간이 늘어나기 때문이다.

코드 구현 및 실행

---

#include <stdio.h>
#define MAX_LIST_SIZE 20
 
struct List
{
    int insert_index;
    int search_index;
    int arr[MAX_LIST_SIZE];
};
 
void ListInit(struct List* list)
{
    int i = 0;
    list->insert_index = 0; // 값을 추가할 때 사용하는 인덱스 -> 모든 값은 0 ~ (insert_index-1) 까지만 유효함!
    list->search_index = 0; // 탐색을 위한 순회 시 사용하는 인덱스
 
    // 모두 0으로 초기화
    for (i = 0; i < MAX_LIST_SIZE; i++)
        list->arr[i] = 0;
    return;
}
void LInsert(struct List* list, int value)
{
    if (list->insert_index >= MAX_LIST_SIZE) 
    {
        printf("저장이 불가능합니다.\n");
        return;
    }
    list->arr[list->insert_index++] = value;
    return;
}
int LCount(struct List* list) // 현재 추가된 수
{
    return list->insert_index;
}
 
int LFirst(struct List* list, int* data) // 첫 번째 요소에 인덱스를 위치시키는 역할이라고 보면 된다.
{
    if (list->insert_index >= 1) // 한 번이라도 값이 추가된 적이 있는 경우에만 사용.
    {
        list->search_index = 0;
        *data = list->arr[list->search_index];
        return 1;
    }
    // search_index를 증가시키지 않는다. 필요하다면 증가를 미리 시키고 접근해야함.
    return 0;
}
int LNext(struct List* list, int* data) // LFirst 함수에 이어 바로 다음 요소에 인덱스를 위치시키는 역할이라고 보면 된다.
{
    if ((list->search_index + 1) < list->insert_index) // 접근해야하는 인덱스(search_index+1)가 유효한 인덱스 범위 내에 존재한다면
    {
        *data = list->arr[++(list->search_index)];
        return 1;
    }
    return 0;
}
void LRemove(struct List* list) // 현재 위치한 인덱스의 값을 제거하고, 빈 요소 자리를 채우는 작업까지 진행한다.
{
    int target = 0;
 
    for (target = list->search_index; target < (list->insert_index - 1); target++) // 유효 인덱스의 바로 전 인덱스까지만 가서 땡겨오면 끝.
        list->arr[target] = list->arr[target + 1];
    list->search_index--;
    list->insert_index--;
 
    printf("\n");
 
    return;
}
 
int main(void)
{
    struct List list;
    int data;
    ListInit(&list);
 
    LInsert(&list, 11);
    LInsert(&list, 11);
    LInsert(&list, 22);
    LInsert(&list, 22);
    LInsert(&list, 33);
 
 
    if (LFirst(&list, &data))
    {
        printf("%d ", data);
        while (LNext(&list, &data))
            printf("%d ", data);
    }
 
    if (LFirst(&list, &data))
    {
        if (data == 22)
            LRemove(&list);
        while (LNext(&list, &data))
        {
            if (data == 22)
                LRemove(&list);
        }
    }
 
    if (LFirst(&list, &data))
    {
        printf("%d ", data);
        while (LNext(&list, &data))
            printf("%d ", data);
    }
 
    printf("\n\n");
    return 0;
}

---