C언어 7 - 2 | 링크드 리스트 기초 (Linked List)

링크드 리스트는 자료구조의 한 형태로 알고리즘에서 다루어야 할 주제이지만 대부분의 C교재는 기본적인 사항을 다룬다.

 

이것도 좋은 자료를 많이 확보해야 하는데 영문 자료에 좋은 자료가 많다. 시간이 되면 알고리즘에 관한 자료들을 더 수집해야 겠다.

 

링크드 리스트는 연결 리스트라고 한다. 배열과 비교가 되곤 하는데 체인처럼 데이터간의 연결이 되어 있다. 하나의 데이터는 데이터와 다음연결방향의 위치(메모리 주소)값을 가지고 있다. C언어에서는 구조체 타입으로 정의한다.

 

구조체는 클래스의 전신 정도로 볼 수 있다. 어찌보면 사용법이 비슷한 부분이 있다. 구조체에 객체 지향 개념을 입혀서 클래스 개념을 만들어도 될 것 같이 설계해놨다.

 

구조체는 다른 종류의 데이터를 묶는 것이다. typedef 키워드와 같이 사용하면 타입의 글자를 줄일 수 있다. 이 예제에서는 struct node를 NODE 로 줄였다.

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

typedef struct node
{
    int number;
    struct node *next_n;
}NODE;

void main(){

    printf("the size of NODE : %d\n",sizeof(NODE));
    NODE *head = (NODE *) malloc(sizeof(NODE));
    
    NODE *node1 = (NODE *) malloc(sizeof(NODE));
    NODE *node2 = (NODE *) malloc(sizeof(NODE));
    NODE *node3 = (NODE *) malloc(sizeof(NODE));
    NODE *node4 = (NODE *) malloc(sizeof(NODE));
    NODE *node5 = (NODE *) malloc(sizeof(NODE));

    head->number = 0;
    head->next_n = node1;
    node1->number = 15;
    node1->next_n = node2;
    node2->number = 30;
    node2->next_n =node3;
    node3->number = 45;
    node3->next_n = node4;
    node4->number = 60;
    node4->next_n = node5;
    node5->number = 75;
    node5->next_n = NULL;
    
    NODE *cur = head->next_n;

    while(cur != NULL)
    {
        printf("value : %d  address : 0x%08X\n",cur->number,cur);
        cur = cur->next_n;
    }
    free(node5); 
    free(node4); 
    free(node3); 
    free(node2); 
    free(node1); 
    free(head); 
    printf("All done and done!");
}

링크드리스트는 애초에 포인터를 사용해서 운영하려고 만든 구조체이다. 동적 메모리를 할당하는 것은 배열과 다르게 실행타임에 얼마든지 데이터를 늘리고 줄일 수 있는 링크드리스트의 특징이다. 

 

 

 

 

먼저 구조체 포인터를 할당한다. 하나의 요소가 생길때마다 메모리에 할당하고 포인터 변수가 필요하다.

    NODE *head = (NODE *) malloc(sizeof(NODE));
    
    NODE *node1 = (NODE *) malloc(sizeof(NODE));
    NODE *node2 = (NODE *) malloc(sizeof(NODE));
    NODE *node3 = (NODE *) malloc(sizeof(NODE));
    NODE *node4 = (NODE *) malloc(sizeof(NODE));
    NODE *node5 = (NODE *) malloc(sizeof(NODE));

헤드는 시작점이다. 헤드에는 값을 넣을 필요는 없지만 일관성을 위해 초기화 시켜준다. 헤드에서 첫번째 노드를 가리킨다. (노드는 하나의 요소이다) 첫번째 노드에 값을 입력하고 둘째 노드를 가리킨다. 이런 식으로 어디까지나 갈 수 있는게 링크드 리스트이다. 제한은 없다. 그러나 이 연결구조에서 배열과 같은 직접 인덱스를 사용하지 못하기때문에 단점도 있다. 탐색 속도가 느리다는 것이 그 하나이다.

    head->number = 0;
    head->next_n = node1;
    node1->number = 15;
    node1->next_n = node2;
    node2->number = 30;
    node2->next_n =node3;
    node3->number = 45;
    node3->next_n = node4;
    node4->number = 60;
    node4->next_n = node5;
    node5->number = 75;
    node5->next_n = NULL;
 

