혹시나 문제가 된다면 바로 비공개 처리하겠습니다. 지적이나 댓글 환영합니다!
이번 포스팅에서는 보너스 파트의 함수를 구현해보았다. 보너스 파트는 연결리스트(랑크드리스트)를 이용한 기본적인 기능을 구현한 함수들을 구현하였다. 이후에도 많이 사용하게 될 것 같다.
참고로, 내가 정의한 libft.h 헤더에는 <unistd.h>와 <stdlib.h>가 include 되어있다. 따라서 libft.h를 호출하면, 따로 정의하지 않고도 <unistd.h> 에 정의된 size_t 타입과 <stdlib.h>의 malloc/free를 사용할 수 있다. 또한 <unistd.h>에 있는 write 함수 또한 사용할 수 있다. 또한 t_list 구조체가 정의되어 있어 보너스 함수 구현에 이를 사용하였다.
* 연결리스트란 무엇인가?
위키 백과의 정의 :
연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다
|
1
2
3
4
5
6
|
typedef struct s_list
{
void *content;
struct s_list *next;
} t_list;
|
cs |
위의 코드는 libft 에서 사용된 단일 연결리스트 구조체의 선언 코드이다. 1개의 연결리스트 구조체를 1개의 노드라고도 한다.
기본적인 노드의 구조는 (단일 연결리스트), 현재 노드의 내용물을 담는 변수(content)와 다음 노드의 주솟값을 갖는 포인터 변수(next) 총 2개로 이루어져있다.
한개의 노드에 다음 노드의 주소를 저장하고, 그 다음 노드에는 그 다음 노드의 주소를 저장하는 식으로 줄줄이 비엔나 소세지처럼 이어진다. 따라서 한개의 노드로부터 다음 노드의 주솟값들을 계속 참조하여 다음 노드로 이동할 수 있다.
그렇다면, 연결리스트를 쓰는 이유는 무엇일까?
기본적인 배열은 정적 할당과 동적 할당으로 나누어진다. 어느 쪽이든, 초기에 할당된 이후에, 연속된 공간의 메모리를 늘려 내용물을 더 저장하거나 원하는 위치의 내용물을 삭제하는 과정들이 자유롭지 않다. 정적 할당의 경우는 거의 불가능하다고 보면 된다. 동적할당에서도 저런 처리를 하려면 복잡한 과정을 거쳐야한다. (예를 들어, "abcd"에서 "bc"를 삭제하고 "ad"라는 문자열을 만드려면, 새로 메모리를 할당하고, 거기에 a와 d만 복사하여 새로운 문자열을 생성해야한다. 그리고 기존 메모리는 해제(free)해줘야한다)
그러나 연결리스트는 다르다. 연결리스트의 어느 곳에나 자유롭게 새로운 노드를 끼워넣거나 기존의 노드를 삭제할 수 있다. 따라서 내용의 수정과 생성/삭제가 유연하게 이루어질 수 있다. 필요시에만 메모리를 할당하기 때문에, 메모리 누수가 발생하지 않는 장점도 있다.
그러한 과정이 어떻게 가능한 지는 다음의 구현 예시 코드들을 통해 더욱 잘 이해할 수 있을 것이다.
(1) ft_lstnew : 새로운 노드를 생성
- 구현 코드 예시 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include "libft.h"
t_list *ft_lstnew(void *content)
{
t_list *lst;
lst = malloc(sizeof(t_list));
if (!(lst))
return (0);
lst->next = 0;
lst->content = content;
return (lst);
}
|
cs |
- malloc을 통해 t_list의 사이즈만큼 메모리를 할당해준다 (malloc 실패 시 0 리턴)
- 할당해준 노드의 next를 0으로 초기화하고, 현재 노드의 content 포인터 변수에는 매개변수로 받은 content의 포인터를 할당한다.
(2) ft_lstsize : 연결리스트의 사이즈 구함
- 구현 코드 예시 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include "libft.h"
int ft_lstsize(t_list *lst)
{
int len;
len = 0;
while (lst)
{
len++;
lst = lst->next;
}
return (len);
}
|
cs |
- lst = lst -> next를 통해, 다음 노드의 주소를 현재 노드에 저장하여, 다음 노드로 이동한다.
- lst가 마지막 노드에 도달하면 마지막 노드의 next 값은 0으로 초기화 된 채로 남아있으므로, 다음 loop로 넘어가면서 while문에서 빠져나오게 된다 (lst == 0이 되므로)
- 다음 노드로 이동할 수 있는 총 횟수가 연결리스트의 총 길이가 된다.
(3) ft_lstlast : 연결리스트의 마지막 노드 구함
- 구현 코드 예시 :
|
1
2
3
4
5
6
7
8
9
10
|
#include "libft.h"
t_list *ft_lstlast(t_list *lst)
{
if (!(lst))
return (0);
while (lst->next)
lst = lst->next;
return (lst);
}
|
cs |
- lst 가 NULL일 경우, 마지막 노드가 없으므로 0을 리턴한다.
- lst = lst -> next를 통해, 다음 노드의 주소를 현재 노드에 저장하여, lst -> next 가 NULL이 될 때까지 다음 노드로 이동한다.
마지막 노드에 저장된 다음 노드의 주소값은 0이기 때문이다.
- 마지막 노드를 찾았다면 해당 노드를 리턴한다.
(4) ft_lstadd_front : 연결리스트의 앞부분에 새로운 노드 추가
- 구현 코드 예시 :
|
1
2
3
4
5
6
7
8
|
#include "libft.h"
void ft_lstadd_front(t_list **lst, t_list *new)
{
new->next = (*lst);
(*lst) = new;
}
|
cs |
- new의 다음 노드 주소로, 주어진 연결리스트(lst)의 첫 노드의 주소를 저장한다.
- 주어진 연결리스트의 첫 노드의 시작 주소를 new의 주소로 갱신한다.
(5) ft_lstadd_back : 연결리스트의 뒷부분에 새로운 노드 추가
- 구현 코드 예시 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include "libft.h"
void ft_lstadd_back(t_list **lst, t_list *new)
{
t_list *lst_ptr;
if (*lst == NULL)
{
(*lst) = new;
return ;
}
lst_ptr = (*lst);
while (lst_ptr->next)
lst_ptr = lst_ptr->next;
lst_ptr->next = new;
}
|
cs |
- 주어진 노드가 NULL이면 해당 노드에 new의 주소를 할당해 준 뒤 함수를 종료한다.
- 그렇지 않으면, 마지막 노드가 발견될 때까지 노드의 위치를 이동한 후, 마지막 노드의 next에 new의 주소를 할당해준다.
참고 자료 출처 :
'IT > 42Seoul' 카테고리의 다른 글
| malloc/calloc 관련 정리 (0) | 2021.05.30 |
|---|---|
| [Libft] C 언어 라이브러리 구현_BONUS_보너스 함수 구현2 (0) | 2021.05.30 |
| Makefile 정리2 (0) | 2021.05.25 |
| Makefile 정리1 (0) | 2021.05.25 |
| TIP : 코드 리뷰 잘 하는 법 (0) | 2021.05.24 |