티스토리 뷰


 절대 시험공부가 하기 싫어서가 아니라 실습실에서 후배들이 중간고사 대비로 연결 리스트에 대해 심각하게 스터디하는 장면을 목격했다. 옛날에 내가 스터디 하면서 후배들 가르칠 때 생각도 나고 해서 잠깐 앉아서 구경이나 하면서 앉아만 있긴 지루하니 간단하게 단방향 연결 리스트를 C언어로 짜봤다. 한 2년 전에 처음 리스트에 대해 배우고 코딩할 때 하루종일 걸려서 끙끙댔었는데, 지금은 한 5분? 10분? 정도면 간단하게 짜여지는게 참 기분이 묘했다.

 결국 연결 리스트의 핵심은 코드에 정의되지 않은 로직 즉, 사용자로 부터 Node를 생성하라는 요청을 받았을 때 메모리 Heap 영역에 공간을 할당하고 그 할당된 친구를 기존 리스트에 붙이거나, 기존의 노드를 삭제하거나, 간단하게 출력만 하거나 등등 일 것이다. 자료 구조에서 연결 리스트는 매우 기초적인 것이지만 이것을 제대로 익히면 C 언어에서의 메모리 동적 할당과 포인터 변수/연산을 이해하는데 큰 도움이 된다.

연결 리스트에 사용할 구조체 선언

1
2
3
4
5
6
7
8
9
10
typedef struct __list {
    struct __node *cur;
    struct __node *head;
    struct __node *tail;
} linkedList;
 
typedef struct __node {    
    int data;
    struct __node *next;
} node;
cs

 기본적인 연결 리스트의 구조체 선언이다. 사실 linkedList 구조체의 *cur 변수는 간단한 형태의 연결 리스트에서는 필요 없지만 그냥 스터디하는 친구가 쓰길래... 여튼 중요한건 __list 구조체(typedef를 사용하여 linkedList 로 별칭 할당)는 하나의 연결 리스트에서 시작점(*head)과 끝점(*tail)을 저장하는 __node에 대한 포인터 변수를 가지고 있다. __node 구조체는 실제 하나의 노드를 나타내고 있으며 내부의 data 변수에 실제 우리가 담고자 하는 데이터를 할당하게 될 것이다. 그리고 각 노드는 다음 노드의 주소 값을 가지는 *next 변수를 가져야한다. 다음 그림을 보면 좀 더 이해가 쉬울 듯.

< 일반적인 단방향 연결 리스트의 구조 >

linkedList 할당 부분

1
2
3
4
5
6
7
8
9
10
int main(void) {
    //linkedList pointer define start
    linkedList *= (linkedList *)malloc(sizeof(linkedList));
    L->cur = NULL;
    L->head = NULL;
    L->tail = NULL;
    //linkedList pointer define end
 
    ...
}
cs

 최초에는 연결 리스트 자체에 대한 정보(Meta Information?)를 가지는 linkedList를 할당 해줘야한다. 예전에 꽤 많은 후배들이 왜 malloc을 사용하여 동적 할당 해줄 때 캐스팅을 해줘야하는지 몰랐던 것이 떠오르는데 malloc은 리턴 타입이 void 이기 때문에 꼭 사용하고자 하는 자료형으로 캐스팅 해줘야한다. return type void 란 딱히 정해진 return type이 없고 내가 쓰고 싶은 형태에 따라 적절하게 사용될 수 있다는. 뭐 그런 느낌적인 느낌이다. 동적할당으로 선언된 *L 은 최초에 어떠한 노드도 포함하고 있지 않으므로 각각의 멤버 변수를 NULL로 초기화 해주는 작업이 필요하다.

insert 함수 선언 부분

