15-3) 구조체를 활용한 연결 리스트

사용자에게 묻지 않고 프로그램이 알아서 동적 메모리 할당하기

 

동적 할당을 사용하면 데이터를 저장할 크기를 프로그램이 실행되는 중에 입력받아 변경할 수 있다. 따라서 컴파일 시점에 메모리 크기를 결정하기 때문에 실행 중에 메모리 크기를 변경할 수 없는 정적 할당보다 장점이 많다고 설명했다. 하지만 동적 할당도 사용자에게 입력받아서 합산하는 '더하기 프로그램'을 만든다고 생각해보자. 이 프로그램은 시작하면서 사용자에게 숫자를 몇 개 사용할 것인지 입력 받고, 그 개수만큼 동적으로 메모리를 할당한다. 그러면 사용자 입장에서는 입력한 개수만큼만 더하기 작업을 할 수 있기 때문에 불편하다.

 

사용자에게 가장 편한 방법은 몇 개의 숫자를 사용할 것인지 일일이 묻지 않고 사용자가 입력하는 대로 알아서 다 저장하고 합산해 주는 것이다. 그렇다고 사용자가 전부 사용할 수도 없을만큼 엄청나게 큰 메모리를 할당받아놓고 메모리 제한이 없는 것처럼 만드는것은 좋지 않다. 사실 이 문제를 해결하는 방법은 많지만 구조체를 배웠으니 구조체를 활용해서 해결해보자.

 

기존 방식에서 사용자에게 입력 받을 숫자의 개수를 붇는 이유는 할당된 주소를 저장할 포인터 변수를 1개만 사용하기 때문이다. 즉 한번의 메모리 동적 할당으로 저장할 공간을 만들기 때문이다.

 

따라서 사용자에게 몇 개의 숫자를 사용할 것인지 묻지 않으려면 메모리를 한번에 할당하지 않고 사용자가 숫자를 입력할 때마다 그 숫자를 저장하는 동적 메모레를 하나씩 늘려가는 방법을 사용하면 된다. 그런데 이 방법을 사용하려면 동적으로 할당된 메모리의 개수만큼 포인터가 있어야한다.

 

동적으로 할당된 메모리의 주소 값을 저장하기 위해 그 개수만큼 포인터가 있어야 한다. 그래서 사용자가 숫자를 입력할 때무다 숫자 1개와 포인터 1개가 늘어나도록 만들어야 한다. 포인터가 늘어나면 '포인터1'과 '포인터2'사이에도 사러 연결 고리가 있어야 연결이 유지된다. 그런데 '포인터1'은 사용자가 입력한 숫자를 저장한 메모리인 '숫자1'을 가리켜야 하기 때문에 '포인터2'를 가리킬 수가 없다. 포인터는 1개의 대상만 가리킬 수 있기 때문이다

 

이 문제는 '숫자1'과 '포인터2'를 각각 별개의 메모리로 할당하지 않고 하나의 메모리로 묶어서 동적으로 할당하면 간단하게 해결할 수 있다.

 

포인터 1 ----> 숫자1, 포인터2

 

위의 상황에서 '포인터2'는 아직 가리키는 대상이 없지만 새로운 숫자가 입력되면 그 숫자가 저장된 메모리의 주소를 가리킬 용도로 미리 만들어 놓은 것이다. 따라서 '숫자2'가 추가로 입력되면 다음 그림처럼 '숫자2'와 또 그 다음 숫자를 가리킬 '포인터3'이 함께 사용하는 동적 메모리를 할당해서 그 시작 주소를 '포인터2'에 저장한다. 이렇게 되면 '포인터2'를 사용해서 '숫자2'와 '포인터3'을 한 번에 사용할 수 있다.

 

포인터 1 ----> 숫자1, 포인터2 ----> 숫자2, 포인터3

 

결국 이런 방법을 사용하면 사용자가 숫자를 입력할 때마다 숫자와 포인터를 한 쌍으로 동적 할당하면서 계속 저장할 수 있다. 그리고 동적으로 할당된 메모리가 포인터로 연결되어있는데, 자료 구조에서는 이런 형식으로 자료를 관리하는 방법을 연결 리스트(linked-list)라고 부른다.

 

 

