C언어 7 - 3 | 링크드 리스트 기초 (Linked List) 요소 추가 및 삭제 함수, 잡설

이 포스팅의 예제는 함수를 사용하여 요소를 추가하고 삭제하는 링크드 리스트이다.

 

링크드 리스트의 개념에 대해서는 이고잉님의 생활코딩의 영상 강의가 매우 좋다.

 

Linked list - Data Structure (자료구조)

개인적으로는 개념에 대해서는 도식이나 그림을 사용한 영상강의가 좋은 것 같고

 

코드 분석에 대해서는 영문 웹사이트나 블로그의 설명이 좋은 것 같다.

 

대신 설명이 잘 써져 있는 곳을 찾기가 힘든데, 그것도 구글의 SEO 최적화로 검색어만 잘 입력하면 쉽게 구할 수 있다. 요샌 워낙 흔해서 그런지 사람들의 이목을 잘 못끌지만... 구글의 검색 알고리즘은 시맨틱 해석을 하는 것으로 보인다. 특히 긴 문장을 검색할 수록 구글은 최고의 검색결과를 보여준다. 검색어과 전혀 무관한 문장을 툭 던져도 알아서 나온다.

 

전통적으로 IT기술자들이 문서를 많이 공유해서 그런가 지금은 그런게 잘되있다.

 

이 링크드 리스트도 워낙 고전이고 입문과정에서 한번씩 해보는 챕터라 자료가 많이 나와있다. 한글, 영문, 다음에는 일본어로 검색해봤다. 역시 전통의 IT 강국이라 자료가 상세하게 나온다. 다음의 자료는 구글에서 링크드리스트 C언어로 검색한 결과이다. 이 키워드는 검색시스템이 추천하는 키워드이다.

 

リンクドリスト c言語 - Google 검색

 

 

어쨋든 인터넷에 자료는 다 있다. 문제는 어떻게 구현하는가 이다. 인터넷의 자료가 많아도 내가 필요한 목적에 쓰지 못하면 무용지물이다.

 

결국은 스스로 해봐야 한다. 남의 코드를 카피하는 것은 한계가 있다.

 

물론 가장 기초적인 문법 사항들에 대해서는 카피라고 할 수 없을 것이다. 아래와 같은 코드를 그대로 복사해서 사용한다고 한들 그걸 카피라고 생각할 수 있을까?

int a = 5;
int b = 10;

int c = a + b;

printf("%d\n",c);

 그런 주장을 하는 사람은 매우 무지한 것이다. 이것은 C언어의 기본 문법에 지나지 않는다. a,b,c를 변수로 사용하는 것은 대다수가 가진 습관이다. 중요한 이유는 타이핑하기 귀찮아서 이거나, a,b,c로 변수를 설정하면 코드가 간결해져서 추상화가 더 쉽다거나 하는 이유가 있다.

 

그건 저작권이 아니라 기호다. 그래서 이 블로그에서는 별로 와닿지 않더라도 n1,n2,n3 를 사용하는 등 숫자를 붙이는 코드가 많다. str1,str2 는 문자열 1번 2번 이렇게 부여한다.

 

그러나 설명의 내용은 일반적이더라도 독창적일 수 있다. 그런 방식의 접근을 하는 사람은 많지 않기 때문일 것이다. 자기의 언어로 바꾸면 일반적인 원리도 독창적이 된다. 한 두개 가지고는 뭐라 할 수 없지만 그런 내용이 몇년에 걸쳐 쌓인다면 지적 재산권을 만들 수 있을 지도 모른다. 그게 참 애매한 부분이 있다.

 

어쨋든 우리는 모두 남에게서 배운다. 남에게서 배우고 또 새로운 것을 하나 붙여 만들면 또 다른 남이 나에게 배우고 이런 순환의 생태계속에 살고 있다. 오픈소스의 생태계에 대해서 세계인들도 커뮤니티에 부정적인 이야기를 많이 한다. 대체로 창조하는 사람과 돈을 버는 사람들이 같지가 않다.

 

이제는 돈을 버는 사람들이 너무나 많은 지지를 받고 있어서 누가 창조했다고 주장하면 돌을 맞을 이야기도 많이 존재한다. 물론 돈을 버는 사람들은 매우 영리하게 일을 잘 한 것이고, 기술이 소수의 전유물일 때 그것을 대중에게 나누어 주는 일을 했으니 공로가 더 클 수도 있다.

 

스티브 잡스가 대표적이지 않을까 싶다. 비즈니스 인사이더는 현재의 애플 컴퓨터는 거의 모두 데니스 리치의 업적에 기반하고 있다고 평가했다. 하지만 사람들이 기억하는 것은 검은 터틀넥을 입고 stay hungry stay foolish 를 외치는 잡스이지 데니스 리치가 아니다.

 

