연결 리스트의 형태, 연결 리스트 C로 구현해보기

1. 연결 리스트의 장점

 

일반적으로 배열을 사용하여 데이터를 순차적으로 저장하고, 나열할 수 있다. 하지만 배열을 사용하는 경우, 메모리 공간이 불필요하게 낭비될 수 있다. 연결 리스트를 활용하여 이를 개선할 수 있다. 다음은 연결 리스트가 아닌, 일반적인 배열을 사용하여 특정 원소를 배열의 첫자리에 추가하는 소스다.

 

#include <stdio.h>
#define INF 10000

int arr[INF];
int count = 0;

void addBack(int data) {
    arr[count] = data;
    count++;
}

void addFirst(int data) {
    for (int i = count; i >= 1; i--)
    {
        arr[i] = arr[i - 1];
    }
    arr[0] = data;
    count++;
}

void show() {
    for (int i = 0; i < count; i++)
    {
        printf("%d", arr[i]);
    }
    
}

int main(void) 
{ 
    addFirst(4);
    addFirst(5);
    addFirst(1);
    addBack(7);
    addBack(6);
    addBack(8);
    show();
}

1 5 4 7 6 8

 

먼저 INF라고 해서 메모리 공간이 무한정 존재한다고 가정한다. 처음에 count에 배열의 원소가 몇 개나 있는지 담도록 한다. addBack 함수는 특정한 숫자를 배열의 뒷부분에 담는다. addFirst는 반대로, 특정한 숫자를 배열의 앞부분에 추가한다. 

 

3, 4, 7이 차례대로 있는 상황이면, 가장 앞쪽에 6이라는 숫자를 넣으려면 3, 4, 7이 한 칸씩 뒤로 물러나야 한다. 그래서 addFirst 함수에서 for문으로 가장 뒤쪽의 원소부터 차례로 앞 숫자까지 돌아가면서 옮겨주는 것이다.  

 

void deleteElement(int index) {
    for (int i = index; i < count; i++)
    {
        arr[i] = arr[i + 1];
    }
}

 

index가 주어졌을 때, index 위치 이후부터의 원소는 주어진 인덱스 자리에 바로 다음 인덱스의 값을 덮어쓰는 방식으로 구현할 수 있다. 

 

이렇게 배열 기반의 리스트를 만들면 특정한 위치의 원소에 즉시 접근할 수 있다는 장점이 있다. 하지만 데이터가 들어갈 공간을 미리 메모리에 할당해야 하기 때문에, 원하는 위치로의 삽입이나 삭제가 비효율적이라는 단점이 있다. 위에 구현한 코드에서도 특정한 값을 넣거나 삭제하려면 배열의 값을 해당 자리를 기준으로 하나씩 모두 옮겨서 문제를 해결하고 있다. 특정한 인덱스에 바로 참조해야 할 때가 있다면 배열을 이용하는 것이 효율적이지만, 삽입과 삭제가 많은 경우에는 연결 리스트가 효율적이다. 

 

2. 연결 리스트 구현해보기

 

그렇다면 구조체와 포인터를 함께 사용하여 구현하는 연결 리스트에 대해 알아보자. 연결 리스트는 리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있어야 한다. 필요할 때마다 메모리 공간을 할당받는 동적 메모리 할당을 한다. 연결 리스트는 삽입과 삭제가 배열에 비해 간단하다. 하지만 배열과 다르게 특정 인텍스로 즉시 접근 못하고 원소를 차례로 검색해야 한다. 또 추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비된다. 

 

(1) 단일 연결 리스트

 

기본적인 단일 연결 리스트 구조체

 

단일 연결 리스트는 하나의 구조체 안에 두 개의 변수가 들어가도록 만든다. data는 데이터를 담는 변수고, next는 다음 노드, 또는 다른 구조체를 단방향으로 가리키는 포인터 변수를 넣어 준다. 일반적으로 연결 리스트의 시작 노드를 헤드(Head)라고 하며 별도로 관리한다. 반대로 끝에 있는 노드는 다음 노드가 없으므로 next 값으로 NULL을 넣는다. 

 

연결 리스트 구조체

 

그럼 이제 위의 구조를 그대로 코드를 옮겨보자.

 

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int data;
    struct Node *next;
} Node;

Node *head; 

int main(void) 
{
    head = (Node*) malloc(sizeof(Node));
    
    Node *node1 = (Node*) malloc(sizeof(Node));
    node1 -> data = 1;
    Node *node2 = (Node*) malloc(sizeof(Node));
    node2 -> data = 2;

    head -> next = node1;
    node1 -> next = node2;
    node2 -> next = NULL;

    Node *cur = head -> next;

    while (cur != NULL)
    {
        printf("%d ", cur -> data);
        cur = cur -> next;
    } 
}

 

동적할당을 사용하므로 먼저 stdlib 헤더를 추가해 주었다. 그리고 정수형 data와 그다음 노드를 가리키는 *next라는 포인터 변수로 구성된 구조체를 만들어서 이름을 Node라고 설정했다. 그리고 일반적으로 연결 리스트는 *head로부터 출발을 하기 때문에 *head라는 이름의 변수를 만들어주는 것이다. 또한 Node는 항상 동적 할당을 위해 포인터 변수로 만들어주는 것이 일반적이다. 필요한 만큼만 메모리 할당을 해 주겠다고 컴퓨터에게 이야기해주는 것이다.

 

    head = (Node*) malloc(sizeof(Node));
    
    Node *node1 = (Node*) malloc(sizeof(Node));
    node1 -> data = 1;
    Node *node2 = (Node*) malloc(sizeof(Node));
    node2 -> data = 2;

