연결 리스트(Linked List)를 다루는 함수 만들기.
연결리스트란?
연결리스트란 데이터 구조 중 하나이다.
각 요소(노드)가 데이터와 다음 노드를 가리키는 포인터를 포함하여 서로 연결된 형태로 구성된다.
연결 리스트의 핵심 요소
1. 노드(Node): 연결 리스트의 기본 구성 요소로, 데이터 (노드가 저장하는 값), 포인터 (다음 노드의 주소를 저장해, 리스트를 연결하는 역할)를 포함한다.
노드는 동적으로 생성되며, 메모리 상에서 비연속적으로 배치되고, 마지막 노 드의 포인터는 NULL을 가리켜 리스트의 끝임을 나타낸다.
2. 포인터(Pointer): 각 노드 내에 포함된NEXT필드는 다음 노드를 가리키는 메모리의 주소를 저장한다. 즉 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간이다.
리스트를 연결하여 순차적으로 탐색할 수 있도록 하며, 포인터를 통해 삽 입, 삭제 등의 작업이 이루어진다.
3. 헤드(Head): 연결 리스트의 가장 첫번째 노드를 가리키는 포인터다.
리스트의 시작점을 나타내며, 이를 통해 모든 노드를 탐색할 수 있게 해준다.
리스트가 비어있다면 NULL 값을 가진다.
헤드를 통헤 삽입 작업을 수행할 수 있다.
새 노드를 헤드에 추가하면 기존 헤드는 새 노드 위로 이동한다.
4. 테일(Tail): 연결 리스트의 마지막 노드를 가리키는 포인터다.
이 노드의 링크 필드는 Null을 가리킨다.
배열과 연결리스트의 차이점
메모리 구조
배열은 연속된 메모리 공간에 데이터를 저장하지만 연결리스트는 비연속적인 메모리 공간에 노드(Node)로 저장한다.
크기 조정
배열은 크기가 고정되어 있으며 생성 시 크기 지정이 필요한 반면 연결리스트는 동적 크기 조정이 가능하다.
데이터 접근 속도
배열은 배열 인덱스를 통해 빠르게 임의 접근이 가능하지만 연결 리스트는 인덱스가 불가능하고 순차적으로 탐색 해야해서 배열에 비해 시간이 소요된다.
삽입 및 삭제
중간 삽입/삭제 시 데이터 이동이 필요한 배열과 달리 연결리스트는 포인터만 변경하면 되므로 효율적이다.
메모리 사용 효율성
배열은 추가 메모리 사용이 없지만 연결리스트는 각 노드에 포인터 저장 공간이 필요하다.
캐시 효율성
연속된 메모리로 로컬리티 활용이 가능해 높은 캐시 효율성을 보이는 배열과 달리 연결리스트는 비연속적인 메모리 배치로 인한 낮은 캐시 효율성을 보여준다.
구조적 특징
배열은 인덱스가 존재하며 데이터만 저장하고 연결리스트는 데이터와 다음 노드를 가리키는 포인터를 포함한다.
사용사례
데이터 접근이 빈번하고 크기가 고정된 경우는 배열이 적합하고, 삽입 삭제가 빈번하거나 크기 변동이 많은 경우는 연결리스트가 적합하다.
배열의 장점
- 인덱스를 통해 임의 접근이 가능하여 검색 속도가 빠르다.
- 구조가 간단하고 구현이 쉽다.
- 캐시 효율성이 높다.
배열의 단점 - 크기를 미리 지정해야 하며, 크기를 초과하면 새로운 배열을 생성해야 한다.
- 삽입/삭제 시 데이터 이동 필요호 인해 비효율적이다.
연결리스트의 장점
- 동적 크기 조정이 가능하다.
- 중간 삽입/삭제가 빠르다.(포인터 조작으로만 처리 가능)
연결리스트의 단점 - 특정 요소 접근 속도가 느리다.
- 추가적인 메모리 사용이 가능하다.
- 캐시 효율성이 낮다.
연결 리스트의 종류
1. 단일 연결 리스트 (Singly Linked List)
- 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가진다.
- 마지막 노드의 포인터는 NULL을 가리킨다.
2. 이중 연결 리스트 (Doubly Linked List) - 각 노드는 데이터와 두 개의 포인터(이전 노드, 다음 노드)를 가진다.
- 양방향 탐색이 가능.
3. 원형 연결 리스트 (Circular Linked List) - 마지막 노드가 첫번째 노드를 가리키는 구조.
- 단일 또는 이중 연결 리스트 형태로구현 될 수 있다.
헤더파일(libft.h)에 구조체(t_list) 추가하기.
typedef struct s_list { void *content; struct s_list *next; } t_list;t_list 구조체란?
void *content노드 안에 저장할 데이터 (자료형 아무거나 가능)
struct s_list *next다음 노드를 가리키는 포인터 (없으면 NULL)
ft_lstnew 함수 구현하기
ft_lstnew 함수란?
새로운 노드(t_list)를 하나 만들어주는 함수이다.
malloc으로 메모리를 만들고,
**content(내용물)**은 주어진 걸 넣어주고
**next(다음 노드)**는 NULL로 초기화 한다.
ft_lstnew 함수 구현
#include "libft.h"
t_list *ft_lstnew(void *content)
{
t_list *node;
node = (t_list *)malloc(sizeof(t_list)); //노드 생성
if (!node)
return (NULL);
node->content = content; //노드에 내용 채우기
node->next = NULL; //next는 비우기
return (node); //노드 반환
}ft_lstadd_front 함수 구현하기
ft_lstadd_front 함수란?
리스트의 맨 앞에 새 노드를 붙이는 함수
기존 리스트가 있다면 새 노드를 맨 앞에 끼워 넣고, 리스트 시작점을 새 노드로 바꿔주는 것.
ft_lstadd_front 함수 구현
#include "libft.h"
void ft_lstadd_front(t_list **lst, t_list *new)
{
if (!lst || !new)
return;
new->next = *lst; //새 노드의 next를 기존 리스트(head)에 연결한다.
*lst = new; //리스트 head를 새 노드로 바꾼다.
}ft_lstadd_back 함수 구현하기
ft_lstadd_back 함수란?
리스트 맨 뒤에 새 노드를 추가하는 함수
기존 리스트를 끝까지 찾아가서, 맨 마지막 노드의 next에 새 노드를 연결하는 것.
ft_lstadd_back 함수 구현
#include "libft.h"
void ft_lstadd_back(t_list **lst, t_list *new)
{
t_list *last;
if (!lst || !new)
return;
if (!*lst) //리스트가 비어있으면 새 노드를 헤드로 만든다.
{
*lst = new;
return;
}
last = *lst; //리스트의 첫번째 노드부터 시작
while (last->next) //next가 NULL이 아닐 때까지 마지막 노드를 찾아간다.
last = last->next; //마지막 노드의 next에 새 노드를 연결한다.
last->next = new;
}ft_letsize 함수 구현하기
ft_letsize 함수란?
리스트에 노드가 몇 개 있는지 세는 함수
리스트가 있으면 노드들을 하나하나 따라가면서 카운트하며, 끝 (NULL)을 만나면 세기를 멈춘다.
ft_letsize 함수 구현
#include "libft.h"
int ft_letsize(t_list *lst)
{
int count;
count = 0;
while (lst) //리스트를 끝까지 반복
{
lst = lst->next; //다음 노드로 이동
count++;
}
return (count);
}ft_lstlast 함수 구현하기
ft_lstlast 함수란?
리스트에서 맨 끝 노드를 찾아주는 함수
리스트를 앞에서부터 끝까지 따라가다가 next가 NULL인 함수를 만나면 마지막 노드임으로 그 노드를 반환한다.
ft_lstlast 함수 구현
include "libft.h"
t_list ft_lstlast(t_list *lst)
{
if (!lst)
return (NULL);
while (lst->next)
lst = lst->next;
return (lst);
}ft_lstdelone 함수 구현하기
ft_lstdelone 함수란?
리스트 안의 노드 하나를 삭제(free)하고 그안에 있는 데이터(content)도 지우는 함수다.
노드 하나만 삭제하고 content도 따로 free해줘야함.
free만 하면 되는 것이 아닌 del()이라는 함수 포인터를 써서 내용물도 지워줘야한다.
ft_lstdelone 함수 구현
#include "libft.h"
void ft_lstdelone(t_list *lst, void (*del)(void))
{
if (!lst || ! del)
return;
del(lst->content); //노드 안 데이터 지우기
free(lst); //노드 자체 메모리 해제
}ft_lstclear 함수 구현하기
ft_lstclear 함수란?
리스트 전체를 다 지우고 free하는 함수
각 노드 안의 content도 del 함수를 사용해서 free 해줘야한다.
마지막에는 **head 포인터(리스트 시작점)**를 NULL로 만들어야 완성
ft_lstclear 함수 구현
#include "libft.h"
void ft_lstclear(t_list **lst, void (*del)(void *))
{
t_list *tmp
if (!lst || !del)
return;
while (*lst) //리스트가 끝날때까지 반복
{
tmp = (*lst)->next; //현재 노드의 다음 노드를 임시로 저장
ft_lstdelone(*lst, del); //현재 노드를 삭제 (내용 + 노드 메모리 free)
*lst = temp; //다음 노드로 이동
}
} //head 포인터 자체가 NULL로 된다.주의할 점
- 하나씩 삭제하면서 다음 노드를 임시로 저장하지 않으면 리스트를 잃어버림.
ft_lstiter 함수 구현하기
ft_lstiter 함수란?
리스트를 하나씩 돌면서, 각 노드의 content에 함수를 적용하는 함수
리스트를 처음부터 끝까지 순회하면서 각 노드 안에 있는 content를 가공/처리함.
1. 리스틑 앞에서부터 끝까지 돈다.
2. 현재 노드의 content에 f() 함수를 적용한다.
3. 다음 노드로 넘어간다.
#include "libft.h"
void ft_lstiter(t_list *lst, void (*f)(void *))
{
if (!lst || !f)
return;
while (lst) //리스트가 끝날 때까지 반복
{
f(lst->content); //현재 노드의 content에 함수 적용
lst = lst->content; //다음 노드로 이동
}
}ft_lstmap 함수 구현하기
ft_lstiter 함수란?
리스트를 순회하면서, content를 가공한 결과로 새 리스트를 만드는 함수
원래 리스트는 건드리지 않고 content를 변형해서 새로운 노드를 새 리스트에 붙이는 것
1. 원래 리스트를 순회한다.
2. 각 노드의 content를 f() 함수에 넣는다 -> 새로운 content를 얻는다.
3. 새 content로 새 노드를 만들어서 새로운 리스트에 추가한다.
4. 만약 중간에 실패하면, 지금까지 만든 새 리스트를 모두 free하고 NULL 변환
ft_lstiter 함수 구현
#incldue "libft.h"
t_list ft_lstmap(t_list *lst, void *(*f)(void *), void (*del)(void *))
{
t_list *new_list;
t_list *new_node;
if (!lst || !f || !del)
return (NULL);
new_list = NULL; //새 리스트 시작은 NULL
while (lst) //원래 리스트를 순회
{
new_node = ft_lstnew(f(lst->content)); //가공한 새 content로 새 노드 만들기
if (!new_node) //만약 메모리 할당 실패하면 지금까지 만든거 다 free하고 NULL 변환
{
ft_lstclear(&new_list, del);
return (NULL);
}
ft_lstadd_back(&new_list, new_node); //새 노드를 새 리스트 뒤에 추가
lst = lst->next; //다음 노드로 이동
}
return (new_list);
}끝
