<자료구조> 연결리스트와 노드

 

* 연결리스트 소개

 - 배열에선 각 인덱스 값들이 메모리 상에서 연이어 저장되어있다. 그렇다면 배열에 새로운 값을 추가하려면 어떻게 해야 할까

 

 - 기존 배열 바로 뒤에 다른 값이 있을 수 있으므로 배열의 길이를 늘리려면 새로운 메모리를 할당해서 값을 하나하나 복사하여 옮겨야한다.

 

 - 위의 방식은 너무 번거롭다. 각 값을 메모리의 다른 곳에 저장하더라도 배열처럼 사용할 수 있다면 어떨까. 각 값에 다음 값의 메모리 주소를 기억하게 하는 것이다. 이를 연결리스트라 한다. (Linked List)

 

 - 이제 첫 값인 1은 2의 주소를 갖고, 2는 3의주소를, 3은 Null을 갖게 된다.

 

* 노드

 - 연결리스트를 C언어 코드로 구현하면 다음과 같은 구조체로 정의한다.

 

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

 

 - 컴퓨터 공학에서 node라는 단어는 직사각형으로 나타낼 수 있는 메모리 덩어리를 의미한다.

 

 - 여기에서 노드는 두 가지 값을 저장한다.

 

 - 코드 블럭 안에서 node를 사용하기 위해서 첫줄에도 node를 명시하였다.

 

* 연결리스트 구현

 - 이제 위에서 봤었던 1,2,3 을 코드로 구현해보자.

 

 - 가장 처음에는 아무것도 가리키지 않는 리스트를 생성한다. ( node *list=NULL;)

 

 - 새로운 node를 만들 때에는 node *n = malloc(sizeof(node)); 와 같이 메모리를 할당해야 한다.

 

 - 메모리할당에 문제가 발생할 때를 대비에서 n==NULL 일 때 return1을 하는 조건문을 작성하여 프로그램을 중지시킬 것이다.

 

 - 값을 저장하려면 (*n).number = 1; 과 같이 작성해야 하지만 이 경우에는 간단하게 화살표 표시로 사용할 수 있다. n->number=1; 과 동일하다.

 

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

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

int main(void)
{
    node *list = NULL;
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

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

    list = n; //첫 번째 node를 정의 햇으므로 list포인터를 n포인터로 바꾼다.

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

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

    list->next = n;

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

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

    list->next->next = n;

    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }

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

 

 - 1을 넣고나서는 다시 n에 새로 메모리를 할당하여 같은 작업을 반복한다. 이 때에는 list→next에 n을 할당한다. 3에서는 list→next→next에 n을 할당하였다.

 

 - 출력을 할 때에는 list에 연결된 node를 처음부터 확인하며 number을 출력한다. list에 영향이 없도록 임의의 tmp node를 list라고 칭하였다

 

 - 마지막에는 메모리를 해제하기 위해서 위와 비슷한 반복문을 시행한다.

 

 - 위와 같은 연결리스트에서 중간에 값을 삽입한다고 가정하자. 1→2→9→3 이되려면 어떻게 해야할까.

 

 - 만약 2 노드가 먼저 9를 가리키게 한다면 3은 메모리에서 길을 잃어 버리고 쓰레기값이 되어 버린다. 따라서 9노드에 먼저 3의 주소를 넣고 2가 9를 가리키게 해야한다.

 

 

---

 

 

참고

 

 

 이 글은 하버드 대학교 David Malan 교수의 CS50 강의를 수강 후 정리하며 쓴 글입니다. 코드는 C언어로 작성되었으며, 개발환경은 CS50 IDE에 최적화되어 있습니다. 일부 라이브러리는 다른 환경에서 별도의 설정이 필요할 수 있습니다.

 

 

 

CS50 공식사이트

CS50

 

부스트코스

다 함께 배우고 성장하는 부스트코스

 

CS50 IDE

CS50 IDE