ft_lstnew, ft_lstadd_front, ft_lstsize, ft_lstlast, ft_lstadd_back, ft_lstdelone, ft_lstclear, ft_lstiter, ft_lstmap

Posted on | In

개요

링크드 리스트와 관련 함수에 대해서 알아보겠습니다.



구조체

1
2
3
4
5
typedef struct		s_list
{
	void			*content;
	struct s_list	*next;
}					t_list;

문제에서 주어진 링크드 리스트의 기본적인 구조체이다.

구조화된 데이터를 처리할 때 구조체를 사용한다. 객체라는 개념도 비슷한 개념이다.

간단하게 말해서 하나이상의 변수들을 묶어서 개발자의 자료형으로 다시 만드는 것이라고 생각하면 편하다.

기본적인 구조는

1
2
3
4
5
6
7
8
struct		구조체 이름
{
  구조체 멤버1;
  구조체 멤버2;
      .
      .
      .
};

struct를 붙여야 문법이 완성이 된다.

typedef를 struct앞에 붙이고 끝에 (sturct 구조체이름)을 치환할 이름을 적으면 편리하게 사용할 수 있다.

구조체에 대한 내용은 더 많지만 이번 과제는 링크드 리스트가 주요 과제이기 때문에 이정도만 하고 나중에 따로 자세하게 다뤄보겠다.



멤버 연산자

구조체를 선언하고 구조체의 멤버를 참조하기 위해서는 구조체 변수를 선언하고 .연산자를 이용한다.

그러나 이번 과제에서는 .연산자가 아닌 ->연산자를 사용할 것이다.

->연산자는 포인터 멤버 연산자라고 불린다. 구조체 포인터를 사용하게 될경우에는 ->를 이용해야합니다.

예를들어 (*ptr).num1 == ptr->num1이다.

이번과제에서 파라메터는 모두 구조체 포인터형으로 정해졌습니다.

이것을 참조하기 위해서는 ->연산자가 필요합니다.



Linked List


가장 간단한 리스트의 형태인 단방향 링크드 리스트이다. 리스트의 처음은 헤드노드라고 하여 다음 노드의 주소값을 가리키는 역할을 수행한다.

그다음 노드부터 content에 노드가 가지고 있는 값이 들어있고 next에는 다음노드의 시작주소를 가지고 있다.

이런식으로 여러개의 구조체 형식이 쭉 이어진 형상을 하여 링크드 리스트라고 부른다.

간단하게 링크드리스트의 구조만 알고 자세한것은 자료구조 포스팅에서 다루도록 하겠다.



ft_lstnew

SYNOPSIS

  • 함수 원형 : t_list *ft_lstnew(void *content);
  • void *content : 노드에 저장할 데이터
  • 리턴값 : 새로운 노드

DESCRIPTION

새로운 노드 생성

ft_lstnew CODE

