[CS50] 연결리스트 : 코딩

지난 포스팅에서 연결 리스트의 정의와 리스트의 기본 단위가 되는 구조체를 정의하는 방법에 대해 공부했습니다. 오늘은 이 구조체를 이용해 실제로 연결 리스트를 구현하고 사용해보도록 하겠습니다.

 

실제로 그림과 같이 리스트에 숫자 2가 저장되어있다고 할때

그림과 같이 숫자 4를 추가하려면 어떻게 해야 할까요?

코드로 작성해보면

node *n = malloc(sizeof(node));
if (n != NULL)
{
	n->number = 4;
    n->next = NULL;
}

이런 식으로 작성해서 4를 넣기 위한 새로운 node를 할당받아야 합니다. 하지만 이렇게 node를 만들기만 한다고 끝나는 것이 아니라 화살표도 연결해줘야 list와 연결된 숫자임을 알 수 있습니다. 어떻게 화살표를 추가해야 할까요?

여기서 만약 list가 4를 가리키도록 화살표를 줘버리면 숫자 2가 버려 지기 때문에 바로 4로 화살표를 줘서는 안 됩니다.

그래서 2의 포인터가 4를 가리키도록 하게 만들어주는 것입니다.

이렇게 만들어주는 코드는

node *tmp = list;
while(tmp->next !=NULL)
{
	tmp = tmp->next;
}

입니다. 

tmp라는 새로운 node를 만들어 list와 같은 방향인 2를 향하게 하고 만약 2의 next가 NULL이 아니라면 NULL이 나올 때까지(즉 끝까지) 그다음 next를 찾아가게끔 만들어 줍니다. 마지막으로 NULL인 끝을 찾았다면 거기에 4를 가리키도록 만들어주면 됩니다.

 

 

그럼 위에서 본 내용을 코드를 작성해보겠습니다. 주석을 잘 따라와 주세요!

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

//지난 시간에 포스팅한 node 구조체 정의
typedef struct node
{
	int number;
    struct node *next;
}
node;


int main(void)
{
//list라는 이름의 node 포인터를 정의함과 동시에 NULL로 초기화 시켜줌
	node *list = NULL;
    
    //node에 메모리를 할당하고 포인터 *n으로 가리킴
    node *n = malloc(sizeof(node));
    if(n == NULL)
    {
    	return 1;
    }
    
    //(*n).number = 1;와 동일한 의미
    //node의 number 필드를 의미함
    n->number = 1;
    n->next = NULL;
    
    //첫번째 node를 정의했으므로 16줄의 *list를 *n으로 바꿔줌
    list = n;
    
    //list에 다른 node를 더 연결하기 위해 n에 새로운 메모리 할당
    n = malloc(sizeof(node));
    if(n == NULL)
    {
    	return 1;
    }
    
    n->number = 2;
    n->next = NULL;
    
    //list가 가리키는 첫번째 node의 다음 node를 n으로 지정
    list->next = n;
    
     n = malloc(sizeof(node));
    if(n == NULL)
    {
    	return 1;
    }
    
    n->number = 3;
    n->next = NULL;
    
    //list가 두번째 node와 연결된 첫번째 node를 가리키고
    //세번째 node를 연결하기 위해 두번째 node의 next를 n으로 지정
    list->next->next = n;
    
    for(node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
    	printf("%i\n", tmp->number);
    }
    
    //마지막으로 메모리 해제를 위해 list에 연결된 node를 처음부터 free해줌
    while(list != NULL)
    {
    	node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.