1. 포인터 복습
int main(void)
{
int *x;
int *y;
x = malloc(sizeof(int));
*x = 42;
*y = 13;
}위 코드는 에러가 발생한다.
그 이유가 무엇일까?
이유를 설명하기전에 코드를 설명하면
int *x; 는 정수를 가리키는 포인터 변수를 만든다.
malloc은 메모리를 할당하는 역할을 하며 할당하고 싶은 크기를 유일한 인자로 받는다.
sizeof(int)로 4byte 공간을 요청하여 할당한 메모리 영역의 첫번째 주소를 반환한다.
x = 42;에서 ""는 역참조 연산자로 x가 담고있는 주소로 가서 값에 42를 넣는다.
이제 버그가 발생한 이유가 나온다.
*y = 13;에서 y는 역참조할 메모리가 없다.
malloc을 통해서 메모리가 할당되지않았기 때문이다.
위 코드를 약간 바꾸면
int main(void)
{
int *x;
int *y;
x = malloc(sizeof(int));
*x = 42;
y = x;
*y = 13;
}이렇게 하면 잘 돌아간다.
y = x;를 통해서 y가 x와 동일한 주소를 가리키고 그 값을 13으로 덮어씌운다.
이 결과 x와 y가 함께 가리키는 곳이 13이 되므로 42는 사라진다.
2. 배열의 크기 조정
배열은 처음 만들 때 크기를 지정합니다. 즉, 고정된 메모리 덩어리입니다.
그런데 만약 배열의 크기를 늘리고 싶다면??
옆에 그냥 한바이트 더 할당하면 안되나 생각할텐데 그것은 불가능합니다.
왜냐하면 해당 배열이 할당된 메모리 주변에도 이미 다른 byte들이 둘러싸고있기 때문입니다.
방법은 새롭게 메모리를 할당하여 기존의 메모리에 있던 값을 새롭게 할당한 메모리에 복사하고 기존의 메모리는 free해주면 됩니다.
이때문에 배열에 값을 추가해주는 과정의 시간복잡도는 O(n)입니다.
- 배열에서 값을 탐색하는 경우는 이진탐색을 사용할 수 있어 O(logn)이 소요됩니다.
이를 코드로 나타내면 다음과 같습니다.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
//int 자료형 3개로 이루어진 list 라는 포인터를 선언하고 메모리 할당
int *list = malloc(3 * sizeof(int));
// 포인터가 잘 선언되었는지 확인
if (list == NULL)
{
return 1;
}
// list 배열의 각 인덱스에 값 저장
list[0] = 1;
list[1] = 2;
list[2] = 3;
//int 자료형 4개 크기의 tmp 라는 포인터를 선언하고 메모리 할당
int *tmp = malloc(4 * sizeof(int));
if (tmp == NULL)
{
return 1;
}
// list의 값을 tmp로 복사
for (int i = 0; i < 3; i++)
{
tmp[i] = list[i];
}
// tmp배열의 네 번째 값도 저장
tmp[3] = 4;
// list가 가리키고 있던 메모리를 초기화
free(list);
// list가 tmp와 같은 곳을 가리키도록 지정 // tmp가 담고있는 주소를 list도 담도록 만든다.
list = tmp; // 원래 포인터의 이름을 사용하기 위해서
// 새로운 배열 list의 값 확인
for (int i = 0; i < 4; i++)
{
printf("%i\n", list[i]);
}
// list의 메모리 초기화
free(list);
}
< + 포인터 이름 옆에 대괄호를 쓰면 메모리 덩어리의 대괄호 안의 숫자의 바이트(4byte단위)로 이동합니다. >
- 메모리가 부족한 경우 포인터는 NULL을 가리키게 되므로 예외처리를 해줍니다.
코드를 보면 알겠지만 굉장히 귀찮고 할일을 많이 주는 코드입니다.
이 코드를 realloc을 통해서 짧게 만들 수 있습니다.
realloc은 기존 배열에서 새로운 배열로 데이터를 복사하는 것으로
stdlib.h에서 사용할 수 있습니다.
// tmp 포인터에 메모리를 할당하고 list의 값 복사
int *tmp = realloc(list, 4 * sizeof(int));
if (tmp == NULL)
{
return 1;
}
// list가 tmp와 같은 곳을 가리키도록 지정
list = tmp;이렇게 realloc의 첫번째 인자에 복사하고 싶은 포인터를 넣어주고 size를 새로 지정하면 됩니다.
배열은 본질적으로 메모리의 덩이리입니다!
3. 연결리스트 : 도입
배열은 접근이 빠르고 바이너리 검색에 적용할 수 있다는 장점이 있습니다.
그러나 고정된 메모리 덩어리이기에 배열의 크기보다 더 큰 값을 넣고 싶다면 새롭게 메모리를 할당해야합니다.
귀찮죠. 그리고 캔버스 같은 메모리를 효율적으로 사용할 수 없습니다.
그래서 배열이외에도 여러 자료구조가 존재합니다.
자료구조에는 메모리에 정보를 각기 다른 방법으로 저장하는 여러 방법들이 있습니다.
그중에서도 지금 설명할 자료구조는 연결리스트입니다.
연결리스트
연결리스트는 메모리 덩어리 여러 개를 포함한 데이터 구조로 각각 포인터로 연결되어 있습니다.
연결리스트는 숫자 뿐 아니라 다음 메모리 덩어리를 가리키는 포인터를 포함하기에 2배의 메모리가 필요합니다. 마지막 포인터에는 NULL (16진법 0)을 넣어 리스트의 끝을 알립니다.
관례적으로 다음 메모리 덩어리를 가리키는 포인터를 next라고 부릅니다.
이를 코드로 만들려면
typedef struct
{
int number;
node *next;
}
node;이렇게 number와 다음 node를 가리키는 포인터가 있으면 될것같지만 안됩니다.
왜냐하면 컴퓨터는 node *next;여기에서 node가 뭔지를 몰라요
다음 줄로 와서 아~ 이게 node구나 알기때문이죠
그래서 이렇게 struct를 만들어야합니다.
typedef struct node
{
int number;
struct node *next;
}
node;struct node *next;를 통해 node구조체를 가리키도록 정의합니다.
이 node라는 struct는 숫자와 포인터가 있습니다.
그리고 이 포인터는 node 구조체를 가리키도록 정의되어있습니다.
4. 연결 리스트 : 코딩,시연
n->number = 1;
(*n).number = 1;n이 node의 크기만큼 할당한 공간의 주소를 가리키고 있는 node형 포인터라면
위 두줄의 코드는 의미가 같다.
n이 가리키는 노드의 number값을 변경하는 것이다.
이러한 연결 리스트를 이용해 리스트를 동적으로 추가할 수 있다.
크기를 조절할 수 있다는 것이 연결리스트의 장점이다.
BUT. 이를 통해 잊어버린 것은 임의접근이다.
이진 탐색은 임의접근을 필요로 하니 이진 탐색 또한 불가하다.
즉, 탐색에는 O(n)이 소요된다.
<전체 코드> :
#include <stdio.h>
#include <stdlib.h>
//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
//node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다.
int number;
//다음 node의 주소를 가리키는 포인터를 *next로 지정합니다.
struct node *next;
}
node;
int main(void)
{
node *list = NULL;
// 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킵니다.
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
//구조체에 값 넣기
n->number = 1;
n->next = NULL;
// 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꿔 줍니다.
list = n;
// 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당합니다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 2;
n->next = NULL;
// list가 가리키는 것은 첫 번째 node입니다.
//이 node의 다음 node를 n 포인터로 지정합니다.
list->next = n;
// 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장합니다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 3;
n->next = NULL;
// 현재 list는 첫번째 node를 가리키고, 이는 두번째 node와 연결되어 있습니다.
// 따라서 세 번째 node를 더 연결하기 위해 첫 번째 node (list)의
// 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정합니다.
list->next->next = n;
// 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력합니다.
// 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료 조건이 됩니다.
for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
printf("%i\n", tmp->number);
}
// 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해줍니다.
while (list != NULL)
{
node *tmp = list->next;
free(list);
list = tmp;
}
}