연결 리스트의 노드를 구조체로 선언하기

 

이제 앞에서 개념적으로 설명한 연결 리스트를 C언어에서 어떻게 구현할 수 있는지 단계별로 설명하겠다. 연결 리스트에서 숫자와 포인터를 함께 저장하기 위해 할당한 메모리를 노드(node)라고 부른다. 

 

포인터 1 ----> 숫자1, 포인터2(파란색 부분이 노드)

 

연결 리스트는 이 노드를 연결해서 데이터를 관리하기 때문에 노드에 해당하는 메모리를 어떻게 구성할지 먼저 결정해야 한다. 앞의 예시처럼 숫자와 포인트의 그룹을 구조체로 만들어 보면 다음과 같다.

 

type struct node /*이 구조체를 연결 리스트에서 노드(Node)라고 함*/ {     int number; /*숫자를 저장할 변수*/     struct node *p_next; /*다음 노드를 가리킬 포인터*/ } NODE;

 

 

연결 리스트에 노드를 추가하며 이어가기

 

1단계: 연결 리스트의 시작 상태

연결 리스트는 이전 노드와 이후에 새로 추가되는 노드를 포인터로 연결하면서 확장되는 방식이다. 하지만 모든 것을 노드만으로 해결할 수는 없다. 왜냐하면 동적으로 할당되는 첫 노드의 주소 값을 저장할 포인터가 필요하기 때문이다. 그래서 연결 리스트의 시작점이 되는 포인터가 필요한데 이 포인터를 헤드 포인터(Head Pointer)라고 한다.

 

포인터 1 (헤드 포인터라고 부른다)----> 숫자1, 포인터2

 

헤드 포인터는 NODE 구조체인 첫 노드를 가리킬 것이기 때문에 다음과 같이 NODE*형식으로 선언해야 한다. 그리고 가리키는 노드가 없음을 명시하기 위해서 NULL을 초깃값으로 대입한다.

/*NULL은 '해당하는 메모리 주소가 없음'이라는 의미로 사용한다.*/

 

NODE *p_head = NULL; /*첫 노드를 가리킬 헤드 포인터를 선언하고 NULL을 초깃값으로 대입함. 첫 노드가 없음을 명시*/

 

NULL (p_head) > "가리키는 대상 없음"

 

2단계: 숫자 12를 저장하기 위한 새 노드 추가

사용자가 12라는 숫자를 입력했다고 합시다. 이 값을 연결 리스트에 저장하기 위해 새로운 노드를 추가해야한다. 따라서 새로운 노드를 위한 메모리를 malloc 함수를 사용해 동적으로 할당한다. 그리고 할당된 새 노드의 주소 값은 p_head 포인터에 저장하여 헤드 포인터가 첫 노드를 가리킬 수 있도록 설정한다. 마지막으로 새로 할당된 노드의 number(p_head->number)에 입력된 숫자12를 저장하고 p_next(p_head->p_next)포인터에는 그 다음 노드가 없다는 뜻으로 NULL을 대입한다.

 

p_head = (NODE*)malloc(sizeof(NODE)); /*새 노드를 위한 메모리를 할당하고 주소 값을 헤드 포인터에 저장함*/ p_head->number = 12; /*노드의 number에 값 12를 저장함*/ p_head->p_next = NULL; /*다음 노드가 없음을 명시*/

새로운 노드가 힙 메모리의 100번지에 할당되었다고 가정하면 p_head는 새 노드를 가리켜야하기 때문에 100번지가 저장될 것이다. 그리고 노드 메모리의 시작 위치에 number가 있기 때문에 첫 노드에 포함된 number의 주소값은 100이고 number 요소의 크기가 4바이트이기 때문에 p_next의 주소 값은 104가 된다.

 

 

3단계: 숫자 15를 저장하기 위한 새 노드 추가

사용자가 15라는 숫자를 추가로 입력했다고 치자. 그러면 이 값을 연결 리스트에 저장하기 위해서는 새로운 노드를 한 번 더 추가해야 한다. 하지만 2단계와 달리 새로 추가되는 노드는 두 번째 노드이기 때문에 할당된 주소를 p_head 포인터에 저장하면 안 되고 첫 노드의 p_next포인터에 저장해야 한다.

 

