-LinkedList 구현
🎈<목차>
1)Linkedlist란 무엇인가?? (간단한 구조&개념)
2)Linkedlist 구현 설명 -"header.h"
3)Linkedlist 구현 설명 -"List.h"
4)Linkedlist 구현 설명- "list.c"
5)Linkedlist 구현 설명 -"src.c"
1)Linkedlist란 무엇인가?? (간단한 구조&개념)
1.Linkedlist 란?
-
데이터를 저장한 단위 메모리가 서로 연결되어 있는 자료구조
-
단일 연결 리스트(singly linked list) : 리스트의 각 노드에 다른 노드를 가리키는 포인터가 하나씩만 있는 연결 리스트
2.연결 리스트(linked list)와 배열의 비교
3.단일 연결 리스트(singly linked list) 관리를 위한 개념
*이번 프로젝트의 연결리스트를 실제 프로그램 내에서 사용하기 위해서는 첫번째 node(begin node)에 접근하기 위한 pointer 변수(begin pointer 가 반드시 필요하다.
*또한 부수적으로 마지막 node(end node)를 가리키는 pointer 변수(end pointer)와 연결 리스트내의 실제 데이터를 저장하고 있는 node의 개수(연결리스트 크기를)를 저장해 놓으면 리스트 관리가 매우 수월 해진다.
2)Linkedlist 구현 설명 -"header.h"
#pragma once
#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <crtdbg.h>
//header 파일 불러오기
typedef int element;//형 재정의(typedef)
//타입정의 설명 링크
[https://sciphy.tistory.com/893]
=>🎉위의 헤더 파일은 이 프로그램을 수행하기 위해 불러오는 헤더 파일로 기존에 항상 쓰던 stdio.h 와 stdlib.h 에서 필요한 헤더파일을 추가함
- <stdio.h>=>Standard Input/Output library (표준입출력 라이브러리),
- <stdlib.h>=>stdlib.h는 C 언어의 표준 라이브러리로, 문자열 변환, 사 난수 생성, 동적 메모리 관리 등의 함수들을 포함하고 있다.
- <stdbool.h> => standard boolean이라는 뜻으로 ,표준 Bool형을 정의하기 위한 헤더파일이다.
- <string.h>=>문자열 처리를 위한 헤더 파일
- <crtdbg.h>=>메모리 누수 탐지 기능을 탑재한 헤더 파일로 프로그램의 malloc이나 free와 같은 메모리 할당 해제가 여기에 정의된 함수를 이용하여 메모리를 추적 할 수 있다.
**그리고 타입 재정의 개념 링크 => Go Go
//https://sciphy.tistory.com/893
3) Linkedlist 구현 설명 -"List.h"
#pragma once
#include "header.h"
typedef struct node /*노드 구조체*/
{
element data; /*데이터 영역 :element(int 형) 데이터 저장*/
struct node*next; /*포인터 영역*/
}NODE;
typedef struct list /*연결리스트 관리 구조체*/
{
NODE*begin; /*begin pointer(begin node 가리킴) */
NODE*end; /*end pointer(end node 가리킴)*/
size_t size; /*연결 리스트의 크기 - 실제 data node의 개수*/
}LIST;
void construct(LIST**); /*연결 리스트 초기화*/
void destruct(LIST**); /*리스트 소멸자 */
bool empty(LIST*); /*연결리스트가 비었는지 확인*/
size_t size(LIST*); /*연결리스트 size 보이도록 나타냄*/
element*at(LIST*, size_t); /*리스트의 특정 인덱스에 접근하여 주소값을 반환 */
void insert(LIST*, size_t, element); /*노드 삽입*/
void erase(LIST*, size_t); /*노드 삭제*/
void clear(LIST*); /* 리스트의 모든 원소를 삭제*/
void merge(LIST*, LIST*); //두 리스트를 병합
void split(LIST*, LIST**, size_t); //두 리스트 분리
size_t find(LIST*, void*); //해당 노드 찾기
void sort(LIST*); /*노드 정렬*/
=>🧨위의 헤더파일은 NODE를 구성하는 구조체와 list를 구성하는 연결리스트 관리 구조체로 구성된다.
=>구현 함수는 다음 주석과 같다
void construct(LIST); //연결 리스트 초기화
void destruct(LIST); //리스트 소멸자
bool empty(LIST); //연결리스트가 비었는지 확인/
size_t size(LIST); //연결리스트 size 보이도록 나타냄/
element *at(LIST, size_t); //리스트의 특정 인덱스에 접근하여 주소값을 반환
void insert(LIST, size_t, element); //노드 삽입
void erase(LIST, size_t); //노드 삭제
void clear(LIST); // 리스트의 모든 원소를 삭제/
void merge(LIST, LIST); //두 리스트를 병합
void split(LIST*, LIST**, size_t); //두 리스트 분리
size_t find(LIST, void); //해당 노드 찾기
void sort(LIST*); //노드 정렬
4)Linkedlist 구현 설명- "list.c
#include "List.h"
/*-----------------------------------------------------------------------------------------
Function name : construct - 연결 리스트 생성 및 초기화
Parameters : *list - 리스트 관리 구조체의 주소
------------------------------------------------------------------------------------------*/
void construct(LIST**list)
{
(*list) = (LIST*)malloc(sizeof(LIST)); //리스트 생성
if (*list != NULL) { /*리스트가 제대로 생성*/
(*list)->begin = (NODE*)malloc(sizeof(NODE)); //begin 노드 생성
(*list)->end = (NODE*)malloc(sizeof(NODE)); //end 노드 생성
(*list)->size = 0; //size는 0으로 초기화
if ((*list)->begin != NULL) /*begin 노드가 제대로 생성*/
{
(*list)->begin->next = (*list)->end; //begin노드가 end노드를 가리킴
(*list)->begin->data = 0; //begin 노드의 데이터 =0으로 초기화
}
if ((*list)->end != NULL) /*end 노드 제대로 생성*/
{
(*list)->end->next = NULL; //end 노드의 next= NULL을 가리킴
(*list)->end->data = 0; //end 노드의 데이터 =0으로 초기화
}
}
}
/*
-------------------------------------------------------------------------------------------
Function name : destruct - 리스트 소멸자
Parameters : *list-리스트 관리 구조체 주소
-------------------------------------------------------------------------------------------
*/
void destruct(LIST**list)
{
NODE*curp; /* curp 노드 (현재 노드를 가리키는 포인터)*/
NODE*nextp; /*nextp 노드 *(다음 노드를 가리키는 포인터 */
if ((*list) == NULL) //list==NULL이라면
{
return;
}
curp = (*list)->begin->next; /*NULL이 아니면*/
while (curp != (*list)->end) { /*curp가 end까지 반복*/
nextp = curp->next; //nextp를 curp next가 가리키는곳으로 지정
free(curp); //curp free시켜주기
curp = nextp; //curp는 nextp로 이동
}
free((*list)->begin); //begin free 시켜주기
free((*list)->end); //end free 시켜주기
(*list)->begin = (*list)->end = NULL; //list안의 begin과 end의 값을 NULL 값으로 지정해놓기
(*list)->size = 0; //list의 size 값을 0으로 초기화
free(*list); //list free시켜 주기
*list = NULL; //list의 값을 NULL로 지정
_CrtDumpMemoryLeaks(); //(메모리 누수 탐색)
return;
}
/*---------------------------------------------------------------------------------------
Function name : empty - 연결리스트가 비웠는지 확인
Parameters : list - 리스트 관리 구조체의 주소
Return : 방법 1) list->size=0으로 리턴
방법 2) 성공 - true, 실패-false
----------------------------------------------------------------------------------------*/
bool empty(LIST*list)
{
return list->size == 0;//list size를 0으로 리턴(초기화)
/*다른 방법*/
// <설명>
//list size가 0이라면 =>true 리턴
//아니면 => false 리턴
/*if (list->size == 0)
return true;
else
return false;
*/
}
/*------------------------------------------------------------------------------------
Function name : size - 리스트 size 확인용
Parameters : list - 리스트 관리 구조체의 주소
Return : list의 size 리턴
-----------------------------------------------------------------------------------*/
size_t size(LIST*list)
{
return list->size; //리스트 size로 리턴
}
/*---------------------------------------------------------------------------------------
Function name :at - 리스트의 특정 인덱스에 접근하여 주소값을 반환
Parameters : list - 리스트 관리 구조체의 주소
index - 연결리스트의 인덱스로 표현
Return : result->data 주소(해당 데이터의 주소)의 값을 리턴
----------------------------------------------------------------------------------------*/
element*at(LIST*list, size_t index)
{
NODE*result = list->begin->next; /*result 노드 포인터 지정*/
for (int i = 0; i < index; i++) {
result = result->next; //리스트의 끝까지 result->next 시켜주기
}
return &(result->data); //result->data 주소의 값을 리턴
}
/*--------------------------------------------------------------------------------------
Function name : insert -해당 리스트 노드 위치에 노드 삽입
Parameters : list - 리스트 관리 구조체의 주소
index - size 값을 배열 인덱스로 표현
data -노드 data 값
---------------------------------------------------------------------------------------*/
void insert(LIST*list, size_t index, element data)
{
NODE*now = list->begin; //now 포인터 지정
for (int i = 0; i < index; i++) { //리스트 끝까지 now->next 시켜주기
now = now->next;
}
NODE*node = (NODE*)malloc(sizeof(NODE)); //노드 생성
if (node != NULL) { /*노드 생성 성공 시*/
node->data = data; //노드 데이터 삽입
node->next = now->next; //노드의 next= now->next의 값을 가리킴
now->next = node; //now->next를 다시 node로 가리키기
}
list->size++; //list->size 1 증가시키기
}
/*--------------------------------------------------------------------------------------
Function name : erase - 해당 리스트 노드 삭제
Parameters : list - 리스트 관리 구조체의 주소
index - size 값을 배열 인덱스로 표현
---------------------------------------------------------------------------------------*/
void erase(LIST*list, size_t index)
{
NODE*now = list->begin;
for (int i = 0; i < index; i++)
{
now = now->next;
}
NODE*temp = now->next->next; //temp 포인터 지정
free(now->next); //now->next free(삭제) 시켜주기
now->next = temp; //now->next를 temp로 가리키기
list->size--; //list-> size 1 감소시키기
}
/*--------------------------------------------------------------------------------------------------
Function name : clear - 리스트의 모든 원소를 삭제
Parameters : list - 리스트 관리 구조체의 주소
Return : 없음
----------------------------------------------------------------------------------------------------*/
void clear(LIST* list)
{
NODE*curp; /* curp 노드 (현재 노드를 가리키는 포인터)*/
NODE*nextp; /*nextp 노드 *(다음 노드를 가리키는 포인터 */
if (list == NULL) //list==NULL이라면
{
return;
}
curp = list->begin->next; /*NULL이 아니면*/
while (curp != list ->end) { /*curp가 end까지 반복*/
nextp = curp->next; //nextp를 curp next가 가리키는곳으로 지정
free(curp); //curp free시켜주기
curp = nextp; //curp는 nextp로 이동
}
return;
}
/*------------------------------------------------------------------------------------------------
Funtion name : append - 두개의 리스트들을 병합
Parameters : list- 리스트 관리 구조체 주소
target - 새로운 리스트 관리 구조체 주소
Return : 없음
---------------------------------------------------------------------------------------------*/
void append(LIST* list, LIST** target)
{
if ((*target)->size == 0 && list->size != 0) /*target의 리스트의 사이즈가 0일때*/
{
destruct(target); /*target 리스트 삭제*/
}
else if (list->size == 0) /*list의 크기가 0일때*/
{
free(list->begin); /*list의 begin 노드가 삭제*/
free(list->end); /*list의 end 노드가 삭제*/
list->begin = (*target)->begin; /*list의 begin은 target 리스트의 begin으로 연결*/
list->end = (*target)->end; /**list의 end은 target 리스트의 end으로 연결*/
list->size = (*target)->size;
free(*target);
*target = NULL;
}
else
{
NODE* temp = NULL;
for (temp = list->begin; temp->next != list->end; temp = temp->next); //temp가 list의 end로 순환
temp->next = (*target)->begin->next; /*temp next는 target 리스트 begind의 next로 연결*/
free(list->end); /*list 리스트의 end를 free 시키기 */
list->end = (*target)->end; /*list 리스트의 end는 target 리스트의 end로 가리키기 */
list->size = list->size + (*target)->size; /*리스트의 size는 list 리스트의 사이즈와 target 리스트의 사이즈를 합한것*/
free((*target)->begin); /*target 리스트의 begin을 free 시켜주기 */
free((*target)); /*target 리스트 free 시켜주기 */
(*target) = NULL;
}
}
/*------------------------------------------------------------------------------------------------
Funtion name : split - 두개의 리스트들을 분할
Parameters : list - 리스트 관리 구조체 주소
target - 새로운 리스트 관리 구조체
size_t - size 값을 배열 인덱스로 표현
Return : 없음
-------------------------------------------------------------------------------------------- - */
void split(LIST* list, LIST** target, size_t index)
{
NODE* now = list->begin;
for (int i = 0; i < index; i++) /*now 포인터 인덱스 끝까지 옮기기*/
{
now = now->next;
}
if (target != NULL) /*target 리스트가 NULL이 아니면*/
{
destruct(target); /*리스트 소멸자*/
construct(target); /*리스트 생성자*/
if (*target != NULL)
{
(*target)->begin->next = now->next; /*target 리스트를 now 포인터 다음 위치에 가리키기*/
free((*target)->end); /*target 리스트의 end를 free*/
(*target)->end = list->end; /*target 리스트의 end를 기존 리스트에 동기화 시키기*/
NODE* end = (NODE*)malloc(sizeof(NODE)); /*end 노드 동적 할당 */
if (end != NULL)
{
end->next = NULL; /*end 끝까지 옮기기*/
}
now->next = end; /* end 동기화시키기 */
now->next = end; /* end 동기화시키기 */
list->end = end;
(*target)->size = list->size - index; /*target size */
list->size = index; /*list size */
}
}
}
/*------------------------------------------------------------------------------------------------
Funtion name : find_element - 리스트 내에서 조건에 맞는 원소를 찾아 인덱스를 반환
Parameters : list - 리스트 관리 구조체 주소
target - 새로운 리스트 관리 구조체
size_t - size 값을 배열 인덱스로 표현
Return : 없음
-------------------------------------------------------------------------------------------- - */
size_t find_element(LIST* list, element condition)
{
NODE* now = list->begin; /*now begin으로 옮기기*/
for (int i = 0; i < l_size(list); i++) /*now 끝까지 옮기기*/
{
now = now->next;
if (condition == at(list, i)) /*만약 지정된 list 인덱스에 값과 condition 값이 같다면*/
{
return i; /*인덱스 반환*/
}
}
return -1; /*아니면 -1으로 반환*/
}
/// <summary>
/// 리스트를 반전
/// </summary>
/// <param name="list"> 대상이 될 리스트 </param>
void l_reverse(LIST* list)
{
}
/*------------------------------------------------------------------------------------------------
Funtion name : sort - 리스트 정렬
Parameters : list - 리스트 관리 구조체 주소
order - 정렬 순서 표현
Return : 없음
-------------------------------------------------------------------------------------------- - */
void sort(LIST* list, bool order)
{
for (int i = 0; i < l_size(list) - 1; i++)
{
NODE* x = list->begin->next;
NODE* y = x->next;
for (int j = 0; j < l_size(list) - i - 1; j++)
{
if (order && x->data > y->data)
{
x->data ^= y->data ^= x->data ^= y->data;
//swap
}
else if (!order && x->data < y->data)
{
x->data ^= y->data ^= x->data ^= y->data;
//swap
}
x = x->next;
y = y->next;
}
}
}
=>😂위의 파일은 주석에 포함되어 있음.
5)-Linkedlist 구현 설명 - "src.c"
#include "header.h"
#include "List.h"
#include "Stack.h"
// main source code
int main()
{
LIST* list1 = NULL;
l_construct(&list1);
l_insert(list1, 0, 1);
l_insert(list1, 0, 2);
l_insert(list1, 0, 3);
l_insert(list1, 0, 4);
l_insert(list1, 0, 5);
LIST* list2 = NULL;
l_construct(&list2);
l_insert(list2, 0, 6);
l_insert(list2, 0, 7);
l_insert(list2, 0, 8);
l_insert(list2, 0, 9);
l_insert(list2, 0, 10);
l_append(list1, &list2);
for (int i = 0; i < l_size(list1); i++)
{
printf("%d -> ", *l_at(list1, i));
}
printf("\n");
l_split(list1, &list2, 5);
for (int i = 0; i < l_size(list1); i++)
{
printf("%d -> ", *l_at(list1, i));
}
printf("\n");
for (int i = 0; i < l_size(list2); i++)
{
printf("%d -> ", *l_at(list2, i));
}
printf("\n");
//printf("%lld", find_element(list1, 11));
l_sort(list1, false);
for (int i = 0; i < l_size(list1); i++)
{
printf("%d -> ", *l_at(list1, i));
}
printf("\n");
l_destruct(&list1);
l_destruct(&list2);
printf("\n\nCHECK\n\n");
_CrtDumpMemoryLeaks();
}