원형 양방향 연결리스트 구현

dlist

typedef struct s_dlist
{
	t_node	*head; // head_node
	int		size; // 연결리스트의 총 길이
}	t_dlist;

node

typedef struct s_node
{
	struct s_node	*next; // next_node
	struct s_node	*prev; // prev_node
	int				value; // value
}	t_node;

dlist_init

연결리스트를 생성 후 초기값을 설정해준다
head = NULL
size = 0;

t_dlist	*dlist_init(void)
{
	t_dlist	*new_list;

	new_list = malloc(sizeof(t_dlist));
	if (!new_list)
		error();
	new_list->head = NULL;
	new_list->size = 0;
	return (new_list);
}

node_init

node를 생성 후 초기값을 설정해준다
next = NULL;
prev = NULL;
value = value;

t_node	*node_init(int value)
{
	t_node	*new_node;

	new_node = malloc(sizeof(t_node));
	if (!new_node)
		error();
	new_node->next = NULL;
	new_node->prev = NULL;
	new_node->value = value;
	return (new_node);
}

add_last_node

연결리스트의 맨 마지막(tail)에 새로운 노드를 추가해준다

void	add_last_node(t_dlist *dlist, int value)
{
	t_node	*new_node;

	new_node = node_init(value);
	if (dlist == NULL) 
    // 만약 연결리스트가 NULL이라면 종료
		return ;
	if (dlist->head == NULL) 
    // 현재 연결리스트안에 노드가 하나도 존재하지않는다면 연결리스트의 Head를 new_node로 하고
    // next와 prev를 자기 자신을 가리키게 한다
	{
		dlist->head = new_node;
		new_node->prev = new_node;
		new_node->next = new_node;
	}
	else
	{
		new_node->prev = dlist->head->prev;
        // new_node의 prev를 tail을 가리키게 한다
		new_node->next = new_node->prev->next;
        // new_node의 next를 head를 가리키게 한다
		new_node->prev->next = new_node;
        // 기존 tail의 next를 new_node를 가리키게 한다
		dlist->head->prev = new_node;
        // 헤드의 prev를 new_node를 가리키게 한다
	}
	dlist->size += 1;
    // 연결 리스트의 사이즈를 하나 추가한다
}

add_first_node

연결 리스트의 맨 앞(head)에 새로운 노드를 추가해준다

void	add_first_node(t_dlist *dlist, int value)
{
	t_node	*new_node;

	new_node = node_init(value);
	if (dlist == NULL)
    // 만약 연결리스트가 NULL이라면 종료
		return ;
	if (dlist->head == NULL)
    // 현재 연결리스트안에 노드가 하나도 존재하지않는다면 연결리스트의 Head를 new_node로 하고
    // next와 prev를 자기 자신을 가리키게 한다
	{
		dlist->head = new_node;
		new_node->prev = new_node;
		new_node->next = new_node;
	}
	else
	{
		new_node->prev = dlist->head->prev;
        // new_node의 prev가 tail을 가리키게 한다
		dlist->head->prev->next = new_node;
        // tail의 next가 new_node를 가리키게 한다
		new_node->next = dlist->head;
        // new_node의 next가 기존 head를 가리키게 한다
		dlist->head->prev = new_node;
        // 기존 head의 prev가 new_node를 가리키게 한다
		dlist->head = new_node;
        //연결리스트의 head를 new_node로 변경한다
	}
	dlist->size += 1;
    // 연결리스트의 사이즈를 하나 늘린다
}

delete_first_node

연결리스트의 head를 삭제한다

void	delete_first_node(t_dlist *dlist)
{
	t_node	*temp_node;

	if (dlist == NULL || dlist->head == NULL)
    // 연결리스트가 NULL이거나 Head가 Null이면 함수를 종료한다
		return ;
	temp_node = dlist->head;
    // temp_node에 head를 저장해준다
	dlist->head->prev->next = dlist->head->next;
    // tail의 next가 head의 next를 가리키게 한다
	dlist->head->next->prev = dlist->head->prev;
    // head의 next의 prev가 tail을 가리키게 한다
	dlist->head = dlist->head->next;
    // head를 head의 next로 변경한다
	free(temp_node);
    // 기존 head를 free시켜준다
	dlist->size -= 1;
    // 연결 리스트의 사이즈를 1 감소시키다
	if (dlist->size == 0) 
    // 만약 연결리스트의 사이즈가 0이라면 head를 NULL포인터로 변경한다
    // 이렇게 하지 않을 시 segmantaion error발생 및 댕글링포인터 발생 가능
		dlist->head = NULL;
}

