포인터

포인터의 개념

• 포인터
• 포인터 연산
• 배열

포인터의 종류

• 상수 포인터
• 배열 포인터
• 구조체 포인터
• 함수 포인터

포인터의 응용

• 포인터 배열
• 함수 포인터 배열
• 다중 포인터
• 연결 리스트

---

포인터의 개념

포인터

포인터 변수는 주소를 값으로 가지는 변수
'역참조'라는 기능으로 주소를 통해 값에 접근할 수 있다.

int x = 30; // 주소 1000

// 선언 1
int *p = &x;

// 선언 2
int *p;
p = &x;

printf("%u\n", p);	// 1000
printf("%d\n", *p);	// 30, 역참조

포인터 연산

포인터는 어떤 자료형이든 항상 주솟값을 값으로 가지는데 int*나 char* 따위의 타입은 왜 지정해줘야 하나 한다면, 각 자료형마다 크기가 달라 메모리를 어느 길이로 읽어줘야 하는지 알려줘야 하기 때문이다.

• +, -
  포인터끼리의 연산은 정의되지 않고, 포인터에 정수를 더할 때의 연산만 정의되는데, 그 포인터의 역참조값의 자료형의 크기만큼 더해진다.

char* c;	// 주소 1000
int* i;		// 주소 2000
double* d;	// 주소 3000

printf("%u %u\n", c, c + 1);	// 1000 1001
printf("%u %u\n", i, i + 1);	// 2000 2004
printf("%u %u\n", d, d + 1);	// 3000 3008

• *
  곱하기 연산이 아니고 참조 연산자이며, 단항연산자이다.

int x = 3;
int* p = &x;

printf("%d", *p);	// 3

• &
  주소연산자이며 단항연산자이다.

int x = 3;	// 주소 1000
int* p = &x;

printf("%u %u", &x, p);	// 1000 1000

• ++, --
  전위증감연산자인지 후위증감연산자인지에 따라 달라진다.
  우선순위는 x++가 제일 빠르고, ++x == *x == &x 이다.

int x = 3;	// 주소 1000
int* p = &x;

printf("%d\n", ++*p);	// x = 4 되고 4 출력
printf("%d\n", *++p);	// p->1004 되고 *(1004) 출력
printf("%d\n", *p++);	// 3 출력하고 p->1004
printf("%d\n", (*p)++);	// 3 출력하고 x = 4

배열

배열은 메모리상에서 연속적으로 원소의 자료형의 크기만큼의 자리를 차지하며 나열되어있다.

int arr[5] = { 1, 2, 3, 4, 5 }; // 주소 1000

for (int i = 0; i < 5; ++i)
	printf("%u: %d\n", &arr[i], arr[i]);

// 1000: 1
// 1004: 2
// 1008: 3
// 1012: 4
// 1016: 5

포인터의 연산과 배열 원소 간 주솟값 차이가 같다는 것을 이용해 다음과 같이 루프를 돌 수도 있다.

int arr[5] = { 1, 2, 3, 4, 5 }; // 시작 주소 1000

for (int* p = &arr[0]; p - &arr[0] < 5; ++p)
	printf("%u: %d\n", p, *p);

또한 위의 성질로부터 동치인 표현을 알 수 있다.

arr[i] = *(arr + i);

배열의 이름이 배열 첫 번째 원소의 주솟값과 같다는 사실로 코드를 더 줄일 수도 있다.

&arr[0] <=> &(*(arr + 0)) <=> &(*arr) <=> arr

int arr[5] = { 1, 2, 3, 4, 5 }; // 주소 1000

for (int* p = arr; p - arr < 5; ++p)
	printf("%u: %d\n", p, *p);

---

포인터의 종류

상수 포인터

역참조나 주솟값이 상수처럼 여겨져 변경이 금지되는 포인터 변수

int x = 4;

const int* p;	// 역참조 변경 금지
p = &x;
*p = 3;	// 오류

int x = 4;

int* const p;	// 주솟값 변경 금지
p = &x; // 오류
*p = 3;

int x = 4;

