Libft Bonus(연결리스트)

연결리스트

연결 리스트란 자료구조의 한 종류로 각각의 데이터들을 보관하고있는 변수들이 자신의 다음 노드를 가르키고 있는 자료구조를 의미한다 배열의경우 데이터가 메모리상에 순차적으로 존재하여 배열 중간에 값을 삽입하고 삭제하는것에 있어서 불편함이 있지만 연결 리스트의 경우 중간에 값을 삽입하거나 삭제하는등의 동작을 할때 연결된노드들의 주소값을 변경주는것으로 쉽게 할 수 있다는 장점이있다 단 특정 데이터를 참조할때 배열의경우 해당 idx번호만 알고있으면 바로 접근이 가능한것과 달리 연결리스트는 head부터 순회하면서 데이터를 확인해야되서 시간이 오래걸린다는 단점이있다 연결리스트의 종류에는 기본 단방향 연결리스트 부터 원형연결리스트 앞으로도 연결되어있지만 뒤로도 연결되있는 이중연결리스트 원형이중연결리스트등 종류가 다양하다 그중에서 이번 Libft Bonus과제에서는 가장 기본적인 단반향 연결리스트에 대해서 구현해본다.

구조

typedef struct s_list
{
	void			*content;
	struct s_list	*next;
}				t_list;

• content : void *형으로 어떤 type이 들어오든 data를 저장할 수 있다.
• next : 자신이 선언된 구조체와 같은 구조체를 포인터변수로 next를 지정해 자신의 다음 노드 주소값을 저장해놓는다.
  👀 노드 : 연결리스트가 가지고있는 다음 연결리스트의 주소를 노드라고 표현한다
  👀 헤드 : 연결리스트의 맨 앞부분을 head라고 표현한다
  👀 테일 : 연결리스트의 맨 끝부분을 tail이라고 표현한다

구현

• ft_lstnew : content를 매개변수로 받아 새로 할당한 연결리스트에 content 로 넣어주고 next노드를 널포인터로 초기화해준다

#include "libft.h"

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

	newnode = (t_list *)malloc(sizeof(t_list));
	if (newnode == 0)
		return (0);
	newnode->content = content;
	newnode->next = (void *)0;
	return (newnode);
}

• ft_lstadd_front : 연결리스트의 head와 새로 추가할 리스트를 매개변수로 받아서 연결리스트의 맨 앞쪽에 추가해준다.

#include "libft.h"

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

• ft_lstadd_back : 연결리스트의 head와 새로 추가할 리스트를 매개변수로 받아서 연결리스트의 맨 뒷쪽에 추가해준다.

#include "libft.h"

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

	if (*lst == (void *)0)
		*lst = new;
	else
	{
		temp = *lst;
		while (temp->next != (void *)0)
			temp = temp->next;
		temp->next = new;
	}
}

• ft_lstsize : 연결리스트의 head를 매개변수로 받아서 연결리스트의 총 길이를 반환해준다.

#include "libft.h"

int	ft_lstsize(t_list *lst)
{
	int		i;
	t_list	*temp;

	i = 1;
	if (lst == NULL)
		return (0);
	temp = lst;
	while (temp->next != (void *)0)
	{
		temp = temp->next;
		i++;
	}
	return (i);
}

• ft_lstlast : 연결리스트의 헤드를 매개변수로 받아서 연결리스트의 마지막 노드(tail)의 주소값을 리턴시켜준다

#include "libft.h"

t_list	*ft_lstlast(t_list *lst)
{
	t_list	*temp;

	if (lst == (void *)0)
		return (lst);
	temp = lst;
	while (temp->next != (void *)0)
	{
		temp = temp->next;
	}
	return (temp);
}

• ft_lstdelone : 연결리스트와 del함수를 매개변수로 받아 해당 연결리스트의 content에 del함수를 실행시킨 후 lst를 free해준다.

#include "libft.h"

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

• ft_lstclear : 연결리스트의 head와 del함수를 매개변수로 받아 head부터 tail까지 모든 연결리스트의 content에 del함수를 적용하고 lst를 free해준다

#include "libft.h"

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

	temp = *lst;
	if (*lst == (void *)0)
		return ;
	while (temp != (void *)0)
	{
		del (temp->content);
		*lst = temp->next;
		free (temp);
		temp = *lst;
	}
	lst = (void *)0;
}

• ft_lstiter : 연결리스트의 헤드와 실행하고싶은 함수 f를 매개변수로 받아서 연결리스트의 head부터 tail까지 모든 연결리스트의 content에 f함수를 실행한다

#include "libft.h"

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

	if (lst == (void *)0)
		return ;
	temp = lst;
	while (temp->next != (void *)0)
	{
		f(temp->content);
		temp = temp->next;
	}
	f(temp->content);
}

• ft_lstmap : 연결리스트의 head와 실행하고싶은 함수 f 오류상황에 실행하고 싶은 함수 del을 매개변수로 받아서 haed부터 tail까지 모든 연결리스트의 content에 f함수를 적용한 내용을 새로운 연결리스트로 만들어서 새로운 연결리스트의 head를 반환해줍니다 만약 malloc중에 오류가 발생했을 시 새로운 연결리스트의 content에 del함수를 적용하고 free후 NULL포인터를 리턴해줍니다

#include "libft.h"

t_list	*ft_lstmap(t_list *lst, void *(*f)(void *), void (*del)(void *))
{
	int		i;
	t_list	*temp_lst;
	t_list	*plst;
	t_list	*plst_head;

	i = 0;
	temp_lst = lst;
	plst_head = 0;
	plst = 0;
	if (lst == (void *)0)
		return (0);
	while (temp_lst != (void *)0)
	{
		plst = ft_lstnew((temp_lst->content));
		if (plst == 0)
		{
			ft_lstclear(&plst_head, del);
			return (0);
		}
		plst->content = f(temp_lst->content);
		ft_lstadd_back(&plst_head, plst);
		temp_lst = temp_lst->next;
		i++;
	}
	return (plst_head);
}