[Data Structure] 선형 리스트(Linear List)

C언어에는 파이썬이나 자바와 달리 list라는 내장된 자료형이 없습니다. 보통 파이썬에서 list를 사용하면 list 내에서의 조작이 굉장히 자유롭습니다. 

예를 들어 뒤에 이어 붙이기, 삭제하기 등이 단 하나의 명령어면 해결이 가능합니다.

 

그러나 C언어에는 list가 존재하지 않습니다. 그래서 위에서 말한 조작이 자유로운 배열의 형태를 직접 만들어주는 게 목적입니다. 

 

● 선형 리스트

c언어에서 구현할 수 있는 리스트에는 여러 종류가 있습니다. 그 중 가장 먼저 생각할 수 있는 것이 선형 리스트입니다.

리스트라는 개념을 생각해보면 항목을 쭉 늘여놓은 목록 같은 개념입니다. 그렇다면 이를 c언어에서 구현한다고 생각했을 때 가장 먼저 생각나는 것이 배열입니다. 

typedef int element;
typedef struct{
    int list[MAX_SIZE];
    int length;
}ArrayListType;

그래서 리스트 구조체의 형태는 위와 같습니다. element 같은 경우에는 전역 변수로 이후에 배열에 입력하거나 삭제시킬 숫자를 의미합니다. 그다음 list라는 이름의 배열을 만들고 배열의 크기는 따로 #define을 하여 설정합니다. 그다음 배열의 크기인 length를 설정합니다. 배열에서 length는 곧 인덱스의 개수를 의미합니다.

그리고 이렇게 생성된 리스트 구조체를 초기화시켜야 합니다.

void init(ArrayListType* L) {
    L->length = 0;
}

위의 리스트 구조체에 대해 초기화를 시켜야하기 때문에 매개변수는 구조체 타입이 들어갑니다. 그다음 배열의 크기를 초기화하여 값이 들어갈 수 있도록 설정합니다.

---

그다음은 만약 리스트에 값을 삽입 혹은 삭제를 할 때 리스트가 가득 차 있거나, 비어있으면 안 되기 때문에 두 가지 상황에서 특정 값을 반환해 주는 함수를 만들어줍니다.

int isFull(ArrayListType* L) {
    return L->length == MAX_SIZE;
}

int isEmpty(ArrayType* L) {
    return L->length == 0;
}

위와 같이 간단히 나오는 이유는 관계연산자의 반환값인 boolean형 값에 따라 true or false가 판별되기 때문입니다.

---

다음은 insert함수입니다.

insert함수부터가 본격적인 시작이라고 할 수 있는데 앞선 함수들을 이용하고, 경우의 수를 아용하여 조건을 만들어 함수를 구성합니다.