const int* const p;	// 역참조, 주솟값 변경 금지
p = &x; // 오류
*p = 3;	// 오류

배열 포인터

type를 가리키는 일반 포인터 변수와는 다르게 type[N]를 가리키는 것

int a[5] = { 1, 2, 3, 4, 5 };
int (*pa)[5];
pa = &a;

for (int i = 0; i < 5; ++i)
	printf("%d ", (*pa)[i]);	// 1 2 3 4 5 

int (*pa)[3];

int x[] = { 1, 2, 3 };
pa = &x;

int y[] = { 0, 1, 4, 9 };
pa = &y;	// int[3]이 int[4]를 가리킬 수 없으므로 오류

구조체 포인터

구조체를 가리키는 포인터 변수

typedef struct vector {
	double x;
    double y;
} vector;

vector a = { 2.0, 3.0 };
vector* ps = &a;

(*ps).x = 4.0;
ps->x = 5.0;	// (*ps).x 와 ps->x는 완전 동치

함수 포인터

함수를 가리키는 포인터 변수
함수 원형과 유사하게 선언하면 된다.

int add(int a, int b);
=> int (*pf)(int, int);

void func(char c);
=> void (*pf)(char);

struct vector cross_product(struct vector v1, struct vector v2);
=> struct vector (*pf)(struct vector, struct vector);

함수도 주소를 가지므로 함수 포인터에 정의한 함수 이름을 대입하면 함수 포인터가 곧 함수가 된다.
물론 double add(double x, double y)같은 함수가 char (*pf)(int)같은 함수 포인터에 대입되지는 않고, 오직 double (*pf)(double, double)에만 대입된다.

int add(int a, int b) {
	return a + b;
}

int (*pf)(int, int);
pf = add;	// pf와 add의 인자, 자료형이 모두 일치하기 때문에 대입이 성립한다.

printf("%d", pf(3, 4));	// pf(3, 4) == add(3, 4) == 7

---

포인터의 응용

포인터 배열

포인터들을 원소로 가지는 배열

int a = 10, b = 20, c = 30, d = 40, e = 50;
int* pa[5] = { &a, &b, &c, &d, &e };

문자열들을 원소로 가지는 배열을 만들 때 사용한다.
"hello world"와 같은 문자열들의 자료형은 const char*로, 모든 문자열은 사실 char형 포인터이기 때문에 배열의 원소로 문자열을 넣는 것은 원소에 char형 포인터를 넣는 것과 같기 때문에 포인터 배열을 사용한다.

char* strs[3] = { "hello world", "pointer", "array" };

for (int i = 0; i < 3; ++i)
	printf("%s\n", strs[i]);

// hello world
// pointer
// array

함수 포인터 배열

함수 포인터를 원소로 가지는 포인터 배열

int (*pf)(int, int);	// 함수 포인터 선언은 이렇게
int (*pf[N])(int, int);	// 함수를 N개 가지는 함수 포인터 배열은 이렇게 선언한다

int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int mul(int a, int b) { return a * b; }
int div(int a, int b) { return a / b; }

// 선언 1
int (*pf[4])(int, int) = { add, sub, mul, div };

// 선언 2
int (*pf[4])(int, int);
pf[0] = add;
pf[1] = sub;
pf[2] = mul;
pf[3] = div;

printf("7 + 2 = %d\n", pf[0](7, 2));	// pf[0] == add
printf("7 - 2 = %d\n", pf[1](7, 2));	// pf[1] == sub
printf("7 * 2 = %d\n", pf[2](7, 2));	// pf[2] == mul
printf("7 / 2 = %d\n", pf[3](7, 2));	// pf[3] == div

// 7 + 2 = 9
// 7 - 2 = 5
// 7 * 2 = 14
// 7 / 2 = 3

다중 포인터

포인터는 주솟값을 가지며 그 주솟값은 어느 한 메모리를 가리킨다. 가리키는 이 메모리가 포인터라면 이 포인터는 이중 포인터가 된다. 이를 확장해보면 n중 포인터도 충분히 가능하다.

int x = 3;
int* px;
int** ppx;	// 2중 포인터