포인터 1 (헤드 포인터)----> 숫자1(number), 포인터2(p_next)

 

첫 노드의 주소 값은 p_head 포인터에 저장되어 있기 때문에 첫 노드의 p_next를 사용하려면 'p_head->p_next'라고 사용하면 된다. 그리고 새로 할당된 노드의 number(p_head->p_next->number)에 입력된 숫자 15를 저장하고 p_next포인터(p_head->p_next->p_next)에는 그 다음 노드가 없다는 뜻으로 NULL을 대입한다.

p_head->p_next = (NODE*)malloc(sizeof(NODE)); /*노드를 위한 메모리를 할당함*/ p_head->p_next->number = 15; /*노드의 number에 15를 저장함*/ p_head->p_next->p_next = NULL; /*다음 노드가 없음을 명시함*/

이렇게 되면 다음 그림처럼 연결 리스트가 구성된다. 새로운 노드가 힙 메모리의 108번지에 할당되었다고 가정하면 첫 번째 노드의 p_next에는 주소 값 108이 저장될 것이다. 그리고 노드의 시작 위치에 number가 있기 때문에 두 번째 노드에 포함된 number의 주소 값은 108이고 number 요소의 크기가 4바이트이기 때문에 p_next의 주소값은 112가 된다.

100번지	첫 번째 노드		두 번째 노드
	100번지	104번지	108번지	112번지
p_head	12 number	108 p_next	15 number	NULL p_next

반복문으로 연결 리스트에서 마지막 노드 탐색하기

지금 설명하고 있는 연결 리스트에 노드를 새로 추가하면 기존에 구성된 노드 목록에서 가장 뒤쪽에 추가될 것이다. 그래서 첫 노드의 주소 값은 p_head에 저장했지만 그 다음 노드의 주소 값은 p_haed->p_next에 저장하고 그 다음 노드의 주소 값은 p_head->p_next->p_next에 저장한다. 이렇게 노드를 5개 추가하고 여섯번째 노드를 추가하려면 여섯번째 노드의 주소값은 다섯번째 노드의 p_next에 저장해야 한다. 따라서 다음과 같이 코드를 구성하면 된다.

 

p_head->p_next->p_next->p_next->p_next->p_next =(NODE*)malloc(sizeof(NODE));

그런데 위와 같이 코드를 적는 것은 문제가 있을것이다. 만약 연결 리스트에 노드가 100개까지 추가되었고 101번째 노드를 추가해야 한다면 p_next->를 무려 100번이나 적어야 하니 코드가 매우 불편하고 복잡해진다.

 

다행이 이 문제는 간단하게 해결할 수 있다. 위 예시를 보면 p_next->작업이 일정하게 반복된다. 따라서 이 문제는 반복문을 사용하여 해결할 수 있다. 이 반복문의 시작 값은 헤드 포인터인 p_head 변수에 저장된 주소 값이고, p_next에 저장된 값이 NULL이 되면 반복문을 끝내게 된다. 왜냐하면 마지막 노드의 p_next에 NULL이 저장되어 있고 새로운 노드가 추가된다면 NULL이 들어있던 p_next에 주소값이 저장될 것이기 때문이다.

 

이 반복문을 코드로 구성해 보자

/*반복은 p_head에 저장된 주소 값에서 시작함. p_head는 첫 노드의 주소 값을 저장함*/ NODE *p = p_head; /*p_next가 NULL일 떄까지 반복함. p_next 값이 NULL이면 마지막 노드라는 뜻임*/ while(NULL != p->p_next){      p = p->p_next; /*p->p_next 값을 p에 대입하면 p는 다음 노드의 주소로 이동함*/ }

위의 예시에서 포인터 변수 p에 저장된 주소 값은 while문이 한 번 반복할 때마다 p가 가리키는 노드의 다음 노드의 주소로 이동한다. 따라서 위의 코드처럼 작업하면 while 반복문을 끝냈을 때 포인터 변수 p에 연결 리스트 마지막 노드의 주소 값이 저장되어 있을것이다.

 

 

100번지	첫 번째 노드(반복 1회)		두 번째 노드
	100번지	104번지	108번지	112번지
p_head	12 number	108 p_next	15 number	NULL p_next

 

 

