이전 장에서 포인터의 중요한 두가지 용도를 보았음. 11장: 변수를 가리키는 포인터를 함수 인수로 사용하여 함수가 변수를 수정하는 방법. 12장: 배열 원소에 대한 포인터에 대해 산술 연산을 수행하여 배열을 처리하는 방법. 이 장에서는 동적 저장소 할당, 함수에 대한 포인터라는 두 가지 기능을 알아보면서 포인터에 대한 내용을 완성함.
동적 할당을 사용해 프로그램은 실행 중 필요에 따라 메모리 블록을 얻을 수 있음.
17.1: basics of dynamic storage allocation.
17.2: dynamically allocated strings, which provide more flexibility than ordinary character arrays.
17.3: dynamic storage allocation for arrays in general.
17.4: storage deallocation - releasing blocks of dynamically allocated memory when they're no longer needed.
동적 할당 구조는 연결되어 리스트, 트리, 기타 매우 유연한 데이터구조를 형성할 수 있기 때문에 C 프로그래밍에서 큰 역할을 함.
17.5: Linked lists(the most fundamental linked data structure)
17.6: Pointer to pointer(enough to warrant a section of its own)
17.7: pointer to functions
마지막 두 섹션은 고급 C프로그래머가 관심가질 내용이고 초보자는 스킵해도 무방하다.
17.8: restricted pointers(C99)
17.9: flexible array members(C99)
17.1 Dynamic Storage Allocation
C의 데이터 구조는 보통 그 크기가 정해져 있음. 배열의 크기는 프로그램 컴파일 후 바뀌지 않는다. (C99에서 VLA는 런타임 시점에 길이가 결정되지만, 그 이후로는 배열이 살아있는 동안 고정되어 있다) 고정된 크기의 데이터 구조는, 프로그램을 수정하고 다시 컴파일하지 않으면 그 크기를 바꿀 수가 없다.
dynamic storage allocation을 사용하면, 데이터구조를 필요에 따라 키우고 줄일 수 있다.
Memory Allocation Functions
동적 할당을 사용하기 위해 <stdlib.h> 헤더에 선언된 다음 메모리 할당 함수 중 하나를 호출해야 한다.
malloc : 메모리 블록을 할당하지만 초기화하지는 않는다.
calloc : 메모리 블록을 할당하고 내용을 지운다.
realloc : 이전에 할당된 메모리 블록의 크기를 조정한다.
셋 중 malloc이 가장 많이 사용된다. 이는 calloc에 비해 효율적인데, 할당하는 메모리를 청소해야 할 필요가 없기 때문이다.
메모리 할당하는 함수를 호출해서 메모리 블록을 요청할 때, 그 함수는 우리가 어떤 형식의 데이터를 블록에 저장하려는지 모른다. 따라서 int, char같은 일반적인 형식의 포인터를 리턴하지 못한다. 대신 void * 포인터를 리턴한다. void * 는 "일반적인" 포인터로, 본질적으로 그냥 메모리 주소이다.
Null Pointers
메모리 할당 함수가 호출되었을 때, 그 요청을 만족하기에 충분한 크기의 메모리 블록을 찾지 못할 가능성은 항상 존재한다. 그런 일이 일어나면, 함수는 null pointer를 반환한다. null pointer는 "아무것도 아닌 것에 대한 포인터"로, 다른 모든 유효한 포인터로부터 구별되는 특별한 값이다. 함수의 리턴값을 포인터 변수에 저장한 후에, 그것이 null pointer인지 아닌지 반드시 확인해야 한다.
null pointer는 NULL 매크로에 의해 표현되며, <locale.h>, <stddef.h>, <stdio.h>, <stdlib.h>, <string.h>, <time.h> 그리고 C99의 <wchar.h> 헤더에 정의되어 있다. 이 중 하나만 include하면 NULL 매크로가 정의된다.
if (p == NULL) ...
if (!p) ...
// p가 null 매크로인지 확인. null pointer는 '거짓'이고 모든 다른 포인터는 '참'이다. 따라서 위 두 라인은 동일하다
if (p != NULL) ...
if (p) ...
// 위 두줄도 동일하다.
17.2 Dynamiccaly Allocated Strings
동적 할당은 문자열을 다룰 때 편리하게 쓰는 경우가 많다. 문자열은 문자 배열에 저장되며, 그 배열의 길이가 얼마나 되야 할 지는 예측하기 힘들다. 문자열을 동적 할당 함으로써, 그 결정을 프로그램이 실행될 때까지 미룰 수 있다.
Using malloc to Allocate Memory for a String
malloc 함수의 원형은 다음과 같다:
void *malloc(size_t size);
malloc은 size 바이트 만큼의 블록을 할당해서 그것을 가리키는 포인터를 반환한다. size의 형식은 size_t(unsigned integer)이다. 매우 거대한 메모리 블록을 할당하는 것이 아니라면, size를 평범한 정수형 타입으로 간주해도 무방하다.
malloc으로 문자열을 위한 메모리를 할당하는 것은 쉽다. 왜냐하면 C에서 char 형식 값은 항상 정확히 1바이트의 저장 공간을 차지하도록 되어 있기 때문이다. n개의 문자가 있는 문자열을 위한 공간을 할당하기 위해, 이렇게 쓴다:
char *p;
p = malloc(n + 1);
인수는 null character를 위한 자리를 위해 n이 아닌 n + 1이다. malloc이 리턴하는 일반적인 포인터는 할당이 수행될 때 char * 형으로 변환된다: 형식 지정은 필요하지 않다. (일반적으로, void * 값을 어떤 타입의 포인터에든 assign할 수 있고, 그 역도 성립한다) 그래도 malloc의 리턴 값을 cast하는 프로그래머들도 있다.
p = (char *) malloc(n + 1);
malloc으로 할당된 메모리는 지워지거나 초기화되어있지 않으므로, p 는 초기화되지 않은 n+1크기의 문자 배열을 가리킨다.
이 배열을 초기화하는 방법 중 하나는 strcpy 함수를 호출하는 것이다:
strcpy(p, "abc");
Using Dynamic Storage Allocation in String Functions
동적 할당을 이용하면 "새로운" 문자열 - 함수 호출 전에는 존재하지 않았던 - 을 리턴하는 함수를 만들 수 있다. 두 개의 문자열을, 둘다 수정하지 않고 연결하는 함수를 만들어 보자. C의 표준 라이브러리에는 그러한 함수가 없다(strcat은 인수로 전달받은 문자열 변수 중 하나를 수정하기 때문에 우리가 원하는 함수가 아니다).
이 함수는 연결되어야 하는 두 문자열의 길이를 측정하고, malloc 함수를 호출해서 연결될 결과물에 맞는 공간을 할당한다. 그리고 나서 첫번째 문자열을 새로운 공간에 복사하고, strcat으로 두번째 문자열을 뒤에 연결한다.
char *concat(const char *s1, const char *s2)
{
char *result;
result = malloc(strlen(s1) + strlen(s2) + 1);
if (result == NULL) {
printf("Error: malloc failed in concat\n");
exit(EXIT_FAILURE);
}
strcpy(result, s1);
strcat(result, s2);
return result;
}
만약 malloc이 null pointer를 반환한 경우, 함수는 에러 메시지를 출력하고 프로그램을 종료한다. 이것이 항상 좋은 해결책은 아니다; 어떤 프로그램은 메모리 할당 실패를 복구하고 계속 실행되어야 한다.
concat같은 동적으로 저장공간을 할당하는 함수는 조심스럽게 사용해야 한다. 함수가 리턴하는 문자열이 더이상 필요가 없어질 때, free 함수를 호출해 문자열이 점유하는 공간을 release해 주어야 한다. 그렇지 않으면 프로그램은 결국 메모리가 부족해질 수 있다.
Arrays of Dynamically Allocated Strings
13.7에서 문자열을 배열에 저장할 때의 문제를 해결했다. 문자열을 문자의 2차원 배열에 열로 저장했을 때 공간이 낭비되었기 때문에, string literal을 가리키는 포인터들의 배열로 만들어 문제를 해결했다. 13.7에서 사용한 방법은 배열의 원소가 동적 할당된 문자열인 경우에도 사용할 수 있다.
17.3 Dynamically Allocated Arrays
동적 할당된 배열은 동적 할당된 문자열과 같은 이점을 갖는다(당연히 문자열도 배열이니까). 프로그램을 작성할 때, 종종 배열의 적합한 크기를 추정하기 어려울 때가 있다; 배열의 크기를 결정하는 것을 프로그램이 실행될 때로 미루면 더 편리할 것이다. 배열을 위한 공간을 프로그램 실행 도중 할당하고 나서, 배열의 첫번째 원소를 가리키는 포인터를 통해 배열에 접근할 수 있다. 12장에서 보았듯이 배열과 포인터 간에 밀접한 관계가 있으므로, 동적 할당된 배열을 사용하는 것은 평범한 배열을 사용하는 것과 똑같이 쉽다.
malloc이 배열에 공간을 할당할 수 있지만, calloc 함수가 대신 사용될 때도 있다. 왜냐하면 calloc 함수는 할당하는 메모리를 초기화하기 때문이다. realloc 함수는 필요에 따라서 배열을 늘리거나 줄일 수 있게 해 준다.
Using malloc to Allocate Storage for an Array
문자열을 위한 공간을 할당할 때와 거의 같은 방식으로 malloc을 사용해 배열을 위한 공간을 할당할 수 있다. 주요한 차이점은 임의의 배열의 원소는 문자열과 달리 항상 1바이트가 아니라는 것이다. 그 결과 각각의 원소에 필요한 공간을 계산하기 위해 sizeof 연산자를 사용해야 한다.
원소가 정수이고 크기가 n인 배열을 쓰는데 n은 프로그램 실행중에 결정된다고 하자. 먼저 포인터 변수를 선언한다.
int *a;
프로그램 내에서 n의 값을 알게 되면, malloc을 호출해서 배열을 위한 공간을 할당한다.
a = malloc(n * sizeof(int));
주의: 배열을 위한 공간을 할당할 때는 항상 sizeof 연산자를 사용해야 한다.
a가 동적 할당된 메모리 블록을 가리키게 되면, a가 포인터라는 사실을 무시하고 배열의 이름으로 사용해도 된다. 이는 C에서의 배열과 포인터의 관계 덕분이다. 예를 들어, 다음과 같은 루프를 사용해 a가 가리키는 배열의 원소를 초기화할 수 있다.
for(i = 0; i < n; i++)
a[i] = 0;
The calloc Function
비록 malloc 함수로 배열을 위한 메모리를 할당할 수 있지만, 대안인 calloc 함수는 때때로 더 낫다. calloc 함수는 <stdlib.h>에 선언되어 있으며 원형은 다음과 같다.
void *calloc(size_t nmemb, size_t size);
calloc은 각각의 원소가 size 바이트를 점유하는 원소 nmemb개를 가진 배열을 위한 공간을 할당한다; 만약 요청받은 공간을 할당하지 못하면 null pointer를 리턴한다. 메모리를 할당한 후, calloc은 그 메모리 공간의 모든 비트를 0으로 초기화한다. 예를 들어, 다음과 같이 calloc을 호출하면 크기가 n인 정수 배열을 위한 공간을 할당하고, 모든 값을 0으로 초기화 시킨다.
a = calloc(n, sizeof(int));
calloc은 malloc과 달리 할당한 메모리를 지우기 때문에, 배열이 아닌 object의 공간을 할당하기 위해서 calloc을 사용하는 경우가 종종 있다. calloc을 호출하면서 첫번째 인자로 1을 넣으면, 어떤 타입의 데이터든간에 공간을 할당한다.
struct point { int x, y; } *p;
p = calloc(1, sizeof(struct point));
위 코드를 실행하면 p는 x와 y가 0인 point 구조체를 가리키게 된다.
The realloc Function
배열을 위한 메모리를 할당하고 나서, 그 크기가 너무 크거나 작은 경우, realloc 함수를 사용해 배열의 크기를 바꿀 수 있다. <stdlib.h>에 있는 realloc 함수의 원형은 다음과 같다:
void *realloc(void *ptr, size_t size);
realloc이 호출될 때, ptr은 반드시 이전에 malloc, calloc, 또는 realloc을 호출해서 얻어진 메모리 블록을 가리켜야 한다(그렇지 않은 경우, undefined behavior). size 매개변수는 블록의 새로운 크기를 나타내며, 원래의 크기보다 늘리거나 줄일 수 있다. ptr이 배열로 사용되고 있는 메모리를 반드시 가리켜야 하지는 않지만, 실제로는 보통 그렇다.
C 표준에서는 realloc의 행동에 대한 몇가지 규칙을 정해 놓고 있다.
- 메모리 블록을 확장할 때, realloc은 블록에 추가된 바이트들을 초기화하지 않는다.
- realloc이 요청받은 대로 메모리 블록을 확장하지 못했을 때, null pointer를 반환한다; 원래 메모리 블록에 저장되어 있던 데이터는 바뀌지 않는다.
- realloc의 첫번째 인자가 null pointer인 경우, malloc과 동일하게 작동한다.
- realloc의 두번째 인자가 0인 경우, 메모리 블록을 할당 해제한다.
표준 문서는 이 이상으로 realloc의 작동 방식을 상세히 설명하지는 않지만, 합리적으로 효율적일 거라고 기대된다. 메모리 블록을 감소시킬 때, 블록에 저장되어 있는 데이터를 움직이는 일 없이 제자리에 둔다. 마찬가지로, 메모리 블록을 늘릴 때도 데이터는 움직이지 않는다. 만약 메모리 블록을 늘릴 수 없는 경우(바로 다음 공간이 다른 목적으로 이미 사용되고 있는 경우), realloc은 다른 공간에 새로운 블록을 할당하고, 예전 데이터를 그 곳에 복사한다.
realloc 함수가 값을 리턴한 후, 반드시 모든 포인터를 새 메모리 블록을 가리키도록 업데이트 해야 한다. 왜냐하면 realloc이 메모리 블록을 다른 어딘가로 옮겼을 가능성이 존재하기 때문이다.
17.4 Deallocating Storage
malloc과 다른 메모리 할당 함수가 메모리 블록을 얻어오는 곳은 heap이라고 알려져 있는 저장 공간이다. 이 함수들을 너무 자주 호출하거나 너무 큰 메모리 블록을 요구하는 것은 heap을 소진시켜서, 함수들이 null pointer를 리턴하게 만들 수가 있다.
설상가상으로, 프로그램은 메모리를 할당하고 더 이상 추적하지 못해서 공간을 낭비할 수 있다.
p = malloc(...);
q = malloc(...);
p = q;
두번째 줄까지 실행했을 때의 결과이다. p가 한 메모리 블록을 가리키고 있고, q는 또다른 메모리 블록을 가리키고 있다.
q가 p로 assign된 후(q is assigned to p), 첫번째 블록을 가리키는 포인터가 더 이상 존재하지 않는다(shaded). 따라서 이 공간은 다시 사용할 수 없다. 더 이상 프로그램에서 접근할 수 없는 메모리 블록을 garbage라고 한다. 가비지를 남기는 프로그램은 memory leak을 가지고 있다. 어떤 언어에서는 garbage collector를 제공해서 자동적으로 garbage를 찾아내고 recycle하지만, C는 그렇지 않다. 대신 C 프로그램에서는 free 함수를 사용해 필요하지 않게 된 메모리를 해제함으로써 garbage를 직접 recycle해야 한다.
The free Function
<stdlib.h>에 있는 free 함수의 원형은 다음과 같다:
void free(void *ptr);
free를 사용하는 것은 간단하다; 더 이상 필요하지 않은 메모리 블록을 가리키는 포인터를 인자로 전달하면 된다.
p = malloc(...);
q = malloc(...);
free(p);
p = q;
free 함수를 호출하면 p가 가리키던 메모리 블록을 해제한다. 이제 그 블록은 다음에 malloc이나 기타 메모리 할당 함수를 호출했을 때 이용할 수 있다.
free함수의 인자는 null pointer거나(이때 free함수는 아무런 효과가 없다) 이전에 메모리 할당 함수로 리턴된 값이어야만 한다. 다른 object에 대한 포인터를 전달한 경우(배열 원소 같은), undefined behavior가 발생한다.
The "Dangling Pointer" Problem
free 함수를 통해 더 이상 필요하지 않은 메모리를 되찾을 수 있지만, 새로운 문제도 생긴다: dangling pointers(달랑거리는 포인터?). free(p)를 호출하는 것은 p가 가리키던 메모리 블록을 해제하지만, p 자체를 바꾸는 것은 아니다. p가 더이상 유효한 메모리 블록을 가리키지 않는다는 사실을 잊어버리면 혼돈이 뒤따를 수 있다.
char *p = malloc(4);
...
free(p);
...
strcpy(p, "abc"); /*** WRONG ***/
dangling pointers는 찾기 어려울 수 있는데, 여러 개의 포인터들이 같은 메모리 블록을 가리킬 수도 있기 때문이다. 만약 그 블록이 해제되면, 블록을 가리키던 모든 포인터들은 'dangling'이 되어 버린다.
17.5 Linked Lists
동적 할당은 리스트, 트리, 그래프, 또 다른 링크드 데이터 구조를 만들 때 특히 유용하다. 이 절에서는 링크드 리스트에 대해 알아본다; 다른 링크드 데이터 구조는 이 책의 범위를 넘어선다.
linked list는 연속된 구조체(nodes)로 구성되어 있다. 각각의 노드는 체인의 다음 노드를 가리키는 포인터를 담고 있다.
리스트의 가장 마지막 노드에는 null pointer가 들어 있다. 위 그림에선 대각선으로 표시되었다.
이전 장들에서, 우리는 데이터 아이템들의 콜렉션을 저장하고 싶을 때에는 항상 배열을 사용했다; 링크드 리스트는 그 대안이 되어 준다. 링크드 리스트는 배열보다 더 유연하다: 쉽게 노드를 삽입하거나 삭제할 수 있어, 리스트를 늘리거나 줄일 수 있다. 반면, 배열처럼 아무 곳에나 접근할 수는 없다. 배열의 각 원소에 접근하는 데에는 모두 동일한 시간이 걸린다; 링크드 리스트 안 노드의 경우에는 시작 지점에서 가까우면 시간이 적게 걸리고, 끝에 가까우면 오래 걸린다.
이 절에서는 링크드 리스트 구현, 그를 통해서 할 수 있는 몇가지 흔한 연산 - 리스트 시작지점에 노드 삽입, 노드 찾기, 노드 삭제에 대해 설명한다.
Declaring a Node Type
링크드 리스트를 설정하려면, 가장 먼저 필요한 것은 리스트를 구성하는 노드를 나타내는 구조체이다. 간단히 생각해서 노드는 하나의 정수와 다음 노드를 가리키는 포인터로 구성되어 있다고 가정하자. 노드 구조체는 다음과 같이 생겼다:
struct node {
int value; /* data stored in the node */
struct node *next; /* pointer to the next node */
};
next 멤버의 형식은 struct node *이며, node 구조체를 가리키는 포인터임을 의미한다. 이름인 node에는 특별한 점이 있으며, 평범한 structure tag이다.
중요하게 짚고 넘어갈 점은, 16.2에서 살펴봤듯이, 구조체 종류에 이름을 붙일 때 structure tag 방법과 typedef으로 특정 구조체의 종류에 이름을 붙이는 방법이 있다. 이 경우 구조체에 있는 포인터 멤버는 항상 같은 종류의 구조체만 가리키기 때문에, structure tag를 사용해야만 한다. node 태그 없이는, next 형식을 선언할 방법이 없다.
이제 node 구조체가 선언되었으므로, 어디서 리스트의 시작 위치를 추적할 방법이 필요하다. 다른 말로, 언제나 리스트의 첫 번째 노드를 가리킬 변수가 필요하다. 그 변수를 first라고 하자:
struct node *first = NULL;
first를 NULL 로 설정하는 것은 리스트가 초기화되면서 비어 있음을 나타낸다.
Creating a Node
링크드 리스트를 만들 때, 노드를 하나 하나 만들어서 리스트에 연결시킨다. 노드를 만드는 것은 세 단계를 거친다:
1. Allocate memory for the node.
2. Store data in the node.
3. Insert the node into the list.
우선 여기서는 1과 2에 집중한다.
node를 만들 때, 노드가 리스트에 삽입될 때까지 임시적으로 그것을 가리킬 포인터 변수가 필요하다. 이 포인터 변수를 new_node라고 하자:
struct node *new_node;
malloc을 사용해 새로운 노드를 위한 메모리를 할당하고, 그 리턴 값을 new_node에 저장하자.
new_node = malloc(sizeof(struct node));
이제 new_node는 node 구조체를 저장하기에 딱 알맞은 크기의 메모리 블록을 가리키게 된다:
그리고 새로운 node의 value 멤버에 데이터를 저장한다.
(*new_node).value = 10;
이 assignment 후에는 이런 그림이 된다:
노드의 value 멤버에 접근하기 위해 indirection 연산자(*)를 사용하였고, 선택 연산자 "." (구조체의 멤버를 선택하기 위해)를 사용하였다. *new_node는 괄호로 감싸져 있어야 한다. "." 연산자는 * 연산자보다 우선순위가 높기 때문이다.
The -> Operator
새로운 노드를 리스트 안에 삽입하는 다음 단계로 넘어가기 전에, 유용한 바로가기에 대해 알아보자. 포인터를 사용해 구조체의 멤버에 접근하는 것이 굉장히 흔한 일이기에 C에서는 이 목적만을 위한 특별한 연산자를 제공한다. right arrow selection, "->" 연산자이다.
*(new_node).value = 10;
new_node->value = 10;
둘은 동일하다. -> 연산자는 *와 . 연산자를 결합한 것이다; new_node를 간접 참조해서 그것이 가리키는 구조체를 찾고, 그 멤버인 value를 선택한다.
-> 연산자는 lvalue를 만들어 내므로 다른 일반적인 변수가 들어가는 곳에 사용할 수 있다. scanf함수에서도 많이 사용된다.
scanf("%d", &new_node->value);
Inserting a Node at the Beginning of a Linked List
링크드 리스트의 장점은 노드가 리스트 안의 어느 지점이든 연결될 수 있다는 것이다: 시작, 끝지점, 또는 중앙 어떤 곳이든. 리스트 가장 처음에 넣는 것이 가장 쉽기 때문에 이것을 먼저 보자.
new_node가 삽입될 노드를 가리키고 있고, first가 링크드 리스트의 첫번째 노드를 가리키고 있다면, 두개의 statement를 사용해서 리스트에 노드를 넣는다. 먼저, 새로운 노드의 next 멤버가 원래 처음에 있던 노드를 가리키도록 많든다:
new_node->next = first;
두번째로, first가 새로운 노드를 가리키도록 만든다.
first = new_node;
이 방법은 리스트가 비어 있을 때에도 사용할 수 있다.
다음은 비어 있는 리스트에 두 개의 노드를 연결하는 코드이다.
first = NULL; // 리스트 초기화
new_node = malloc(sizeof(struct node));
new_node->value = 10;
new_node->next = first;
first = new_node; // 첫번째 노드를 링크에 삽입
new_node = malloc(sizeof(struct node));
new_node->value = 20;
new_node->next = first;
first = new_node; // 두번쨰 노드를 링크에 삽입
링크드 리스트에 노드를 삽입하는 것은 매우 흔한 연산이어서 그를 위한 함수를 쓰고 싶을 때가 많다. 그 함수의 이름을 add_to_list라고 하자. 이 함수는 두 개의 매개변수를 갖는다: list(원래 리스트의 첫번째 노드를 가리키는 포인터), n(새로운 노드에 저장될 정수)
struct node *add_to_list(struct node *list, int n)
{
struct node *new_node;
new_node = malloc(sizeof(struct node));
if (new_mode == NULL) {
printf("Error: malloc failed in add_to_list\n");
exit(EXIT_FAILURE);
}
new_node->value = n;
new_node->next = list;
return new_node;
}
위 함수는 list 포인터를 바꾸지 않는다. 그 대신, 새로 삽입된 노드를 가리키는 포인터를 반환한다. add_to_list를 호출할 때, 그 반환값을 first에 저장해야 한다.
first = add_to_list(first, 10);
first = add_to_list(first, 20);
위 문장들은 10과 20이 담겨 있는 노드를 first가 가리키고 있는 리스트에 삽입한다. add_to_list가 first의 새로운 값을 반환하는 게 아니라 first를 직접 업데이트하는 것이 꽤 까다롭다. 이 문제에 대해선 17.6에서 설명한다.
다음 함수는 add_to_list를 사용해서 사용자가 입력한 숫자들을 담고 있는 링크드 리스트를 만든다.
struct node *read_numbers(void)
{
struct node *first = NULL;
int n;
printf("Enter a series of integers (0 to terminate): ");
for (;;) {
scanf("%d", &n);
if (n == 0)
return first;
first = add_to_list(first, n);
}
}
숫자들은 입력한 역순으로 리스트에 저장된다. first는 항상 가장 마지막으로 입력한 숫자를 담은 노드를 가리키고 있기 때문이다.
Searching a Linked List
링크드 리스트를 만들었으면, 특정한 데이터를 검색해야 될 수 있다. 리스트를 검색하기 위해서 while 문도 쓰일 수 있지만, for 문이 종종 더 낫다. 우리는 카운팅을 포함하는 루프에서 for 문을 사용하는 것에 익숙하지만, for 문의 유연성 덕분에 링크드 리스트를 포함한 다른 작업에 적합한 경우가 많다. 링크드 리스트의 노드들을 다음과 같은 관례적 방법을 사용해서 접근한다. 포인터 변수 p를 "현재" 노드를 추적하기 위해 사용한다:
for (p = first; p != NULL; p = p->next)
...
p = p ->next
이 assignment는 포인터 p를 다음 노드로 전진시킨다. 이런 형태의 assignment는 C에서 링크드 리스트를 가로지르는 loop을 작성할 때 변함 없이 쓰인다.
search_list 함수: 정수 n을 리스트(매개변수 list가 가리키는)에서 검색한다. 만약 n을 찾으면, n을 담고 있는 노드의 포인터를 반환한다; 찾지 못하면 null pointer를 반환한다. 위에 쓴 관례적 표현을 사용해서 써 보자.
struct node *search_list(struct node *list, int n)
{
struct node *p;
for (p = list; p != NULL; p = p->next)
if (p->value == n)
return p;
return NULL;
}
search_list를 다르게 쓰는 방법도 많이 있다. 대안 중 하나는 p 변수를 없애고, list 자체를 이용해서 현재 노드를 추적하는 것이다:
struct node *search_list(struct node *list, int n)
{
for (; list != NULL; list = list->next)
if (list->value == n)
return list;
}
list 변수는 원래 리스트의 포인터의 복사본이므로, 그 자체를 함수 내에서 바꾸더라도 전혀 문제가 되지 않는다(*list의 값을 바꾸지 않았음).
또 다른 대안은 list->value == n 테스트를 list != NULL 테스트와 결합하는 것이다.
struct node *search_list(struct node *list, int n)
{
for (; list != NULL && list->value != n; list = list->next)
;
return list;
}
리스트의 마지막에 도달했을 때, list의 값은 NULL 이므로 n을 찾지 못해서 리스트의 마지막에 도달했을 때 list를 리턴하는 것은 NULL을 리턴하는 것이다. 이 버전을 while 문으로 바꾸면 좀더 깔끔해진다.
struct node *search_list(struct node *list, int n)
{
while (list != NULL && list->value != n)
list = list->next;
return list;
}
Chapter 17 - Advanced Uses of Pointers - 2/3 에서 계속됨