연결리스트 구현하기

자료구조를 공부해본 사람은 누구나 연결리스트가 뭔지 알 것이다. 이를 복습차, 코드로 다시 구현해보자.

1. 노드 정의

먼저 연결리스트의 각 노드의 구조체를 정의해보자. 이는 교과서 처럼 다음과 같다.

struct _node{
    int key;
    struct _node *next;
} note_t;
typedef struct _node node_t;

• 여기서는 int 라고 했는데, int 가 아니여도 좋다.

• 저 구조체 안에 추가적으로 넣고 싶은 변수를 더 넣어도 된다.

• next 라는 포인터를 통해 다음 노드와 연결된다.

2. 노드 삽입

연결리스트에 노드를 삽입한다는 것은 일반적으로 리스트 끝 노드에 노드를 추가하는 것이다.

연결리스트는 또한 일반적으로 리스트 앞부분을 가리키는 포인터인 head와 끝을 가리키는 포인터인 tail을 함께 가진다.

코드를 보자.

node_t *head = NULL, *tail = NULL;
​
void insert_node(int n){
    node_t *new_node = (node_t *)malloc(sizeof(node_t));
    new_node->key;
    new_node->next = NULL;
}

• 연결리스트란, 노드를 필요할 때마다 생산하여 관리하는 것이다. 이는 배열과 다르게 메모리를 절약할 수 있는 장점이다. 따라서 malloc으로 동적할당 해준다.

여기까지만 하면, 노드의 key 에 프로그래머가 저장하고 싶은걸 인자로 받아 저장할 수 있다. 여기서는 int형인데 상황에 따라 다른 자료형을 쓰면 된다.

이제 만들어진 노드를 연결리스트에 연결해보자.

연결리스트는 일반적으로 head와 tail이 사용된다고 했다. 연결리스트에 연결할 때, 저 두개를 염두해보자. 그러면 연결리스트가 비어있는 경우와, 비어있지 않은 경우, head와 tail의 처리과정이 다를 것임을 알 수 있다.

node_t *head = NULL, *tail = NULL;
​
void insert_node(int n){
    node_t *new_node = (node_t *)malloc(sizeof(node_t));
    new_node->key;
    new_node->next = NULL;
    
    if( head == NULL ){
        head = new_node;
        tail = new_node;
    }else{
        tail->next = new_node;
        tail = new_node;
    }
}

이게 이해가 되지 않는다면, 하나씩 손으로 구현해가면서 이해해보자. 펜을 들고 노트에 하나씩 그려봐야 이해가 되는 경우도 있고, 따라 코드를 치다보면 이해가 되는 경우도 있으니깐.

또한, 이는 교과서와도 같은 정의이므로 내용과 코드 모두 숙지하는 것이 좋다.

3. 연결리스트 출력하기

연결리스트 출력은 연결된 노드들을 순차적으로 출력하는 것이다.

두가지 방식이 있다. 반복문과 재귀이다.

• 반복문

void print_list(node *from){
    node *node;
    
    node = from;
    while (node != NULL){
        printf("%d ", node->key);
        node = node->next;
    }
}

코드를 보면 알겠지만, 지역 변수 node 라는 포인터가 from 이라는 node 부터 가르키기 시작해서 연결된 노드를 쭉 printf 를 이용하여 출력하는 것이다.

연결리스트의 처음부터 출력하고 싶다면, 다음과 같이 호출하면 된다.

int main(){
    ...
    print_list(head);
}

• 재귀

void print_list2(node_t *from){
    if (from == NULL)
        return ;
    printf("%d ", from-key);
    print_list2(from->next);
}

노드의 key값을 먼저 출력해주고, 그 다음 node를 함수의 인자로 보내주는 방식이다. 심플하다.

재귀를 이용하면 연결리스트를 역순으로 출력할 수도 있는데, 코드는 다음과 같다.

void print_list2(node_t *from){
    if (from == NULL)
        return ;
    print_list2(from->next);
    printf("%d ", from->key);
}

딱 2줄 바뀌었다. key 값을 먼저 출력하는 것이 아니라, 재귀적으로 함수를 먼저 호출한 뒤 key 값을 출력한다. 이렇게 하면, 함수 호출이 탈출조건에 도달하여 더이상의 호출이 끝나고, 다시 함수들이 리턴되면서 각 노드의 key 값을 출력할 것이다.

이 역시 교과서적인 내용이므로 모두 숙지해야 좋을 것 같다.