다음은 탐색용 헤드이다. 처음 나오는 헤드가 아니라 이 헤드로 탐색을 한다고 보면 된다. 탐색용 헤드에 가장 처음 생성한 헤드가 가리키는 노드의 주소를 입력하면 탐색을 할 수 있다. 탐색헤드는 첫번째 노드에 연결된다. NULL 이 아니라면 현재 위치의 데이터(cur->number)를 읽어 올수 있다. 그 다음에 한칸 전진하기 위해서 두번째 노드를 가리키는 손을 자신의 포인터에 대입한다. 이것이 탐색을 하는 원리이다.

 

혼동스러운 부분이 있는데

 

NODE *cur = head->next_n 으로 설정하면 일단 cur에 동적메모리가 할당된 것은 아니다. 따라서 cur는 free해줄 필요가 없다. 

 

cur 는 주소값을 가지고 있다. (32비트 혹은 64비트 시스템에 따라) 그 주소값에 가서 -> 연산자는 구조체 개별 요소에 접근할 수 있다.

 

cur->number 는 head가 가리키던 노드에 저장된 정수값이다.

 

그리고 여기 cur->next_n 이부분이 헷갈리기 쉽다.

 

cur

 

cur->next_n

 

이 둘다 주소값이기 때문이다. cur 는 현재 위치이고 cur->next_n은 다음 노드의 위치이다. 쉽게 말해 한칸이다.

 

그럼 각자의 위치는 어떻게 되는가?

 

1.head

 

2. cur (head ->next_n 과 동일) 

 

3. cur -> next_n

 

cur->here 이렇게 써줬으면 좋았을 텐데 뭐 그렇게 만들 수는 있지만 CPU에게 한번 더 일을 시켜야 하니까 비효율 적이다.

 

내가 어디쯤 와있는지 판단하기 위해서 변수가 갖는 특징을 빨리 캣치해야 한다. 그런 부분들이 링크드리스트의 에로사항이라 할 수 있다.

 

    NODE *cur = head->next_n;

    while(cur != NULL)
    {
        printf("value : %d  address : 0x%08X\n",cur->number,cur);
        cur = cur->next_n;
    }
    free(node5); 
    free(node4); 
    free(node3); 
    free(node2); 
    free(node1); 
    free(head); 
    printf("All done and done!");
}

while 문을 저렇게 돌린 후에 마지막으로는 free로 동적 메모리 할당을 해제한다. 히프 영역에서 일어나는 일이며 프로그램 종료시에 히프영역도 사라지지만 스택영역과 달리 프로그래머가 메모리를 직접 해제하지 않으면 안된다.

 

stackoverflow라는 말도 메모리를 해제하지 않아서 프로그램이 크래쉬 (충돌, 비정상 종료)된 상황을 말한다. 메모리가 적은 과거에는 자주 일어났었고 메모리가 많은 지금도 메모리 관리에 부주의하면 언제라도 일어날 수 있는 상황이다.

 

말이 나와선데 stackoverflow 는 전세계 최대의 개발자 커뮤니티다. 파이썬에 관련한 질의 응답만도 수백만개 올라와있다고 한다. 다 읽어보지 않아서 사실인지는 모르겠다 ;;; (다 읽으면 늙어 죽을 듯) 그 사이트의 이름으로 명성을 떨칠만큼 메모리 관리가 프로그래머들에게는 중요하고 임팩트가 있는 것 아닐까? 생각해본다.

 

참고자료

Linked List | Set 1 (Introduction) - GeeksforGeeks

링크드 리스트는 자료구조에서 좀 더 깊이 있는 내용을 다룰 수 있을 거 같다. 이번 C 튜토리얼에는 아직 자료도 부족하고 해서 그렇게 깊게 들어가지 않으려고 한다.