delete_last_node

연결리스트의 tail을 삭제한다

void	delete_last_node(t_dlist *dlist)
{
	t_node	*temp_node;

	temp_node = dlist->head;
    // temp_node에 head를 저장해준다
	if (dlist == NULL || dlist->head == NULL)
    // 연결리스트가 NULL이거나 Head가 NULL이면 함수를 종료
		return ;
	if (dlist->head->next == dlist->head)
    // 만약 연결리스트에 값이 하나만 있을 시 head가 NULL포인터를 가리키게 한다
		dlist->head = NULL;
	else if (dlist->head->next == dlist->head->prev)
    // 만약 연결리스트에 값이 두개만 있을 시 head의 next와 prev가 head를 가리키게 한다
	{
		temp_node = dlist->head->next;
		dlist->head->next = dlist->head;
		dlist->head->prev = dlist->head;
	}
	else
	{
		temp_node = dlist->head->prev;
        // temp_node가 tail을 가리키게 해준다
		dlist->head->prev = dlist->head->prev->prev;
        // head의 prev가 기존 tail의 prev를 가리키게 해준다
		dlist->head->prev->next = dlist->head;
        // 기존 tail의 prev의 next가 head를 가리키게 해준다
	}
	free(temp_node);
    // temp_node를 free시켜준다
	dlist->size -= 1;
    // 연결 리스트의 size를 하나 감소시킨다
}

delete_all_node

연결리스트의 모든 노드를 삭제시킨다

void	delete_all_node(t_dlist	**dlist)
{
	t_node	*free_temp;
	t_node	*next_temp;
	int		i;

	i = 0;
	if (dlist == NULL)
    // 만약 연결리스트가 NULL이면 함수를 종료시킨다
		return ;
	next_temp = (*dlist)->head;
    // next_temp가 head를 가리키게 해준다
	while (i < (*dlist)->size)
    // 연결리스트의 size만큼 반복시킨다
	{
		free_temp = next_temp;
        // free_temp를 next_temp로 설정해준다
		next_temp = next_temp->next;
        // next_temp는 다음 node를 가리키게 해준다
		free(free_temp);
        // free_temp를 free해준다
		i++;
	}
	free(*dlist);
    // 연결리스트도 free해준다
}

delete_value_check

연결리스트안에 같은 값이 있는지 확인한다

int	dlist_value_check(t_dlist *dlist, int value)
{
	int		i;
	t_node	*next_temp;
	t_node	*prev_temp;

	i = 0;
	if (dlist == NULL || dlist->head == NULL)
    // 만약 연결리스트가 NULL이거나 head가 NULL이면 함수를 종료시킨다
		return (0);
	next_temp = dlist->head;
	prev_temp = dlist->head->prev;
	while (i < (dlist->size / 2) + 1)
    // 연결리스트의 next와 prev부터 돌면서 비교할거기 때문에 연결리스트 size의 반 만큼 반복시킨다
	{
		if (next_temp->value == value || prev_temp->value == value)
        // 만약 next_temp나 prev_temp의 value와 매개변수로 받은 value값이 같다면 1을 반환해준다
			return (1);
		next_temp = next_temp->next;
        // next_temp가 다음 node를 가리키게 해준다
		prev_temp = prev_temp->prev;
        // prev_temp가 이전 node를 가리키게 해준다
		i++;
	}
	return (0);
    // 이상없을시 0을 반환해준다
}

dlist_print

연결리스트의 모든값을 순서대로 출력해준다

void	dlist_print(t_dlist *dlist)
{
	int		i;
	t_node	*temp_node;

	i = 0;
	if (dlist == NULL || dlist->head == NULL)
    // 연결리스트나 head가 NULL일 경우 함수를 종료시킨다
		return ;
	temp_node = dlist->head;
	while (i < dlist->size)
    // 연결리스트의 size만큼 반복하면서 value값을 출력시켜준다
	{
		ft_printf("%d\n", temp_node->value);
		temp_node = temp_node->next;
		i++;
	}
}