ppx = &px;	// ppx는 px를 가리킨다.
px = &x;	// px는 x를 가리킨다. 즉, ppx->px->x

printf("%d %d %d\n", x, *px, **ppx);	// 3 3 3

*px = 4;
printf("%d %d %d\n", x, *px, **ppx);	// 4 4 4

2010년 이후 대부분의 전자기기는 64비트 운영체제를 사용하고 있다. 이 말은 컴퓨터 메모리의 주솟값이 64비트 크기라는 것이고, 1바이트 = 8비트이므로 64비트는 8바이트이다.

즉, char는 1바이트, int는 4바이트, double은 8바이트를 가지듯이, 주솟값인 자료형*은 8바이트의 용량을 가진다.

포인터의 연산은 역참조값의 자료형 크기만큼 건너뛰면서 연산하는데, 2중포인터는 역참조값이 (1중)포인터이므로 2중포인터의 연산은 8씩 더해진다. (물론, 64비트 운영체제에서의 얘기고 32비트면 4씩 더해진다.)

int x = 3;	// 주소 100
int* px = &x;	// 주소 1000
int** ppx = &px;	// 주소 10000

printf("%u %u\n", ppx, ppx + 1);	// 1000 1008
printf("%u %u\n", px, px + 1);	// 100 104

연결 리스트

node라는 기본 단위를 가지며 주솟값에 의해 물고 물어지는 구조를 가진 자료구조

구조의 이해

왜 node가 포인터를 사용해야 하는지 납득할 필요가 있다. node가 아래와 같은 형태를 가졌다고 해보자.

node {
  int data;
  node next;
}	// 실제로는 작동하지 않는 문법, 그저 읽기 편하게 만든 유사 코드다.

node a;
a.data = 3;

정의했듯 a.next도 a처럼 node 자료형이다. 마찬가지로 (a.next).next도 node이다. 그렇다면 여기서 약간의 장난을 쳐볼 수 있다.

(a.next).data = 4;
((a.next).next).data = 5;
(((a.next).next).next).data = 6;
...

이렇게 하면 배열보다 훨씬 좋은 무한히 이어지게 할 수 있는 무언가를 만들 수 있을 것으로 보인다. 하지만 이는 작동하지 않는다. 이유라고 한다면 node를 선언할 때 node를 사용했기 때문이다.

node의 정의에 node가 들어갔다는 건 순환 논리이므로 오류가 발생한다. 그렇지만 node*를 사용하면 이름에 node가 들어가는 것 뿐이지 사실은 주솟값을 사용하는 것이므로 이 논리 오류를 회피할 수 있다.

그래서 우리는 node를 이렇게 정의한다:

struct node {
	int data;
    struct node* next;
};

// typedef로 struct 키워드를 제거해주면
typedef struct node {
	int data;
    struct node* next;
} node;

그럼 위에서 장난친 것을 새로 만든 node로 구현해보자.
c언어에는 구조체 포인터의 멤버 변수(구조체를 정의할 때 포함시킨 원소들을 멤버 변수라고 부른다.)에 접근하는 -> 연산자가 있다.
아까와 마찬가지로 a도, a->next도, (a->next)->next도 node* 자료형이다. 즉, 아까 코드의 모든 .을 ->으로 바꾸기만 해도 작동한다.

node* a;
a->data = 3;
(a->next)->data = 4;
((a->next)->next)->data = 5;
(((a->next)->next)->next)->data = 6;
...

점점 데이터가 많아질수록 값을 뒤에 연달아서 추가하고 싶다고 ->를 여러 번 쓸 수는 없다. 이를 루프를 통해 일괄적으로 처리해주고 싶고, 아예 데이터를 추가하는 함수를 만들어 더 쉽게 사용하고 싶다.

연결 리스트 구현

연결 리스트의 첫 번째 노드를 관례적으로 head라고 붙이는 경향이 있다. 우리도 앞으로 그렇게 사용한다.

연결 리스트의 맨 마지막 데이터에 도달하는 방법은 다음과 같다. 마지막 노드의 next는 NULL일 것이라는 가정 하에서 만들어졌다. (NULL도 포인터이며, 0을 가리킨다. 주로 가리키는게 없는 포인터를 초기화할 때 사용한다.)

