[Libft] Bonus

libft 프로젝트의 bonus part 함수들을 구현하면서 메모했던 내용들을 정리해두었다. 이 라이브러리의 함수들은 꾸준히 업데이트 되고 있기 때문에 가장 최신의 코드는 여기 깃헙저장소를 참고...

libft 프로젝트의 bonus part 함수들을 구현하면서 메모했던 내용들을 정리해두었다. 이 라이브러리의 함수들은 꾸준히 업데이트 되고 있기 때문에 가장 최신의 코드는 여기 깃헙저장소를 참고...

1. ft_lstnew

Prototype

t_list *ft_lstnew(void *content);

Parameters

1. The content to create the new element with.

Return value

The new element.

External functs.

malloc

Description

Allocates (with malloc(3)) and returns a new element. The variable ’content’ is initialized with the value of the parameter ’content’. The variable ’next’ is initialized to NULL.

    #include "libft.h"

    t_list      *ft_lstnew(void *content)
    {
        t_list  *new; 

        new = (t_list *)malloc(sizeof(t_list));
        if (new == NULL)
            return (NULL);
        new->content = content;
        new->next = NULL;
        return (new);
    }

새로운 노드 생성하는 함수

• new 리스트의 next 변수(다음 노드의 포인터)는 NULL로 초기화.

• 생성하는 함수일 뿐, 추가하거나 삽입하는 함수는 아님 !! 그래서 아래와 같은 의문이 들었지만 쓸데없는 걱정이었다.

  • 원래 NULL을 가리키던 마지막 요소는 어떻게 되는 걸까?

  • 두 개의 리스트가 NULL을 가리키는 것 아닌가?

• 노드의 생성, 추가, 삽입은 개념이 다 다르다.

  • 추가는 새로 만든 노드를 연결리스트의 제일 마지막에 붙이는 작업

  • 삽입은 노드와 노드 사이에 새로운 노드를 삽입하는 작업

  • 참고 : https://junistudy.tistory.com/2
• malloc으로 메모리를 할당해주는 이유

  • malloc없이 새로운 노드를 만들게 되면, ft_newlst 함수가 종료되면서 반환되는 new 노드는 stack에서 사라지게 된다.

  • malloc을 하면 힙영역에 할당되고, 그래야 함수가 종료돼도 메모리 상에 남아 t_list *new 가 할당 받은 메모리를 가리킬 수 있게 된다.

  • 메모리 구조 참고

2. ft_lstadd_front

Prototype

void ft_lstadd_front(t_list **lst, t_list *new);

Parameters

1. The address of a pointer to the first link of a list.

2. The address of a pointer to the element to be added to the list.

External functs.

None

Description

Adds the element ’new’ at the beginning of the list.

    #include "libft.h"

    void    ft_lstadd_front(t_list **lst, t_list *new)
    {
        if (lst == NULL || new == NULL)
            return ;
        new->next = *lst;
        *lst = new;
    }

리스트 제일 앞에 새 리스트 추가하는 함수

1. 새 노드의 다음 주소를 head로 설정

2. head를 새 노드로 설정

3. 연결 리스트 구현시 이중 포인터를 사용하는 이유

   • 단일 연결리스트에서 삽입과 삭제를 통해 head 포인터의 값을 변화시킬 수 있다.

   • 이때, 호출 함수의 포인터변수가 참조하는 객체를 피호출 함수에서 바꾸고자 할 경우 이중 포인터를 사용하면 된다.

4. t_list **lst 는 t_list 포인터(lst)의 주소를 가리키는 포인터다.

   • t_list **lst 변수가 담고있는 값은 t_list *의 주소

   • t_list ** lst가 담고 있는 t_list * 의 주소는 어떤 리스트의 첫번째 주소

   • 즉, *lst는 head의 주소

5. 의문점

   원래 head는 데이터가 없으니, head노드가 중간 노드가 됐을때 데이터도 따로 넣어줘야할 것 같다. 그래서 이 함수는 잘 안 쓰지 않을까? 제일 앞에다 새 노드를 추가하는 일보다는 제일 뒤에 추가하는 경우가 더 많은 것 같다.

3. ft_lstsize

Prototype

int ft_lstsize(t_list *lst);

Parameters

1. The beginning of the list.

Return value

Length of the list.

Description

Counts the number of elements in a list.

    #include "libft.h"

    int     ft_lstsize(t_list *lst)
    {
        int size;

        size = 0;
        while (lst != NULL)
        {
            lst = lst->next;
            size++;
        }
        return (size);
    }

- (lst++) == (lst = lst->next)

4. ft_lstlast

Prototype

t_list *ft_lstlast(t_list *lst);

Parameters

1. The beginning of the list.

Return value

Last element of the list.

Description

Returns the last element of the list.

    #include "libft.h"

    t_list      *ft_lstlast(t_list *lst)
    {
            if (lst == NULL)
                    return (NULL);
        while (lst->next != NULL)
                    lst = lst->next;
        return (lst);
    }

5. ft_lstadd_back

Prototype

void ft_lstadd_back(t_list **lst, t_list *new);

Parameters

1. The address of a pointer to the first link of a list.

2. The address of a pointer to the element to be added to the list.

Description

Adds the element ’new’ at the end of the list.

    #include "libft.h"

    void    ft_lstadd_back(t_list **lst, t_list *new)
    {
        t_list *last;

        if (lst == NULL || new_node == NULL)
            return ;
        if (*lst == NULL)
        {
            *lst = new_node;
            return ;
        }
        last = ft_lstlast(*lst);
        new->next = last->next;
        last->next = new;
    }

리스트의 마지막에 새 노드를 추가하는 함수

1. new의 다음 주소는 원래 last의 다음 주소( = NULL) 로 설정

