C언어로 리스트 구현하기

리스트란?

우리가 자료를 정리하는 방법 중 하나이다.

예를 들어, 오늘 해야 할 일을 적는다든가, 버킷 리스트를 적는다든가 등등..

리스트는 항목들이 차례대로 저장되어 있으며, 각각의 항목들은 순서나 위치를 갖는다.

리스트는 배열과 연결리스트를 이용하여 구현할 수 있다.

이번에는 배열로 리스트를 구현 해보겠다.

---

배열로 리스트 구현

배열로 리스트는 구현하면 메모리가 순차적으로 할당된다.

리스트를 구현하기 위해서 어떤 것이 필요한지 알아보자.

 

1. 리스트 정의

2. 리스트 초기화 함수

3. 포화상태 공백상태 검사 함수

4. 특정한 위치에서 값을 얻어내는 함수

5. 끝부분에 추가 / 특정 위치에 추가 함수

6. 삭제함수

7. 출력함수

---

1. 리스트 정의

#include <stdio.h>
#define MAX_LIST 100

typedef int element;
typedef struct {
    element array[MAX_LIST];
    int size;
} ArrayType;

최대 크기는 100으로하고,

size변수는 변수가 들어가있는 실제 사이즈를 의미한다.

(데이터의 개수)

---

2. 리스트 초기화

void init_list(ArrayType *l)
{
    l->size = 0;
}

처음에는 데이터가 들어가 있지 않기때문에,

리스트의 실제크기는 0이된다.

---

3. 포화 상태 / 공백 상태 검사함수

int is_empty(ArrayType *l)
{
    if(l->size == 0)
        return 1; //공백
    else
        return 0;
}

int is_full(ArrayType *l)
{
    if(l->size == MAX_LIST)
        return 1; //포화
    else
        return 0;
}

공백 상태라면, size가 0일 것

포화 상태라면, size가 MAX_LIST가 된다.

---

4. 특정한 위치에서 값을 얻어내는 함수

element get_entry(ArrayType *l, int pos)
{
    if(pos < 0 || pos >= l->size)
        printf("pos error\n");
    else
        return l->array[pos];
}

pos는 특정한 위치이다.(pos는 0부터 시작한다.)

만약 pos가 0보다 작거나 size보다 같거나 크다면, 범위를 초과했기 때문에 오류임!

(만약 size가 10이라면 [0] [1] [2] ... [9] 이렇게 흘러갈 텐데 pos가 10이라면 범위 초과!)

 

문제가 없다면, pos위치에 있는 값을 추출해낸다.

 

---

5. 끝부분에 추가 / 특정 위치에 추가 함수

void insert_last(ArrayType *l, element item)
{
    if(is_full(l) == 1)
        printf("empty\n");
    else{
        l->array[(l->size)++] = item;
    }
}

배열의 현재 위치에 데이터를 넣고,

사이즈를 증가 시킨다.(후위 연산자를 사용한 점 주의하자!)

size가 지금까지 이전에 해왔던 front, rear라고 생각하면 편하다.

 

void insert(ArrayType *l, int pos, element item)
{
    if(!is_full(l) && (pos >= 0) && (pos <= l->size)){
        for(int i = l->size - 1; i >= pos; i--){
            l->array[i + 1] = l->array[i];
        }
        l->array[pos] = item;
        l->size++;
    }
}

이젠 특정한 위치에 삽입해야 하는 경우를 보자.

특정한 위치에 삽입을 하려면,

특정위치부터 모든 요소들을 오른쪽으로 한칸씩 밀어야한다.

그리고 그 위치에 삽입한다.

크기는 1개를 삽입했으니 size++로 증가시켜준다

---

6. 삭제함수

element delete(ArrayType *l, int pos)
{
    element item;

    if(pos < 0 || pos >= l->size)
        printf("pos error\n");
    else{
        item = l->array[pos];
        for(int i = pos; i < l->size - 1; i++){
            l->array[i] = l->array[i + 1];
        }
        l->size--;
        return item;
    }
}

삭제할 때, 삭제할 원소를 미리 저장해둔다.

그리고 모든 요소들을 왼쪽으로 한칸씩 밀면 된다.

크기는 1개를 삭제했으니, size--로 감소시켜준다.

---

7. 출력함수

void print_list(ArrayType *l)
{
    int i;
    for(i = 0; i < l->size; i++){
        printf("%d -> ", l->array[i]);
    }
    printf("\n");
}

---

확인 / 전체코드

#include <stdio.h>
#define MAX_LIST 100

typedef int element;
typedef struct {
    element array[MAX_LIST];
    int size;
} ArrayType;

void init_list(ArrayType *l)
{
    l->size = 0;
}

int is_empty(ArrayType *l)
{
    if(l->size == 0)
        return 1; //공백
    else
        return 0;
}

int is_full(ArrayType *l)
{
    if(l->size == MAX_LIST)
        return 1; //포화
    else
        return 0;
}

element get_entry(ArrayType *l, int pos)
{
    if(pos < 0 || pos >= l->size)
        printf("full or pos error\n");
    else
        return l->array[pos];
}

void insert_last(ArrayType *l, element item)
{
    if(is_full(l) == 1)
        printf("empty\n");
    else{
        l->array[(l->size)++] = item;
    }
}

void insert(ArrayType *l, int pos, element item)
{
    if(!is_full(l) && (pos >= 0) && (pos <= l->size)){
        for(int i = l->size - 1; i >= pos; i--){
            l->array[i + 1] = l->array[i];
        }
        l->array[pos] = item;
        l->size++;
    }
}

element delete(ArrayType *l, int pos)
{
    element item;

    if(pos < 0 || pos >= l->size)
        printf("pos error\n");
    else{
        item = l->array[pos];
        for(int i = pos; i < l->size - 1; i++){
            l->array[i] = l->array[i + 1];
        }
        l->size--;
        return item;
    }
}

void print_list(ArrayType *l)
{
    int i;
    for(i = 0; i < l->size; i++){
        printf("%d -> ", l->array[i]);
    }
    printf("\n");
}

int main(void)
{
    ArrayType l;
    init_list(&l);

    insert_last(&l, 1); //1삽입
    print_list(&l);
    insert_last(&l, 2); //2삽입
    print_list(&l);
    insert_last(&l, 3); //3삽입
    print_list(&l);

    insert(&l, 0, 4); //0번째 위치에 4삽입
    print_list(&l);

    delete(&l, 1); //1번째 위치요소 삭제
    print_list(&l);
    
    return 0;
}

---

주의할 점

스택, 큐, 덱, 리스트를 구현하면서

증감연산자의 사용이 잦다.

스택에서는 top을 증감하고,

큐, 덱 에서는 front와 rear를 증감하고,

리스트에서는 size를 증감한다.

 

증감을 시키고 데이터를 삽입/삭제하는지, 

혹은 데이터를 삽입/삭제하고 증감을 시키는지 정확히 알 필요가 있다.

그래야 후위 증감을 선택할 것인지 전위 증감을 선택할 것인지 나뉘기 때문이다.

헷갈린다면, 직접 그림을 그려서 과정을 살펴보는 것이 좋은 방법일 것이다.