다소 냉소적이지만 코드에 대한 탐구는 문득 그런 생각을 들게 한다. 이 모든 것들을 누가 무엇을 생각하며 창조했을까? 그 사람들은 대접을 잘 받았을까? 아니면 그냥 역사속에 잊혀졌을까? 딱히 알지 못하는 사람들에 동정하기 위함은 아니다. 이것이 인간 개인들이 모인 인류는 앞으로 나아가기 위해서 모든 사람을 기억할 필요가 없다. 인류에게 인격이 있다면 그것은 끓임없는 탐구와 열정, 초월성의 추구다. 그게 가장 잘 드러나는 것이 기술분야이다.

 

우리가 보는 코드들 ... 골방과 연구실에서 수십년을 연구한 사람이 제시한 하나를 해답을 우리는 보고 있을 뿐이다.

 

하루만에 이해가 되지 않는게 당연할 것이다. 

 

링크드 리스트 함수

잡설은 이정도로 하고 C언어의 링크드 리스트 코드를 살펴본다. main 함수와 결과를 먼저 보는게 낫다.

 

첫 시작인 헤드의 바로 다음에 붙이는 기초적 방식으로 구현되었다.

 

추가적으로 개선을 할 필요가 있지만 단순히 설명하기에는 좋다. 링크드 리스트의 추가와 삭제만 있기 때문이다.

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

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

void addFirst(NODE * node_Point, int num1)
{
    NODE * newNode = (NODE *)malloc(sizeof(NODE));
    newNode->next_n = node_Point->next_n;
    newNode->number = num1;
    node_Point->next_n = newNode;
    printf("Added [value : %d  address : 0x%08X]\n",newNode->number,newNode);
}
void removeFirst(NODE * node_Point)
{
    if(node_Point == NULL){
        return;
    }
    printf("removing  process... ");
    NODE *removeNode = node_Point->next_n;
    printf("let go at [value : %d  address : 0x%08X]\n",removeNode->number,removeNode);
    node_Point->next_n = removeNode->next_n;
    free(removeNode);
}

void main(){

    printf("the size of NODE : %d\n",sizeof(NODE));
    NODE *head = (NODE *) malloc(sizeof(NODE));
    head->next_n = NULL;

    addFirst(head,12);
    addFirst(head,24);
    addFirst(head,36);
    removeFirst(head);
    addFirst(head,48);
    addFirst(head,60);
    removeFirst(head);
    addFirst(head,72);
    addFirst(head,84);

    NODE *cur = head->next_n;
    printf("\n Here's every list available!\n");
    while(cur != NULL)
    {
        printf("value : %d  address : 0x%08X\n",cur->number,cur);
        cur = cur->next_n;
    }
    printf("All done and done!\n\n");
    
    cur = head->next_n;
    while(cur != NULL)
    {
        printf("staring freeing mem... ");
        printf("let go at [value : %d  address : 0x%08X]\n",cur->number,cur);
        NODE * temp = cur->next_n;
        free(cur);
        cur = temp;
    }
    free(head);
    printf("Heap Memory is free now!");
}

 

 

요소를 추가하는 함수이다. 우선 기준이 되는 노드의 포인터를 받아야 한다. 여기서는 메인에서 헤드를 받는다. 입력할 숫자도 받는다. 알기 쉽게 12의 배수로 했다.

 

새로운 링크를 추가하므로 동적인 메모리 할당이 필요하다. 사이즈는 NODE 사이즈 만큼 포인터에 할당한다. newNode 가 할당받은 메모리는 이 함수가 끝나도 남아있겠지만 newNode 라는 포인터에 메인함수에서 접근할 수는 없을 것이다.  따라서 식별자가 사라지기 전에 자신의 역할을 다해야 한다.

void addFirst(NODE * node_Point, int num1)
{
    NODE * newNode = (NODE *)malloc(sizeof(NODE));
    newNode->next_n = node_Point->next_n;
    newNode->number = num1;
    node_Point->next_n = newNode;
    printf("Added [value : %d  address : 0x%08X]\n",newNode->number,newNode);
}

처음엔 head 포인터가 들어오므로 head 기준으로 설명한다.

 

head 가 매개변수로 들어오면 함수안에서 메모리를 새로 할당하는 노드의 바로 앞에 위치할 것이다.

 

지금 head 가 가리키는 마지막은 NULL 이다. (리스트의 끝이라는 뜻) NULL을 새로 할당한 노드의 next_n에 대입한다.

 

새로 할당한 값을 newNode->number 데이터 영역에 대입한다. 

 

이 시점에서 새로운 노드의 정보 입력은 완료되었다. 12를 넣었다면

 

node1은

 

number = 12

next_n = NULL

 