1
2
3
4
5
6
7
8
9
10
11
void createNode(linkedList *L, int tdata) {
    node *newNode = (node *)malloc(sizeof(node));
    newNode->data = tdata;
    newNode->next = NULL;
    if(L->head == NULL && L->tail == NULL)
        L->head = L->tail = newNode;    
    else {
        L->tail->next = newNode;
        L->tail = newNode;
    }
}
cs

 새로운 노드(newNode)를 node 구조체의 포인터 변수로 생성하고 현재 연결리스트(L)에 붙이는 함수다. 매개 변수로는 main 함수에서 할당한 LinkedList의 주소값(L)과 삽입할 데이터(tdata)를 받는다. 동적 할당을 통해 heap 영역에 newNode가 사용할 공간을 할당 받고 이 할당받은 공간의 시작 주소 값을 newNode 포인터 변수에 할당했다. 예전 스터디 때 의외로 많이 들었던 질문이 "어차피 1개의 노드를 할당하는 것이면 동적 할당 하지않고 그냥 정적 선언해서 주소 값만 리턴 받으면 되지 않나요?" 인데, 이것에 대해 정확하게 설명하려면 메모리 구조상의 스택(Stack) 영역과 힙(Heap) 영역에 대한 이해가 필요하다. Stack 영역은 소스 코드 진행 상 하나의 함수가 끝나면 그 함수 내에서 선언되고 사용된 모든 정보가 사라진다. 정확히 말하면 해당 공간이 사라지는 것은 아니고 무의미해지는데 코드가 진행되면서 해당 메모리 공간이 다른 것으로 무조건 덮어 씌워지게 될 것이다. 반면 Heap 영역은 사용자가 요청에 따라 할당을 받고 사용자의 요청에 따라 삭제가 이루어지는 곳이다. 즉, 해당 함수가 종료되어도 할당받은 메모리 공간을 계속 사용할 수 있다는 소리가 된다.

 여튼 malloc을 통해 할당받은 노드에 데이터를 집어넣고 next 변수를 NULL로 초기화(여기가 끝이란 말) 한 뒤 간단한 조건문이 튀어나왔는데, 이는 최초의 *L 이 Empty List 즉, 공백 리스트일 때를 예외처리 해준 것이다. 지금 집어 넣는 노드가 첫 노드라면 headtail을 방금 할당한 노드의 주소 값으로 넣어준다는 소리다. 만약 지금 집어 넣는 노드가 첫 노드가 아니라면? 지금 끝이라고 정의되어있는 노드(tail)의 next에 할당한 노드의 주소 값을 넣어주고 그 끝이라고 정의된 노드에 방금 새롭게 할당한 노드의 주소 값을 넣어주는 것이다. (아 말로 풀어쓰려니 겁나 어렵넹.. 그냥 코드보시고, 그래도 이해안되면 그림을 그려보세요.) 추가로 우리는 끝 노드의 주소값(L->tail) 정보가 있으니 이 경우 삽입 시의 시간 복잡도는 O(1)이된다.

delete 함수 선언 부분

1
2
3
4
5
6
void deleteLastNode(linkedList *L) {
    node *= L->head;
    while(p->next->next != NULL) p = p->next;
    p->next = p->next->next;
    L->tail = p;
}
cs

 마지막 노드를 삭제하는 함수다. 첫 노드(L->head) 부터 끝 노드(p->next == NULL)의 전 노드(p->next->next == NULL)까지 간 다음 그 노드의 next를 NULL로 만들어 버린다. (그런데 내가 왜 소스코드에는 p->next = p->next->next 라고 했는지... 아마 중간 노드 삭제를 고려한 듯 하다; 어차피 결과는 다르지 않다.) 처음 연결 리스트를 접하면 생각보다 삭제시 조건문을 한번에 떠올리지 못하는 경우를 자주 봤다. 그리고 p->next->next 를 보고 감탄을 하는 후배들을 봐왔는데, 나는 오히려 처음 연결 리스트를 코딩하면서 단번에 p->next->next를 떠올린다면 코딩 센스가 대단히 좋은 친구라고 밖에 못하겠다. 당연히 나도 그 때는 그 생각을 못 했다. 코딩할 때는 마지막 노드만을 삭제하는 함수를 구현했지만 만약 중간 노드를 삭제하려는 경우 삭제하려는 노드의 이전 노드 next에 삭제하려는 노드 다음 노드의 주소값을 넣어주면 된다. 뭔 말이고 하니 다음 그림을 보면 된다.