node* tmp = head;
while (tmp->next != NULL)
	tmp = tmp->next;

마지막 노드를 이을 노드를 만들어 맨 끝에 '매달아'보자. a라는 데이터를 뒤에 넣기 위해 맨 끝에 매달릴 노드 p는 다음과 같이 만든다.

int a = 3;	// 연결 리스트의 마지막에 삽입할 데이터

node to_add;
to_add.data = a;

node* p = (node*)malloc(sizeof(node));
*p = to_add;	// p라는 구조체 포인터에 3이라는 a의 값을 저장함
p->next = NULL; // 연결 리스트의 마지막 노드의 next는 NULL이 돼야하므로 미리 초기화

이제 두 코드를 합쳐서 맨 끝 노드에 맨 끝에 매달릴 노드를 붙여보자.

// 넣을 데이터
int a = 3;

node to_add;
to_add.data = a;

// 맨 끝에 붙일 노드인 p 만들기
node* p = (node*)malloc(sizeof(node));
*p = to_add;	
p->next = NULL;

// 연결 리스트의 맨 끝까지 오기
node* tmp = head;
while (tmp->next != NULL)
	tmp = tmp->next;
    
// 맨 끝에 p 붙이기
tmp->next = p;

함수화시키면 다음과 같다. (외부 함수에서 지역 변수인 head의 값을 바꿔야 하므로 주소 호출을 사용해야 한다. 그래서 인자로 이미 node*인 head에 포인터를 하나 더 붙여서 node**의 자료형으로 끌고 왔다. 이해가 안되면 그냥 위의 함수화 전 코드의 head를 *head로 바꾸면 완전 동일하다.)

void insert(node** head, node to_add)
{
	node* p = (node*)malloc(sizeof(node));
    if (p == NULL) return;	// 동적할당이 실패했을 때의 대비책, 관례 상의 코드이다.
    *p = to_add;
    p->next = NULL;
    
    node* tmp = *head;
    while (tmp->next != NULL)
    	tmp = tmp->next;
    
    tmp->next = p;
}

int a = 3;
node to_add;
to_add.data = 3;

node* head = NULL;	// 원래 끝 노드의 next가 NULL인데 노드가 없으니 head가 NULL
insert(&head, to_add);	// 오류!

이렇게 하면 사실 작동하지 않는다. 연결 리스트에 노드가 1개 이상 존재할 때는 이 함수로 작동이 되지만 노드가 없는 첫 삽입의 경우에는 head가 NULL이므로 NULL->next나 NULL->data같은 것은 정의가 되지 않으므로 오류가 발생한다.

따라서 head가 노드가 있는지 없는지를 조건 분기해서 함수를 구현해야 한다.

void insert(node** head, node to_add)
{
	node* p = (node*)malloc(sizeof(node));
    if (p == NULL) return;
    *p = to_add;
    p->next = NULL;
    
    if (*head == NULL) 	// head에 노드가 없는 경우
    {	
    	*head = p;
    }
    else				// head에 노드가 1개 이상 있는 경우
    {	
    	node* tmp = *head;
	    while (tmp->next != NULL)
    		tmp = tmp->next;
    
    	tmp->next = p;
    }
}

연결 리스트에 어떤 값이 저장되어있는지 확인하기 위해서 출력 함수도 구현해야한다. 마지막 노드의 next가 NULL이므로 그 전까지 data를 쭉 출력해주면 된다.

void print(node* head)
{
	for (node* tmp = head; tmp != NULL; tmp = tmp->next)
    	printf("%d\n", tmp->data);
}

사용해보자.

int main()
{
	node* head = NULL;
    node to_add;
    
    to_add.data = 3;
    insert(&head, to_add);
    
    to_add.data = 4;
    insert(&head, to_add);
    
    to_add.data = 5;
    insert(&head, to_add);
    
    print(head);
}

3
4
5

연결 리스트에 제대로 값이 매달린 것을 볼 수 있다.