조건을 체크하여 연결 리스트에 새로운 노드 추가하기

 

연결 리스트에 노드가 하나도 없는 경우(p_head가 NULL인 경우)를 체크하지 않으면 문제가 발생할 수 있다. 따라서 p_head가 NULL인지 여부를 체크해서 처음 노드를 만드는 작업인지를 구별해야 한다. 연결 리스트에 노드를 추가하는 작업은 이후에도 계속해서 반복적으로 일어나는 작업이기 때문에 이 작업을 함수로 만들어 보자.

다음에 정의한 AddNumber 함수는 연결 리스트에 새로운 노드를 추가하고 data 변수에 넘긴 숫자 값을 새로 추가된 노드의 number에 저장하도록 구성했다.

 

void AddNumber(NODE **pp_head, int data) /* *p의 주소를 담을때 : **pp (별이 한개 더 붙음) */ {      NODE *p;      if(NULL != *pp_head){          p = *pp_head; /*pp_head를 사용해 값을 변경하면 p_head값이 수정된다. p_head 포인터에 저장된 주소 값을 의미한다. 이 값이 NULL이면 기존 연결 리스트에 노드가 없다는 뜻이다.*/          /*마지막 노드를 찾기 위해서 p_next가 NULL일때까지 반복함*/          while(NULL != p->p_next) p = p->p_next;          p->p_next = (NODE *)malloc(sizeof(NODE));  /*새 노드를 위한 메모리를 할당함*/          p = p->p_next;   /*새로 만든 노드의 주소 값을 p에 넣음*/ } else {      /*p_head 값이 NULL이라서 첫 노드가 추가됨. p_head 값에 직접 대입함*/          **p_head = (NODE*)malloc(sizeof(NODE));          p = *pp_head; /*새로 만든 노드의 주소 값을 p에 넣음*/          }      p->number = data;  /*새 노드의 number에 data값을 저장함*/      p->p_next = NULL;  /*다음 노드가 없음을 명시함*/ }

이렇게 AddNumber 함수를 만들었다면 이 연결 리스트에 새로운 노드를 추가하고 값15를 저장하고 싶을 때 다음과 같이 코드를 구성하면 된다.

 

NODE *p_head = NULL; AddNumber(&p_head, 15);

 

 

연결 리스트의 마지막 노드 기억하기

앞에서 정의한 AddNumber 함수의 단점은 노드가 추가될 때마다 마지막 노드를 찾기 위해 탐색을 해야 한다는 점이다.

노드가 많아질수록 이 작업은 점점 더 느리게 수행된다. 그래서 연결 리스트는 시작 노드의 주소 값을 기억하는 헤드 포인터처럼 마지막 노드의 주소 값을 기억하는 '테일 포인터'(Tail Pointer)를 하나 더 사용한다. 그러면 새 요소가 추가될 때 마지막 노드를 찾기 위해 일일이 탐색하지 않고 테일 포인터가 가리키는 노드에 바로 추가할 수 있다.

AddNumber 함수에 테일 포인터 p_tail을 사용하도록 소스 코드를 수정해 보자.

 

void AddNumber(NODE **pp_head, NODE **pp_tail, int data) {      if(NULL != *pp_head){          (*pp_tail)->p_next = (NODE*)malloc(sizeof(NODE));          *pp_tail = (*pp_tail)->p_next;  /*p_tail(*PP_tail)에 새 노드의 주소 값을 저장함*/ } else {          /*p_head 값이 NULL이라서 첫 노드가 추가됨. p_head에 직접 대입함*/          *pp_head = (NODE*)malloc(sizeof(NODE)); /*새 노드의 메모리를 할당함*/          *pp_tail = *pp_head;  /*새 노드의 주소값을 p_tail(*pp_tail)에 저장함*/          }      (*pp_tail)->number = data;  /*새 노드의 number에 data 값을 저장함*/      (*pp_tail)->p_next = NULL;  /*다음 노드가 없음을 명시함*/ }

위의 코드처럼 연결 리스트의 마지막 노드를 기억하는 테일 포인터를 사용하도록 변경하면 다음 그림처럼 테일 포인터가 항상 마지막 노드를 가리키게 된다.

 