< 중간 노드를 삭제하는 경우. 이전 노드의 next를 다음 노드의 주소 값으로만 바꿔주면 된다. >

 사실 우리의 소중한 메모리 공간을 이쁘게 사용하기 위해서는 삭제해준 노드가 할당 받은 heap 영역을 해제해 줘야한다. 코드에서는 생략되었다. 그리고 단방향 연결리스트는 각 노드가 이전 노드의 주소값(prev)를 가지고 있지 않기 때문에 삭제를 위해서는 반드시 첫 노드(head)부터 순차 탐색을 해서 삭제할 노드의 이전 노드까지 가야한다. 그렇기 때문에 삭제시의 시간복잡도는 O(n)이 된다. (어? 그럼 마지막 노드의 이전 노드 값도 계속 가지고 있으면 되잖아? 마지막 노드만을 지우는 경우는 잘 없다. 세상은 그렇게 호락호락 하지 않다. 마지막 값만 지울 거면 스택을 쓰지.)

print 함수 선언 부분

1
2
3
4
5
6
7
8
9
10
void printNodes(linkedList *L) {
    node *= L->head;    
    putchar('[');
    while(p != NULL) {
        printf("%d, ", p->data);
        p = p->next;
    }
    putchar(']');
    putchar('\n');
}
cs

 모든 노드를 출력해주는 함수의 선언 부분이다. 매우 간단하다. 우리는 리스트의 첫 시작 노드의 주소값(L->head)을 가지고 있고, 끝 노드의 next에게 NULL을 주었다. 그냥 반복문을 돌면서 p->next가 NULL이 될 때까지 p=p->next를 하며 p->data를 출력해주면 되는 것이다.

전체 소스코드

실행결과

< 1삽입 - 2삽입 -3삽입 - 삭제 - 4삽입 - 5삽입 - 6삽입 - 삭제 - 삭제 - 7삽입 - 출력 >

같이 보면 좋을지도 모르는 포스트

[개인공부/C and C++] - 변수와 메모리 관계에 대해

[개인공부/시스템] - 스택 메모리 영역에 대해

[개인공부/시스템] - 스택 프레임(Stack Frame)에 대해

Programming Compile & Loading (Prezi Presentation) - 43 슬라이드 부터 보세요.

마무리

 역시 시험기간에는 포스트가 정말 잘 써진다. 그리고 방금 느낀 건데, 뭔가 내가 생각해서 쓰는 글 보다 단순하게 머리 속에 있는 지식을 끄집어 내서 쓰는게 훨씬 쉽다는 것을 깨달았다. 젠장 그리고 이 현실 도피성의 성격을 가진 포스트가 누군가의 현실에는 도움이 되었으면 좋겠다.


2016.10.08 추가 내용

지나가시던 어떤 분(컴퓨터공학 전공의 학생으로 추정)이 포스트를 보고 메일로 질문을 주셨다. 꽤나 성심성의껏 답해드렸다 생각되어 여기에 남긴다.

질문요약

1. *L은 동적할당인가요?

2. node 구조체 내의 *next는 왜 스스로를 할당하나요. 이해가 되지 않습니다.

장문의 답변

...생략...

포인터에 대해 간략하게 설명드리면, 질문자님께서 프로그래밍하여 선언된 변수는 모두 메모리 공간에 자리를 잡게됩니다. 그리고 각 메모리 공간은 1 byte 마다 고유의 주소 값을 가지고 있습니다. 만약 int 형의 변수를 선언한다면 int 자료형의 크기인 4 byte 크기 만큼 메모리가 할당됩니다. 4 byte 만큼 할당 되었단 얘기는 4개의 주소 값을 쓰고 있다는 얘기겠죠? 여기서는 임의로 1000, 1001, 1002, 1003 이라는 4개의 주소 값을 할당받았다고 가정하겠습니다.