int insert(ArrayListType* L, int pos, element x) {
    if(isFull(L))
    	error("List is Full");
    else if(pos < 0 || pos > (L->length))
    	error("Index Error");
    else {
    	for(int i = (L->length-1; i >= pos; i--)
            L->list[i+1] = L->list[i];
        L->list[pos] = x;
        L->length++;
    }
}

먼저 insert의 매개변수로는 입력을 진행해줄 list의 포인터 변수, 현재의 위치를 나타내 줄 pos, 그리고 넣어줄 값인 x가 들어갑니다. 

 

첫 번째는 isFull의 조건식입니다. isFull 함수를 보면 return값이 boolean입니다. 즉, 포화상태이면 true, 아직 자리가 남아있으면 false를 반환하는 것입니다. if-else문도 조건식이 참인지 거짓인지에 따라 문장을 실행하기 때문에 올바른 문법이라고 할 수 있습니다.

※ 참고로 error는 문자열을 받아 그대로 프린트하는 함수입니다.(따로 만들어줌)

 

두 번째는 else if식입니다. else if에는 인덱스 오류에 대한 처리를 했습니다. pos는 내가 현재 element를 넣으려는 위치에 해당하기 때문에 pos가 아예 배열 밖에 위치한다면 마찬가지로 오류라고 알려줘야 할 것입니다.

 

마지막은 else문입니다. else문은 위의 조건식처럼 오류가 발생하지 않은 정상적인 경우를 말합니다. 그렇게 되면 원하는 위치 즉, pos에 값을 넣었을 때 기존에 pos뒤에 있던 값들은 한 칸 씩 뒤로 밀어야 합니다. 그렇다면 먼저 배열의 끝에서 pos의 위치에 해당하는 만큼 반복문을 돌려 배열을 한 칸씩 밀어줘야 합니다. 배열의 끝 인덱스는 length-1이고 현재 위치는 pos이기 때문에 갱신도 i--로 해줍니다. 

굳이 i--로 해주는 이유 + pos의 값을 for문 밖에 넣어주는 이유는 한 칸 씩 미는 메커니즘 때문인데 만약 pos부터 시작해서 끝까지 i++로 간다고 하면 L->list [i+1] = L->list [i]라고 했을 때, 처음 한 번은 되겠지만 두 번째부터는 원래 i+1 인덱스에 pos의 값이 덮어써져 for문이 종료됐을 때 pos부터 뒤로 모든 값이 pos의 값과 같을 것입니다. 

그리고 for문을 종료하고 나면 pos자리에 element를 넣어주고 전체 길이가 1 커졌기 때문에 length도 1 키워줍니다.

---

다음은 delete함수입니다.

delete는 if와 else if까지는 insert와 같지만, else에서의 흐름만 살짝 다릅니다.

element delete(ArrayListType* L, int pos) {
    element item;
    
    if(isFull(L))
    	error("List is Full");
    else if(pos < 0 || pos > (L->length))
    	error("Index Error");
    else {
    	for(int i = pos; i < L->length; i++)
            L->list[i] = L->list[i+1];
        L->length--;
        return item;
    }
}

대체적으로 insert와 비슷하지만 함수의 타입을 element형으로 한 이유는 반환을 리스트의 값인 element로 받기 때문입니다. 

delete에서 중요한 것은 정확히 삭제가 일어나는 것이 아니라는 것입니다. 만약에 malloc을 통해 메모리를 할당한다면 free를 통해 통째로 없애버릴 수 있지만 위에서는 삭제하고자하는 위치인 pos의 element값을 pos+1의 위치에 있는 값으로 덮어쓰기를 해주는 느낌이라고 보시면 됩니다.

---

앞으로 추가적으로 몇 가지 리스트의 종류들이 나오겠지만, 선형 리스트는 명확한 사용처가 존재합니다. 

선형 리스트의 경우에는 리스트의 조작, 삽입과 삭제가 불편하기 때문에 주로 읽기 전용으로 많이 쓰입니다. 배열의 크기가 정해져있고, 순차적으로 하나씩 데이터가 저장되기 때문입니다. 

 

위의 장점을 활용한 대표적인 예시가 다항식과 행렬입니다. 

 

● 다항식(polynomial)

다항식의 경우에는 차수가 높은 항부터 낮은 항까지 차례대로 나타나기 때문에 선형 리스트를 쓰기 좋은 조건이라고 할 수 있습니다.

 

다항식을 구현하는 방법은 두 가지가 있습니다. 

1. 모든 항을 다 구현하는 방법.

2. 계수가 0인 항은 제외하는 방법.

 

예를 들어 10x^5 + x + 2가 있다고 할 때, 중간에 4제곱부터 제곱까지는 비는 공간이기 때문에 배열에는 {10,0,0,0,1,2}가 저장되겠지만, 실제로는 0에 해당하는 공간을 사용하지 않기 때문에 메모리 낭비가 심합니다. 그래도 장점은 계산이 비교적 간단하고 쉽다는 것입니다. 

이를 보완하는 방법은 계수에 해당하는 배열과 차수에 해당하는 배열을 따로 만들어서 인덱스를 동시에 관리하는 방법입니다.

 

● 행렬(matrix)

행렬도 다항식과 비슷합니다. 행렬을 작성하는 방법도 마찬가지로 두 가지입니다.

1. 전체 행렬을 2차원 배열로 작성한다.

2. 0인 부분을 제외하고 작성한다.

 

다항식에서도 대부분의 계수가 0인 경우에는 희소다항식이라고 부르듯 행렬에서도 대부분이 0인 행렬을 희소행렬이라고 부릅니다. 

일단 가장 먼저 생각나는 방법이 2차원 배열이지만, 위와 마찬가지로 메모리 낭비가 심하다는 단점이 있습니다. 

 

희소행렬 표현 방법>

 

1. 0이 아닌 원소만 추출하여 <행번호, 열번호, 원소> 쌍으로 배열에 저장

2. 추출한 순서쌍을 2차원 배열에 행으로 저장

3. 원래의 행렬에 대한 정보(행개수, 열개수, 0이 아닌 원소 수)를 0번 행에 저장

---

지금까지 선형 리스트의 개념과 구현 방법, 그리고 이들의 다양한 활용에 대해 알아봤습니다.