GET_NEXT_LINE - Bonus (연결리스트)
GET_NEXT_LINE - Bonus (연결리스트)
개요
이번에는 연결리스트를 활용한 풀이입니다. 연결리스트란 자료 구조의 하나로, 해당 과제에서는 파일 하나당 리스트를 하나씩 생성해서 그 리스트를 연결하는 방식으로 풀이하는 방법입니다. 포인터 배열과 달리, 파일 하나당 하나의 구조체를 갖게 되므로 매우 정당한 풀이라고 할 수 있습니다.
다만, 파일의 개수가 많으면 노드(구조체)를 생성할 때와 삭제할 때 탐색을 진행하면서 시간이 오래 걸릴 수 있다는 단점을 가지고 있습니다. 하지만 포인터 배열의 치명적인 단점을 갖지 않는다는 점에서 평가 진행 시, 디펜스에 취약한 점이 없는 풀이입니다.
앞서 소개했듯, 연결리스트로 풀 경우, 10개의 함수로 만들기 어려울 수도 있습니다. 하나의 함수는 하나의 기능만 수행해야 올바른 코드를 작성할 수 있지만, 여건이 안된다면 두 개의 역할을 하는 함수를 만들어 풀어보시고 나중에 줄여보세요. 풀이 구조를 잘 생각해 보시고 함수를 만들어 보시기 바랍니다.
목표
포인터 배열과 동일합니다.
구현 전 사전 지식
1. 연결리스트
1. 연결리스트
저는 라 피신에서 연결리스트를 학습하지 못하고 본 과정에 들어왔습니다. 물론 Libft 과제에서 보너스 파트를 풀어냈다면, 연결리스트 개념을 접할 수 있겠습니다마는, 그 조차 연결리스트의 첫 시작이었다면 연결리스트 풀이에 익숙하지 않을 수 있습니다. 따라서 연결리스트의 개념과 활용이 중요합니다.
구현
header
typedef struct s_list
{
파일 디스크립터 선언
문자열을 기억할 포인터 선언
다음 노드를 가리킬 포인터 선언
} t_list;먼저 헤더에 구조체를 선언해서 get_next_line에 쓸 수 있도록 합시다.
pseudo code
char *get_next_line(int fd)
{
반환할 문자열을 가리킬 포인터 선언
문자열을 할당할 포인터 선언
파일 정보를 저장할 노드 선언
연결리스트를 진행할 리스트 포인터 선언
if fd값을 탐색하여 fd에 해당하는 노드가 없다.
노드를 생성한다.
버퍼를 할당한다.
노드와 버퍼를 이용해서 파일을 읽고, 한 줄을 생성한다.
if 파일(노드)의 백업이 없다.
그 노드를 삭제하고, 연결리스트를 재연결한다.
한 줄을 반환한다.
}
char *read_file(t_list *node, char **buff)
{
read 함수의 반환 값을 확인할 변수 선언
while 읽을 수 있으면 읽는다.
read 함수를 실행한다.
if read 함수가 오류를 발생시키는지 확인한다.
에러 처리
읽은 버퍼를 문자열로 만든다.
노드의 백업에 버퍼를 덧붙인다.
if 한 줄이 완성할 수 있다.
while문을 빠져나온다.
버퍼를 해제한다. // 더 이상 버퍼를 사용하지 않는다.
if 한 줄을 완성할 수 있다.
한 줄을 반환한다.
널을 반환한다.
}
char *make_oneline(t_list *node)
{
줄바꿈문자의 위치를 저장할 변수
널문자의 위치를 저장할 변수
반환할 문자열 포인터 선언
반환 후 남은 문자열 포인터 선언
줄바꿈의 인덱스를 찾는다.
널문자의 인덱스를 찾는다
if 문자열이 줄바꿈문자로 끝났거나 널문자로 끝났다
반환할 문자열은 남은 전체 문자열이다.
반환 후 남은 문자열은 없다.
else
줄바꿈 문자까지 포함한 문자열이 반환할 문자열이다.
줄바꿈 문자 다음 문자부터 끝까지 남은 문자열이다.
노드의 백업을 반환 후 남은 문자열로 바꾼다.
반환할 문자열을 반환한다.
}
void del_fd_list(t_list **lst, t_list *node)
{
노드 탐색을 위한 포인터 선언
사라질 노드를 제외하고 남은 노드를 이어줄 포인터 선언
첫 노드 시작점을 저장한다.
while 연결리스트에서 노드를 탐색한다.
if next_fd를 통하여 노드를 찾았다.
반복문을 빠져나온다.
해당 노드를 삭제하기전에 next_fd값을 변수에 저장한다.
노드를 삭제한다
이전 노드와 next_fd를 잇는다.
}생략되어있는 함수가 많지만, 이런 방식으로 진행됩니다.
동료 평가
1. 본인이 작성한 연결리스트 풀이에서, 노드를 어떻게 다루는지 설명할 수 있어야 합니다.
2. 어떻게 노드를 생성하는지 노드를 삭제할 때는 어떻게 삭제하고 남은 노드를 연결하는지 등을 평가전에 되새겨 봅시다.
마치며
연결리스트는 동료 평가에서 본인이 작성한 코드를 잘 설명할 수 있다면 문제 없이 통과하실 수 있을 것입니다. gnl의 허점 없는 풀이를 원하신다면 시도해 보시길 바랍니다.
다음은 ft_printf 과제입니다.