이 때, 방금 할당한 int 형 변수의 시작 주소 값은 1000이 됩니다. 이 때 컴퓨터는 int 형의 크기(4 byte)를 알고 있으니 시작 주소 값만을 사용해 데이터를 처리할 수 있는데 (1000의 주소 값에서 시작하여 4개 만큼의 주소 값을 사용하면 된다는 것을 알고있음) 이러한 식의 처리를 주소값과 포인터를 사용해 할 수 있습니다. 

질문으로 돌아가 linkedList *L이 동적할당이냐고 물어보셨는데, 답부터 알려드리자면 맞습니다. 변수명 앞에 *이 붙을 경우 이 변수는 포인터 변수(주소값을 저장하는 변수, 포인터 변수는 무조건 4 byte 입니다.)로 사용하겠다고 컴퓨터(컴파일러)에게 알려줍니다. *L이 포인터 변수로 선언되었고, 주소 값을 저장할 준비가 되었습니다. 이 다음에 malloc 함수를 통해 메모리 공간에 linkedList 구조체의 크기(3개의 포인터 변수 = 12 byte)만큼을 할당하고 이 할당받은 메모리의 시작 주소 값을 *L에 저장합니다. 동적 할당이 잘 되었고, 포인터에 주소 값도 잘 저장되었다면 이제 이 포인터 변수에 저장된 주소 값으로 동적 할당되어 생성된 LinkedList 구조체에 접근할 수 있습니다.

현재까지의 진행을 가정과 예를 들어 표시하면 다음과 같습니다.

  • malloc을 통해 할당된 불특정 메모리 공간의 시작 주소 값 : 2000

  • malloc을 통해 할당된 불특정 메모리 공간의 데이터 : *cur, *head, *tail

  • *L에 주소값 : 1000

  • *L의 데이터(주소값) : 2000

*L을 참조하여 LinkedList 구조체에 접근한다고 생각하시면 쉬우실 겁니다.

위 내용을 이해하셨다면 다음 질문도 쉽게 이해하실 수 있습니다. 우선 구조체(struct) 선언를 변수 선언과 같다고 생각하시면 안됩니다. 오히려 변수를 만들기 위한 자료형(틀)을 선언하는 것이라고 생각하시기 바랍니다. node 구조체를 동적할당으로 메모리의 불특정 위치에 할당한다면 이 불특정 위치의 시작 주소 값을 저장할 공간이 필요합니다. 그래서 이전 node의 *next에 다음 node의 시작 주소 값을 저장합니다. 보내주신 사진이 구조상으로는 맞지만 만약 *next에 다음 node의 실제 데이터가 저장된다고 이해하신 것이라면 틀린 것이고, *next에 다음 node로 가기 위한 시작 주소 값이 저장되는 것이라고 이해하신 것면 맞습니다.

  • malloc을 사용한 첫번째 node의 시작 메모리 주소 값 : 1000

  • malloc을 사용한 첫번째 node의 크기 : 8 byte (int 4 + 포인터 4)

  • malloc을 사용한 두번째 node의 시작 메모리 주소 값 : 1100

  • 첫번째 node의 *next에 저장된 두번째 node의 주소 값 : 1100

위 와 같은 방식으로 새로운 node를 malloc 통해 계속 할당하고 malloc의 retrun 값(malloc은 불특정한 메모리 공간에 생성된 시작 주소 값을 return해 줍니다.)을 이전 node의 *next에 저장한다면 구조적으로 보았을 때 연결된 형태의 자료 구조를 만들 수 있습니다. 이러한 자료 구조를 연결 리스트(Linked List)라고 합니다.

...생략...


저작자 표시 비영리 변경 금지
신고
프로필사진

Yowu (Yu Yongwoo)

My MBTI type is ENTP. (Of course I do not believe it 100%, but I want to do that) I use Node.js to develop the backend. I use Ubuntu Linux as my development environment, and I love Vim. I am interested in open source and are keen to contribute. I have a bachelor's degree in computer science from Catholic University and now a software engineer at Plating Inc., I spent about 5 years developing and learning, and I am still interested in software development and culture. Recently, I am interested in React, Serverless structure, Domain Design Driven. Sometimes I play drums in the band.