100번지	첫 번째 노드		두 번째 노드
	100번지	104번지	108번지	112번지
p_head	12	108	15	NULL
	number	p_next	number	p_next

따라서 새로 추가한 노드(마지막 노드)의 주소 값을 p_tail 포인터가 기억하므로 노드가 추가될 때마다 마지막 노드를 찾기 위해 탐색할 필요가 없다. 즉 앞에서 구성한 AddNumber 함수에서는 마지막 노드를 찾기 위해 다음 반복문이 필요했지만 테일 포인터를 사용하도록 만든 AddNumber 함수에서는 이 반복문이 사라졌기 때문에 프로그램이 훨씬 효율적이다.

 

while(NULL != p->p_next) p = p->p_next; /*마지막 노드를 탐색하는 반복문이 필요하지 않음*/

 

 

연결 리스트의 전체 노드 제거하기

이렇게 동적으로 할당된 노드들은 free 함수를 호출하여 메모리를 해제할 때까지 유지된다. 따라서 프로그램이 끝날 때 동적으로 할당된 노드를 모두 제거하는 작업을 추가해야 한다. 이 작업은 연결 리스트를 구성하는 노드를 탐색하면서 하나씩 노드를 제거해야 하므로 앞에서 설명한 마지막 노드를 찾는 작업과 비슷하다. 즉 첫 노드부터 마지막 노드까지 반복하면서 주소 값을 저장하기 위해 할당된 메모리를 하나씩 해제하면 된다. 그런데 이 작업을 너무 단순하게 생각해서 코드를 다음과 같이 구성하면 문제가 생기므로 주의해야 한다.

 

NODE *p = p_head; /*시작 노드부터 마지막 노드까지 이동하도록 반복문을 구성*/ while(NULL != p){      free(p);                 /*포인터 변수 p가 가리키는 노드를 삭제함*/      p = p->p_next;      /*오류 발생 : 다음 노드로 이동할 수 없음*/ }

앞의 코드는 포인터 변수 p를 사용해서 연결 리스트를 구성하는 첫 노드부터 마지막 노드까지 찾는 작업은 잘 구성했다. 하지만 free 함수를 호출한 시점에 문제가 있다. 왜냐하면 free(p);를 수행하면 포인터 변수 p가 가리키고 있던 메모리가 해제되는데 이 해제된 메모리에 다음 노드의 주소 값을 기억하고 있던 p_next도 포함되어 있기 때문이다. 즉 이미 해제된 메모리를 사용하려고 해서 오류가 발생한 것이다.

 

1. while 반복문 수행 전 상황

2. free(p);가 수행됨. 포인터 변수 p가 가리키는 대상이 메모리에서 해제됨

3. p = p->p_next;가 수행됨

포인터p가 가리키던 대상 메모리가 해제되었기 때문에 108번지가 들어 있던 p_next를 사용할 수 없다. 이미 해제된 메모리를 사용하려니까 오류가 발생한다. 이 문제를 해결하려면 p가 가리키는 대상 메모리를 해제하기 전에 p->p_next에 저장된 주소값을 다른 포인터 변수로 옮겨놓고 해제하면 된다.

 

NODE *P = p_head, *p_save_next; /*시작 노드부터 마지막 노드까지 이동하도록 하는 반복문을 구성*/ while(NULL != p){      p_save_next = p->p_next; /*p->p_next 값을 다른 포인터 변수에 보관함*/      free(p_head);                 /*포인터 변수 p_head가 가리키는 노드를 삭제함*/      p_head = p;                  /*다음 노드로 옮김*/ } /*while문이 끝났다는 것은 연결 리스트의 모든 노드가 제거되었다는 뜻이다.*/ P_tail = p_head;                  /*반복문을 빠져나오면 p_head 값은 NULL이므로 p_tail값도 NULL로 변경함*/

 

연결 리스트로 더하기 프로그램 만들기

여러 개의 숫자를 입력 받아서 합산하는 프로그램에 연결리스트를 추가하여 소스 코드를 수정해 보겠다. 이렇게 작업하면 사용자에게 몇개의 숫자를 사용할 것인지 묻지 않고 바로 사용자가 입력한 숫자들을 합산해서 출력할 수 있다.