[CS50] 6.4 연결 리스트: 코딩

연결 리스트는 다음과 같이 구현할 수 있다.

 

 

1. 구조체 정의

typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(void)
{
    node *list = NULL;

node 구조체를 정의하고

정수형 값이 저장되는 number,

다음 node의 주소를 가리키는 포인터 next를 지정한다.

 

node 포인터 list를 정의한다. node를 가리키게 될 포인터이다.

list는 아직 어디도 가리키지 않고 있기 때문에 NULL로 초기화한다.

 

 

 

2. node 생성과 주소 연결

node *n = malloc(sizeof(node));
if (n == NULL)
{
   return 1;
}

n->number = 1;
n->next = NULL;

먼저, 새로운 node를 생성하기 위해 메모리를 할당하고 이 node 안을 가리키는 포인터 n을 선언한다.

다음, n→number = 1로 node의 값을 저장한다. 이 코드의 의미는 (*n).number와 같다.

포인터 n 앞에 *를 붙여 실제 값으로 가라고 한 후, number 속성에 1을 저장하라는 의미를

간단히 ->(화살표)로 나타낸다.

 

next도 n→next = NULL로 포인터가 가리키는 곳 안으로 와서 NULL을 저장한다.

아직 다음에 가리킬 노드가 정해지지 않았기 때문이다.

 

이제 node를 만들었으니 list가 node를 가리키도록 해야한다.

아래와 같이 포인터 list가 포인터 n이 가리키는 곳과 같은 곳을 가리키도록 해준다.

마침내 list는 1번 node를 가리킬 수 있게 된다!!

list = n;

 

이제 2번 노드를 생성한다.

포인터 n은 이제 2번 노드를 가리키게 되며,

이 노드의 number, next에 각각 2와 NULL로 초기화해준다.

여기서도 next가 NULL인 이유는 가리킬 노드가 정해지지 않았기 때문이다.

n = malloc(sizeof(node));
if (n == NULL)
{
   return 1;
}

n->number = 2;
n->next = NULL;

 

2번 노드가 생성되었으므로 1번노드의 next 속성값은 2번 노드의 주소가 된다.

포인터 list는 1번 노드를 가리키고 있고 1번 노드의 next로 가서

현재 2번 노드를 가리키고 있는 포인터 n의 값을 저장한다.

(1번 노드의 next에 2번 노드의 주소 저장)

list->next = n;

 

3번 노드가 만들어 졌다면 다음과 같이 접근할 수 있겠다.

1번 노드를 가리키는 list가 1번의 next에 접근해서 2번 노드로 이동.

2번 노드의 next에 현재 3번 노드의 주소를 가진 포인터 n의 값을 저장.

list->next->next = n;

 

 

 

 

 

 

 

 

출처: www.boostcourse.org/cs112