2. last의 다음 주소가 new를 가리키도록 변경

3. ft_lstlast();` 함수의 인자로 lst를 보내야하는지 *lst를 보내야 하는지 헷갈렸다.

   • lstlast 함수는 파라미터로 t_list * 즉, 첫 번째 요소의 주소를 받는다.

   • 이렇게 생각하면 조금 쉬워진다.

     ft_lstadd_back 함수에서 우리가 받은 인자의 자료형은 t_list *이고, (t_list ) = t_list 이기 때문에 lst 를 인자로 보내면 된다.

4. *lst == NULL 과 lst == NULL 의 차이

   • *lst는 lst의 첫번째 주소, 즉 헤드의 주소를 의미한다. 헤드가 비었다는 건,

     *lst는 빈 리스트 라는 뜻!

   • lst == NULL은 리스트 자체가 존재하지 않는다 뜻!

6. ft_lstdelone

Prototype

void ft_lstdelone(t_list *lst, void (*del)(void *));

Parameters

1. The element to free.

2. The address of the function used to delete the content.

External functs.

free

Description

Takes as a parameter an element and frees the memory of the element’s content using the function ’del’ given as a parameter and free the element. The memory of ’next’ must not be freed.

    #include "libft.h"

    void    ft_lstdelone(t_list *lst, void (*del)(void *))
    {
        if (lst == NULL)
            return ;
        del(lst->content);
        free(lst);
    }

1. del 함수로 content 변수 free

2. lst 요소 free

3. 의문점1 : The memory of ’next’ must not be freed ?

   • next 변수가 가리키는 다음 노드는 지우지 말라는 뜻.

   • 연결 해주는 작업은 이 함수가 끝난 뒤 따로 처리해줘야 할듯.

4. 의문점2 : 그냥 free(lst) 만 하면 안되는 이유는?

   • content 변수는 주소만 담고 있어서 그 주소가 가리키는 값까지 삭제를 해줘야 하는데, free(lst)를 한 후에는 lst->content 로 접근이 불가능하다. 그래서 content를 먼저 free해주고 그 다음에 lst를 free 해줘야 한다.

   • 순서 중요!

7. ft_lstclear

Prototype

void ft_lstclear(t_list **lst, void (*del)(void *));

Parameters

1. The adress of a pointer to an element.

2. The adress of the function used to delete the content of the element.

External functs.

free

Description

Deletes and frees the given element and every successor of that element, using the function ’del’ and free(3). Finally, the pointer to the list must be set to NULL.

    #include "libft.h"

    void        ft_lstclear(t_list **lst, void (*del)(void *))
    {
        t_list  *curr;
        t_list  *next;

        curr = *lst;
        while (curr)
        {
            next = curr->next;
            ft_lstdelone(curr, del);
            curr = next;
        }
        *lst = NULL;
    }

연결 리스트 전체 노드 데이터를 삭제하는 함수

1. curr 을 삭제하기 전에 next에 curr의 다음 노드 입력

2. curr 에 할당된 메모리 해제.

3. curr을 next 초기화.

4. lst는 빈 리스트 -> *lst = NULL; (안하면 쓰레기값)

5. next 말고 prev 변수를 만든 뒤에 prev를 삭제하는 방식도 가능할 것 같다.

   1. prev에 curr 기억

   2. curr = curr->next : curr은 다음 노드로 이동

   3. prev 메모리 해제

8. ft_lstiter

Prototype

void ft_lstiter(t_list *lst, void (* f)(void *));

Parameters

1. The adress of a pointer to an element.

2. The adress of the function used to iterate on the list.

Description

Iterates the list ’lst’ and applies the function ’f’ to the content of each element.

    #include "libft.h"

    void    ft_lstiter(t_list *lst, void (*f)(void *))
    {
        if (lst == NULL || f == NULL)
            return ;
        while (lst)
        {
            f(lst->content);
            lst = lst->next;
        }
    }

리스트를 반복하면서 특정 함수 적용시키는 함수.

9. ft_lstmap

Prototype

t_list *ft_lstmap(t_list *lst, void *(*f)(void * ), void (*del)(void *));

Parameters

1. The adress of a pointer to an element.

2. The adress of the function used to iterate on the list.

3. The adress of the function used to delete the content of an element if needed.

Return value

The new list. NULL if the allocation fails.

External functs.

malloc, free

Description

Iterates the list ’lst’ and applies the function ’f’ to the content of each element. Creates a new list resulting of the successive applications of the function ’f’. The ’del’ function is used to delete the content of an element if needed.

    #include "libft.h"

    t_list      *ft_lstmap(t_list *lst, void *(*f)(void *), void (*del)(void *))
    {
        t_list  *new_head;
        t_list  *new_next;
        t_list  *curr;

        if (lst == NULL || f == NULL || del == NULL)
            return (NULL);
        if ((new_head = ft_lstnew(f(lst->content))) == NULL)
            return (NULL);
        curr = new_head;
        lst = lst->next;
        while (lst)
        {
            if ((new_next = ft_lstnew(f(lst->content))) == NULL)
            {
               ft_lstclear(&new_head, del);
               return (NULL);
            }
            curr->next = new_next;
            curr = new_next;
            lst = lst->next;
        }
        return (new_head);
    }

• lst = lst->next 를 와일문 위에서, 와일문 안에서 두 번 쓴 이유

  lst->next가 NULL이었을 경우 와일문 진입 못하게 하기 위해서.

  • NULL 인데 와일문 진입했을 경우 -> return NULL;

  • NULL 이여서 와일문 진입 안 했을 경우 -> return (new_head) (헤드만 있는 연결 리스트)

• curr 임시 노드를 만든 이유.

  실제 new_head의 값이 new_next로 바뀌면 안돼서.