[리스트] 리스트구조 - 배열로 구성된 리스트

리스트 - 배열로 구성된 리스트

l 리스트 (list) : 항목들을 차례대로 나열하여 정리할 때 사용하는 자료구조

(ex) 리스트의 예

• 한 주일의 요일들 (일요일, 월요일, ... , 토요일)
• 한글 자음의 모음들 (ㄱ, ㄴ, ㄷ, ..., ㅎ)
• 가드 한 벌의 값 (Ace, 2, 3, ..., King)

 

리스트를 구현하는 방법으로는

1. 배열을 이용해 구현하는 방법

2. 포인터를 이용하여 연결 리스트를 만드는 방법

위 2가지가 있다.

먼저 배열로 구현한 리스트를 볼 것이다.

배열은 같은 형의 변수를 여러 개 만드는 경우에 사용되며, 항목을 저장할 수 있는 여러 개의 공간을 가진다.

이 공간들엔 인덱스 번호가 주어지고, 이 번호를 통해 접근할 수 있다.

위 그림의 배열은 7개의 상자가 있는데 저장된 항목들은 6개 (A~F)이다. 이 때 남은 1개의 상자의 공간을 낭비한다.

이것이 배열의 약점이다.

우선 배열리스트를 C언어로 어떻게 구현하는지 이와 관련된 함수들을 살펴보자.

#include <stdio.h>
 
#pragma warning(disable : 4996)
#define SIZE 100
 
//// 타입정의 -> int형을 element로 정의 ////
//// 타입 변경할 때 편하게 하기위해 ////
typedef int element;
 
typedef struct {
    element list[SIZE];            //배열
    int length;                    //현재 배열에 저장된 데이터 개수
}ArrayListType;
 
//// 배열 초기화
void init(ArrayListType *L)
{
    L->length = 0;
}
////배열이 비어있는지 확인할 함수
////비어있으면 1, 그렇지 않으면 0 반환
int is_empty(ArrayListType *L)
{
    return L->length == 0;
}
//리스트가 가득 차있으면 1, 그렇지 않으면 0 반환
int is_full(ArrayListType *L)
{
    return L->length == SIZE;
}
//리스트 데이터 출력
void display(ArrayListType *L)
{
    for (int i = 0; i < L->length; i++)
        printf("%d ", L->list[i]);
    printf("\n");
}

이와 같이 구조체로 처리할 데이터들을 묶어 구조체 포인터를 이용해 구조체 내 데이터 값들을 처리하는

방식은 이 다음에 나올 많은 자료구조에서도 쓰이는 방식이니 빨리 적응하는 게 정신에 이롭다ㅎㅎ

그럼 배열리스트에 하나의 값을 임의의 장소에 삽입한다고 가정해보자.

위 그림에서는 인덱스번호: 4에 새로운 값 N을 삽입한 것을 생각해보았다. 

이런 상황에는 항목이 1개 더 증가하는 것이므로 원래 인덱스 4에 있던 E와 그 뒤에 있던 F는

1칸씩 뒤로 밀려 이동하게 된다.

그럼 배열리스트 삽입을 C언어로 구현해보자

// position : 삽입하고자 하는 위치 (인덱스값)
// item : 배열에 삽입할 데이터값
void AddInArrayList(ArrayListType *L, int position, element item)
{
    //배열이 가득 차있는지와 삽입할 인덱스 값 유효성 검사
    if (!is_full(L) && (position >= 0) && (position <= L->length))
    {
        int i;
        // for문으로 삽입하고자하는 위치와 그 뒤의 항목들을 1칸씩 뒤로(index+1) 이동시킴
        // i = 제일 끝에 있는 항목의 인덱스값;
        for (i = (L->length - 1); i >= position; i--)
            L->list[i + 1] = L->list[i];
 
        L->list[position] = item;
        //중요! 항목이 1개 늘었으니 length값 1증가
        L->length++;
    }
}

역시 중요하게 눈여겨볼 것은 for문에서 i값을 어떻게 처리하는가, 그리고 삽입 이후에 L->length 값 1 증가시키기

인 것 같다.

위의 배열리스트 삽입 그림과 코드를 같이 보며 삽입할 때 데이터들의 이동 등을 이해하면 쉽게 느껴질 것이다.

사진에서 N이 코드에서 item 이 되는 것이고, 삽입하고자 하는 위치 4가 position이 되는 것이다.

for문은 그림 (b), (c)처럼 움직이도록 하려면 어떻게 처리해야할까 이해하면 된다.

다음으로 배열리스트에서 삭제를 알아볼 것이다.

삭제는 삽입의 역순으로 행하면 된다. 즉, 임의의 인덱스위치에서 항목을 삭제하고, 삭제한 인덱스 뒤의 항목들을

앞으로 1칸씩 이동시키면 된다.

말로는 설명이 어려울 수 있으니 그림으로 보면

그림과 같이 배열리스트의 삭제 코드를 보도록 하자

// element타입인 이유는 삭제한 값을 반환시킬 때 이렇게 함수타입을 설정한다.
// position 삭제를 하고자 하는 위치(인덱스값)
element DelArrayList(ArrayListType *L, int position)
{
    int i;
    element item;        //삭제한 값을 담을 변수
    // position 값이 올바르면
    if ((position >= 0) && (position <= L->length - 1))
    {
        item = L->list[position];
 
        // i의 범위는 (position <= i <= length - 1)
        // 삭제한 인덱스의 뒤에 있던 항목들 앞으로 1칸씩 이동
        for (i = position; i < L->length; i++)
            L->list[i] = L->list[i + 1];
 
        // 삭제를 해서 항목이 1 감소했으니 length값 1 감소
        L->length--;
        return item;
    }
}

이 역시 그림과 코드를 함께 보면서 이해하도록 해보자

그림에서 인덱스가 3인 항목 N을 삭제를 한다. 즉 position = 3 으로 생각해서 생각해 보도록 하자

또 for문에서 i의 범위, 값의 이동이나 삭제연산을 마친 후 L->length--; 로 배열 항목개수를 감소시키는 것도 

중요하니 눈여겨보도록 하자.

이렇게 리스트에서도 배열리스트를 알아보았다. 다음엔 연결리스트를 공부하도록 하겠다

(연결리스트부터는 내용을 얼마나 잘 이해하느냐가 중요하다... 아무래도 포인터를 많이 다루다보니

 이해가 빡셀 수 있다.)