head에 malloc()을 이용해서 구조체 노드만큼의 메모리만 할당을 받고, 이어서 첫 번째, 두 번째 노드를 만들어주는 코드다. head와 마찬가지로 하나의 노드만 들어가도록 메모리 할당을 해 준다. 그리고 첫 번째 노드인 node1의 데이터는 1을 넣어 주고, 두 번째 노드인 node2의 데이터에는 2를 넣어준다. 

 

    head -> next = node1;
    node1 -> next = node2;
    node2 -> next = NULL;

그리고 next를 이용해 노드를 연결해주는 것이다. head에서 node1으로, node1에서 node2로 이어주고, node2는 마지막 노드라서 NULL값을 가진다. 항상 끝 노드는 NULL 값을 가져야 한다. 

 

    Node *cur = head -> next;
    while (cur != NULL)
    {
        printf("%d ", cur -> data);
        cur = cur -> next;
    }

이제 하나의 포인터 변수인 *cur을 만들어서 head에 next를 가리키도록 하여 while문에서 전체 원소의 값을 출력할 수 있도록 한다. 하나씩 뒤에 있는 원소를 포인터 값으로 가지게 해서 바로 뒤에 있는 노드로 이동하는 방식으로 출력이 된다.

 

1 2

차례로 연결 리스트에 담겨 있는 원소가 출력이 된다. 이제 하나씩 함수로 빼서 연결 리스트를 완성해볼 것이다.

 

(2) 연결 리스트 삽입하는 함수 만들어보기

 

연결 리스트에 새 원소 삽입하는 방법

 

연결 리스트에 특정한 원소를 첫번째 위치에 삽입하려면, 먼저 head 노드의 next가 1을 가리키니까 그 값을 새로운 노드도 동일하게 가리키도록 한다. 그러고 나서 head의 next를 삽입할 노드의 data 값을 가리키도록 한다. 

 

그럼 이런 원리로 연결 리스트의 첫번째 위치에 원소를 삽입하는 함수를 만들 수 있다.

 

void addFront(int a, Node *root) {
    Node *temp = (Node*) malloc(sizeof(Node));
    
    temp -> data = a;
    temp -> next = root -> next;
    root -> next = temp;
}

int main(void) 
{
	//...
    addFront(4, head);
	//...
}

4 1 2

먼저 Node 구조체인 *temp라는 포인터 변수를 만들어서 동적 메모리 할당을 해준다. 그리고 차례로 temp의 데이터는 넘겨받은 a 값으로 넣고, temp의 next는 root의 next에 해당하는 노드를 가리키고, 마지막으로 root의 next는 삽입하는 temp를 가리키도록 한다. 

 

(3) 연결 리스트 삭제하는 함수 만들기

 

연결 리스트의 원소 삭제하는 원리

 

위 연결 리스트에서 노드 1을 삭제하려면, head의 next를 두 번째 노드의 데이터를 가리키도록 한 후, 삭제하고 싶은 노드의 데이터를 메모리 해제해주면 된다. 

 

void removeNode(Node *root) {
    Node *temp = root -> next;
    root -> next = temp -> next;
    free(temp);
}

int main(void) 
{
    // ...
    addFront(4, head);
    removeNode(node1);
    // ...
}

4 1

삭제하고 싶은 노드의 이전 노드를 인자로 받아, 그 노드가 다음다음 노드를 가리키게 하면 끝난다. 

 

(4) 연결 리스트 메모리 해제하는 함수 만들기

 

기본적으로 연결 리스트는 원소를 한 개씩 거쳐가면서 살펴볼 수 있기 때문에 리스트 메모리를 해제할 때도 가리키는 다음 원소 한 개씩 접근해서 해제해 준다. 

void freeAll(Node *root) {
    Node *cur = head -> next;

    while (cur != NULL)
    {
        Node *next = cur -> next;
        free(cur);
        cur = next;
    }
}

 

먼저 Node 타입의 cur 포인터를 head가 가리키는 노드를 가리키도록 한다. 그리고 while문에서 원소를 한 개씩 순회하면서 지금 원소의 메모리를 해제해 주고, 다음 원소가 NULL일 때까지 다음 원소를 가리키도록 해 주면 된다.

 

(5) 연결 리스트 전체 출력 함수 만들기

 

앞서 보았듯 현재 노드가 NULL이 아닐 동안, 노드의 data를 출력해주는 코드다.

void printAll(Node *root) {
    Node *cur = root -> next;

    while (cur != NULL)
    {
        printf("%d ", cur -> data);
        cur = cur -> next;
    } 
}

 

(6) 완성된 연결 리스트 사용하기

 

int main(void) 
{
    head = (Node*) malloc(sizeof(Node));
    head -> next = NULL;

    addFront(2, head);
    addFront(1, head);
    addFront(4, head);
    addFront(5, head);
    addFront(9, head);
    removeNode(head);
    printAll(head);
    freeAll(head); 
}

5 4 1 2

바라는 대로 나온다. 기본적으로 head의 next는 NULL값을 가져야 한다. 초기 상태에는 아무것도 없기 때문이다. 연결 리스트 앞쪽에 숫자를 넣고, 맨 앞의 노드를 지운 다음에 프린트한 대로 메모리 해제를 해 주는 것이다.

 

참고로 위 소스코드에 덧붙여서, 삽입 및 삭제 기능에서의 예외 상황을 처리할 필요가 있다. 삭제할 원소가 없는데 삭제하는 경우 "삭제할 원소가 없습니다", head 노드 자체를 잘못 넣은 경우 등을 체크해야 한다.