이다. 이제 헤드가 node1을 가리키도록 해야함으로써 연결을 완료된다.

 

head - node1

 

이 관계가 완료되었다.

 

두번째 값을 넣는것도 반복이다. (node2)

 

head 가 24를 가지고 매개변수로 들어와서 newNode 포인터에 메모리를 할당하고, head가 가리키는 node1의 값을 node2에 대입할 것이다. 그 다음에 값 24를 newNode->number에 대입한다. newNode 데이터는 다 되었다.

 

다시 head가 이번에는 node2를 가리킨다. head->next_n = newNode

 

head - node2 - node1

 

이 되는 것이다.

 

나머지는 반복이다...

 

다음은 삭제이다. 삭제는 가장 최근에 추가한 요소를 삭제할 것이다. 추가한 곳에서 삭제한다는 것은 스택의 push and pop과 비슷하다. 단 pop 처럼 값은 반환안한다.

 

만약 NULL이면 헤드 외에 요소가 없다는 뜻이다. 그런 경우 그냥 return 이다.

 

삭제 위치는 바로 찾을 수 있다. head가 가리키는 주소이다. 현재까지 node2를 생성했다면 node2가 될 것이다.

 

head가 가리키는 주소값을 NODE 포인터에 할당한다. 주소만 가져오므로 동적 메모리를 할당하지 않을 것이다.

 

그런 후 헤드의 포인터에 삭제할 노드가 가리키는 위치를 입력한다.

 

그러면 삭제할 노드의 주소값이 확보가 되었고 head는 다음 노드인 node1을 가리키면서 node2는 리스트에서 떨어져 나갔다.

 

마지막으로 free 함수로 노드를 메모리에서 삭제를 한다. 이 과정을 잊으면 메모리 누수가 발생한다. free가 성공했는지 실행 결과는 확인해야 한다.

 

void removeFirst(NODE * node_Point)
{
    if(node_Point == NULL){
        return;
    }
    printf("removing  process... ");
    NODE *removeNode = node_Point->next_n;
    printf("let go at [value : %d  address : 0x%08X]\n",removeNode->number,removeNode);
    node_Point->next_n = removeNode->next_n;
    free(removeNode);
}

 

메인함수는 따로 설명이 필요없다. 순차적으로 링크드 리스트를 호출하다가 마지막에 탐색용 포인터 cur를 꺼내서 사용한다.

void main(){

    printf("the size of NODE : %d\n",sizeof(NODE));
    NODE *head = (NODE *) malloc(sizeof(NODE));
    head->next_n = NULL;

    addFirst(head,12);
    addFirst(head,24);
    addFirst(head,36);
    removeFirst(head);
    addFirst(head,48);
    addFirst(head,60);
    removeFirst(head);
    addFirst(head,72);
    addFirst(head,84);

    NODE *cur = head->next_n;
    printf("\n Here's every list available!\n");
    while(cur != NULL)
    {
        printf("value : %d  address : 0x%08X\n",cur->number,cur);
        cur = cur->next_n;
    }
    printf("All done and done!\n\n");
    
    cur = head->next_n;
    while(cur != NULL)
    {
        printf("staring freeing mem... ");
        printf("let go at [value : %d  address : 0x%08X]\n",cur->number,cur);
        NODE * temp = cur->next_n;
        free(cur);
        cur = temp;
    }
    free(head);
    printf("Heap Memory is free now!");
}

마지막 while 문은 어떻게 메모리를 해제해야 하는지 알려준다.

 

탐색용 포인터에 head 가 가리키는 노드를 대입힌다. head 부터 순차로 탐색하여 모두 메모리에서 제거 할 것이다.

 

원리는 remove 함수와 같다. 임시 노드 포인터에 다음 노드의 주소를 저장후 본인 cur 의 메모리를 해제한다. 그 후 임시 포인터에서 다음의 주소값을 얻는다. while문이 돌 때마다 cur의 주소가 NULL이 아닌지 확인한다. 마지막 노드의 포인터에는 NULL 이 있을 것이므로 cur가 NULL 이라는 것은 모두 메모리에서 해제되었다는 의미이다.

 

cur 역시 스택에 있는 포인터이기 때문에 임무를 끝내고 메모리를 해제할 필요가 없다.

 

마지막으로 헤드(처음 노드)를 메모리에서 해제한다. 끝이다.

 

설명해 놓으니까 꽤나 길다. 자료구조라서 복잡하기 때문에 그렇다. 먼저 그림으로 개념을 익히고 나서 코드를 사용해 보는 것을 권장한다. 그림을 봐선 알겠는데 코드로 구현할 수 없으면 말짱 도루묵이고 코드는 짜고 있는데 개념이 없다면 온라인의 링크드 리스트 개념도를 봐야한다. 

 

Linked list - Data Structure (자료구조)