1
2
3
4
5
6
7
8
9
10
11
12
t_list	*ft_lstnew(void *content)
{
	t_list	*node;

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

구조체 tlist형의 크기만큼 동적으로 할당해준다.

나머지 코드부분은 과제의 조건에 따라서 설계하였다.

그림으로 표현하면 다음과 같다.



ft_lstadd_front

SYNOPSIS

  • 함수 원형 : void ft_lstadd_front(t_list **lst, t_list *new);
  • t_list **lst : 삽입될 리스트
  • t_list *new : 리스트에 더해질 노드
  • 리턴값 : 새로운 노드를 앞에 더한 리스트

DESCRIPTION

새로운 노드를 앞에 붙인 후에 해당 리스트를 리턴

ft_lstadd_front CODE

1
2
3
4
5
6
7
void	ft_lstadd_front(t_list **lst, t_list *new)
{
	if (!lst || !new)
		return ;
	new->next = *lst;
	*lst = new;
}

이중포인터로 선언한 것이 특이하다. 리스트 관련함수 중에서 헤드 포인터를 바꿔줄 경우가 있는데

선언한 함수 안에서 바꿔주기 위해서 이중포인터를 사용한다.

new라는 새로운 노드를 리스트의 앞에 삽입한다.

삽입하는 과정은 new의 노드의 next 즉 new 노드가 가리키는 값이 리스트의 첫번째 노드가 되게하고 첫 노드가 new노드로 바꾸어주면 된다.

그림으로 표현하면 다음과 같다.



ft_lstsize

SYNOPSIS

  • 함수 원형 : int ft_lstsize(t_list *lst)
  • t_list *lst : 개수를 샐 리스트
  • 리턴값 : 노드의 개수

DESCRIPTION

노드의 개수를 센다

ft_lstsize CODE

1
2
3
4
5
6
7
8
9
10
11
12
int	ft_lstsize(t_list *lst)
{
	int	size;

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

노드가 더이상 가리키는게 없을때까지 이동하면서 개수를 센다.

비교적 쉬운 문제이다.



ft_lstlast

SYNOPSIS

  • 함수 원형 : t_list *ft_lstlast(t_list *lst);
  • t_list *lst : 리스트
  • 리턴값 : 마지막 노드

DESCRIPTION

마지막 노드를 반환하는 함수

ft_lstlast CODE

1
2
3
4
5
6
7
8
t_list	*ft_lstlast(t_list *lst)
{
	if (!lst)
		return ((void *)0);
	while (lst->next)
		lst = lst->next;
	return (lst);
}

노드가 널값을 가리킬 때까지 이동한 후 리턴한다.

비교적 쉬운 문제이다.



ft_lstadd_back

SYNOPSIS

  • 함수 원형 : void ft_lstadd_back(t_list **lst, t_list *new);
  • t_list **lst : 삽입될 리스트
  • t_list *new : 이어붙일 노드
  • 리턴값 : 이어붙인 리스트

DESCRIPTION

새로운 노드를 앞에 붙인 후에 해당 리스트를 리턴

ft_lstadd_back CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void	ft_lstadd_back(t_list **lst, t_list *new)
{
	t_list	*last;

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

new라는 새로운 노드를 리스트의 뒤에 삽입한다.

삽입하는 과정은 리스트의 마지막 노드를 의미하는 변수를 이용하여 새로운 노드가 가리키는 값에 기존의 마지막노드가 가리키는 값을 넣고

기존의 마지막 노드가 가리키는 값을 새로운 노드의 시작주소가 되도록 설정하면된다.

그림으로 표현하면 다음과 같다.



ft_lstdelone

SYNOPSIS

  • 함수 원형 : void ft_lstdelone(t_list lst, void (del)(void *));
  • t_list *lst : 리스트
  • void (*del)(void *) : void *형을 매개변수로 가진 삭제 함수 포인터

DESCRIPTION

노드의 content를 삭제

ft_lstdelone CODE

1
2
3
4
5
6
7
void	ft_lstdelone(t_list *lst, void (*del)(void *))
{
	if (!lst)
		return ;
	del(lst->content);
	free(lst);
}

content변수는 주소값이므로 content가 가리키고 있는 값까지 지워줘야한다. 만약 free(lst)를 그냥한다면 lst->content가 안된다.

따라서 삭제함수포인터 del함수를 이용해서 content의 값을 지우고 동적해제를 시켜준다.



ft_lstclear

SYNOPSIS

  • 함수 원형 : void ft_lstclear(t_list *lst, void (del)(void *))
  • t_list **lst : 리스트
  • void (*del)(void *) : void *형을 매개변수로 가진 삭제 함수 포인터

DESCRIPTION

리스트의 노드 데이터를 모두 삭제, 빈 리스트를 만든다

ft_lstclear CODE

1
2
3
4
5
6
7
8
9
10
11
12
void	ft_lstclear(t_list **lst, void (*del)(void *))
{
	t_list *tmp;

	while (*lst)
	{
		tmp = (*lst)->next;
		ft_lstdelone(*lst, del);
		(*lst) = tmp;
	}
	*lst = (void *)0;
}
  1. 현재 노드의 다음 노드주소를 버퍼에 담아놓는다
  2. 노드의 데이터를 삭제
  3. 다음 노드로 이동한다.
  4. 마지막에 리스트는 널값을 가리켜야 한다고 문제의 조건이있다.



ft_lstiter

SYNOPSIS

  • 함수 원형 : void ft_lstiter(t_list lst, void (f)(void *))
  • t_list *lst : 리스트
  • void (*f)(void *) : void *형을 매개변수로 가진 리스트에 적용할 함수 포인터

DESCRIPTION

전체 노드의 데이터에 f함수를 적용한다.

ft_lstiter CODE

1
2
3
4
5
6
7
8
9
10
void	ft_lstiter(t_list *lst, void (*f)(void *))
{
	if (!lst)
		return ;
	while (lst)
	{
		f(lst->content);
		lst = lst->next;
	}
}

마지막 노드까지 이동하면서 content에 f함수를 적용한다.



ft_lstmap

SYNOPSIS

  • 함수 원형 : t_list ft_lstmap(t_list *lst, void *(f)(void ), void (del)(void *));
  • t_list *lst : 리스트
  • void (*f)(void *) : void *형을 매개변수로 가진 리스트에 적용할 함수 포인터
  • void (*del)(void *) : void *형을 매개변수로 가진 삭제 함수 포인터

DESCRIPTION

전체 노드의 데이터에 f함수를 적용한 리스트를 복제한다. 만약 새로운 노드를 만들수 없다면 리스트를 clear하고 종료한다.

ft_lstmap CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
t_list	*ft_lstmap(t_list *lst, void *(*f)(void *), void (*del)(void *))
{
	t_list *new_lst;
	t_list *tmp;

	new_lst = 0;
	while (lst)
	{
		if ((tmp = ft_lstnew(f(lst->content))) == 0)
		{
			ft_lstclear(&new_lst, del);
			return ((void *)0);
		}
		ft_lstadd_back(&new_lst, tmp);
		lst = lst->next;
	}
	return (new_lst);
}

마지막 노드까지 이동하면서 content에 f함수를 적용한 후 리턴하려고 만든 새로운 리스트에 복사한다.



3줄 요약

1. 링크드 리스트의 복습으로는 좋았지만 자세하게 알려면 자료구조를 깊게 공부해야할것같다.

2. .과 -> 차이를 알게되었다.

3. 이런 것을 만든사람이 참 궁금하다. 어떻게 만들었지