연결리스트
typedef struct s_list
{
char *content;
struct s_list *next;
} t_list;
t_list *head;
head = (t_list *)malloc(sizeof(t_list));
...
C
복사
연결리스트는 위와 같은 구조체들이 연결되어 있는 것을 뜻합니다. 각 구조체마다 다음에 연결된 구조체의 주소를 next에 저장하고 있음으로써 서로 연결될 수 있습니다. 예를 들어 위와 같은 head를 생성한 뒤 그 뒤로 노드를 붙여나가면 아래와 같은 구조가 될 것입니다.
구조체 이름 | head | node1 | node2 | node3 | node4 |
주소 | 0x00000000a | 0x00000000b | 0x00000000c | 0x00000000d | 0x00000000e |
content | “123” | “abc” | “a1c” | “2623” | “4242” |
next | 0x00000000b | 0x00000000c | 0x00000000d | 0x00000000e | NULL |
연결리스트의 끝은 해당 구조체의 next가 NULL 포인터를 가리킬 때 끝이라고 판단합니다.
이중포인터
이중포인터는 흔히 2차원 배열에서 많이 사용합니다. 일반 포인터를 먼저 살펴보면 쉽게 이해할 수 있습니다.
char *str = "abc";
C
복사
변수 | str | str[0] | str[1] | str[2] | str[3] |
주소 | 0x000000001 | 0x00000000q | 0x00000000w | 0x00000000e | 0x00000000r |
content | 0x00000000q | ‘a’ | ‘b’ | ‘c’ | 0 |
포인터는 주소를 가리키는 변수이기 때문에 str 자체에는 str[0]의 주소값이 들어가있습니다. 그래서 만약 *을 붙이게 되면 0x00000000q에 있는 값을 불러와서 ‘a’를 출력하게 될 것입니다.
이중포인터도 마찬가지로 해당 주소값에 있는 내용을 불러오게 되는데 다만 길을 한 번 더 가야 할 뿐입니다.
char alpha = 'a';
char **head;
char *route;
route = α
head = &route;
C
복사
변수 | head | route | alpha |
주소 | 0x000000001 | 0x00000000q | 0x00000000@ |
content | 0x00000000q | 0x00000000@ | ‘a’ |
즉, 아래와 같은 결과를 볼 수 있습니다.
route = 0x00000000@ ‘a’
head = 0x00000000q
*head = 0x00000000@ ‘a’
연결리스트에 이중포인터가 왜 필요할까?
위에서 사용했던 구조체를 다시 가져오겠습니다.
typedef struct s_list
{
char *content;
struct s_list *next;
} t_list;
t_list *head;
head = (t_list *)malloc(sizeof(t_list));
...
C
복사
main 문에서 head는 항상 연결리스트에서 제일 첫 리스트를 가리키게 하려고 하고 우리는 새로운 리스트를 생성해서 제일 앞에다가 붙이는 함수를 만드려고 합니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct s_list
{
char *content;
struct s_list *next;
} t_list;
void newlst_front(t_list *head)
{
t_list *node;
printf("---------------------------\n");
printf("***Making new front node***\n");
node = (t_list *)malloc(sizeof(t_list));
if (node == NULL)
return ;
node->next = head;
printf("new node = %p\n", node);
printf("head = %p, node->next = %p\n", head, node->next);
head = node;
printf("new head = %p\n", head);
printf("---------------------------\n");
printf("*********FINISHED!*********\n");
printf("---------------------------\n");
}
int main(void)
{
t_list *head;
head = (t_list *)malloc(sizeof(t_list));
if (head == NULL)
return (-1);
printf("head = %p\n", head);
newlst_front(head);
printf("head = %p\n", head);
return (0);
}
C
복사
메인에서 head를 만들어 줬고 우리는 head를 newlst_front 함수로 넘겨서 새로운 node를 만들어서 작업해준 다음 head를 node로 바꿔줬습니다. 결과가 어떻게 나올까요?
1.
main 문에서 만든 head는 5840을 가리키고 있습니다.
2.
newlst_front 함수에서 새 node를 만들어 주었고 해당 노드는 5850을 가리키고 있습니다.
3.
node→next에 head가 들어갔는지 확인하고 head가 node를 가리키게 합니다.
4.
head가 정상적으로 바뀌었는지 확인해보니 5850 새로 만든 노드를 가리키고 있어서 함수를 빠져나옵니다.
여기까지는 정상적으로 된 것 같은데 막상 마지막 main 문에 나와서 head를 다시 출력해보니 여전히 5840을 가리키고 있는 것을 볼 수 있습니다. 왜 그럴까요?
같은 변수 이름에서 비롯된 오해?
lstnew_front로 head를 넘기면, 해당 함수에서도 똑같이 head라는 이름으로 멤버에 접근할 수 있습니다.
이는 두 head가 동일한 변수라는 오해를 불러올 수 있습니다. 사실 함수에서 인자를 받으면 해당 이름으로 변수를 만들어서 넘겨준 인자의 값을 넣어주게 됩니다.
위와 같이 같은 head의 이름을 가진 포인터 변수이지만 사실 둘은 별개의 변수이고 단지 같은 주소를 가리키고 있을 뿐입니다. lstnew_front 함수에서 새 node를 생성 후 head에게 node를 가리키게 하면 아래와 같이 됩니다.
그리고 해당 함수가 끝나면 해당 함수에서 선언된 변수들은 사라집니다.
만들어진 node는 동적 할당이 된 채로 프로그램이 종료될 때까지 떠돌게 됩니다...
이중포인터를 이용해서 head 수정
코드를 다음과 같이 수정합니다
#include <stdio.h>
#include <stdlib.h>
typedef struct s_list
{
char *content;
struct s_list *next;
} t_list;
void newlst_front(t_list **head)
{
t_list *node;
printf("---------------------------\n");
printf("***Making new front node***\n");
node = (t_list *)malloc(sizeof(t_list));
if (node == NULL)
return ;
node->next = *head;
printf("new node = %p\n", node);
printf("head = %p, node->next = %p\n", *head, node->next);
*head = node;
printf("new head = %p\n", *head);
printf("---------------------------\n");
printf("*********FINISHED!*********\n");
printf("---------------------------\n");
}
int main(void)
{
t_list *head;
head = (t_list *)malloc(sizeof(t_list));
if (head == NULL)
return (-1);
printf("head = %p\n", head);
newlst_front(&head);
printf("head = %p\n", head);
return (0);
}
C
복사
main 함수에서 head의 주소값을 넘겨주게 됩니다. 그렇게 되면 newlst_front에서 head는 아래처럼 됩니다.
이렇게 newlst_front에서 head가 main의 head의 주소값을 가리키게되고 우리는 *head를 통해 main의 head가 가리키는 포인터를 바꿀 수 있습니다.
코드에서 볼 수 있듯이 *head가 node를 가리키게 하고 함수가 종료되면 해당 함수내 변수는 사라집니다.
이렇게 되면 함수가 종료되었을 때 main에서 선언한 head가 가리키는 값이 정상적으로 변경되게 됩니다.
코드의 실행 결과는 아래와 같습니다.
단일 포인터를 사용했을 때는 main에서의 head가 처음 가리키든 5840을 newlst_front 함수가 끝나고도 여전히 가리켰었지만 이중포인터를 사용하게되면 정상적으로 5850을 가리키는 것을 확인할 수 있습니다.
이렇게 우리는 연결리스트를 사용할 때 상황에 따라 해당 구조체의 멤버에만 접근하는 경우와 해당 구조체를 가리키는 포인터 변수를 수정해야 될 경우를 판단하여 적절하게 이중포인터를 활용해야합니다.
