-LinkedList 구현
🎈<목차>
1)Linkedlist란 무엇인가?? (간단한 구조&개념)
2)Linkedlist 구현 코드 설명
3)화면 출력 결과
🎆 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 구현 코드 설명
Linkedlist.h -[1]
#pragma once
enum BOOL { FALSE, TRUE };
typedef struct _node Node; /* 구조체 노드 형명재지정 */
struct _node { /* 노드 구조체 (자기참조 구조체 사용) */
int data; /* 데이터 영역 : int형 데이터 저장 */
Node *next; /* 포인터 영역 */
};
typedef struct _list { /* 연결 리스트 관리 구조체 */
Node *head; /* head pointer (head node 가리킴) */
Node *tail; /* tail pointer (tail node 가리킴) */
int size; /* 연결 리스트의 크기 - 실제 data node의 개수 */
}List;
BOOL createList(List *lp); /* 연결 리스트 초기화 */
BOOL addFirst(List *lp, int data); /* head node 뒤에 node 추가(역순 저장) */
BOOL addLast(List *lp, int data); /* tail node 앞에 node 추가(정순 저장) */
void displayList(List *lp); /* 리스트 내의 모든 데이터 출력 */
BOOL removeNode(List *lp, int data); /* data 노드 삭제 */
Node * searchNode(List *lp, int data); /* data와 일치하는 node 검색 */
void sortList(List *lp); /* 노드 정렬 - 오름차순 */
void destroyList(List *lp); /* 리스트 내의 모든 노드를 삭제 */
Linkedlist.cpp -[2]
#include "singlyLinkedlist.h"
#include <stdio.h> // printf(), scanf()
#include <stdlib.h> // malloc(), free()
/*----------------------------------------------------------------------------------
Function name : createList - 연결 리스트 생성 및 초기화
Parameters : lp - 리스트 관리 구조체의 주소
Returns : 성공 - TRUE / 실패 - FALSE
----------------------------------------------------------------------------------*/
BOOL createList(List *lp)
{
if (lp == NULL) {
return FALSE;
}
lp->head = (Node*)malloc(sizeof(Node));
if (lp->head == NULL) {
return FALSE;
}
lp->tail = (Node*)malloc(sizeof(Node));
if (lp->tail == NULL) {
free(lp->head);
return FALSE;
}
lp->head->next = lp->tail;
lp->tail->next = lp->tail;
lp->size = 0;
return TRUE;
}
/*----------------------------------------------------------------------------------
Function name : addFirst - head node 뒤에 node 추가(역순 저장)
Parameters : lp - 리스트 관리 구조체의 주소
data - 추가할 데이터
Returns : 성공 - TRUE / 실패 - FALSE
----------------------------------------------------------------------------------*/
BOOL addFirst(List *lp, int data)
{
Node*np;
if (lp == NULL) {
return FALSE;
}
np = (Node*)malloc(sizeof(Node));
if (np != NULL) {
np->data = data;
np->next = lp->head->next;
lp->head->next = np;
++lp->size;
return TRUE;
}
else {
return FALSE;
}
}
/*----------------------------------------------------------------------------------
Function name : addLast - tail node 앞에 새 node 추가(정순 저장)
Parameters : lp - 리스트 관리 구조체의 주소
data - 추가할 데이터
Returns : 성공 - TRUE / 실패 - FALSE
----------------------------------------------------------------------------------*/
BOOL addLast(List *lp, int data)
{
Node*np;
Node*btp;
if (lp == NULL) {
return FALSE;
}
np = (Node*)malloc(sizeof(Node));
if (np != NULL) {
np->data = data;
np->next = lp->tail;
btp = lp->head;
while (btp->next != lp->tail) {
btp = btp->next;
}
btp->next = np;
++lp->size;
return TRUE;
}
else {
return FALSE;
}
}
/*----------------------------------------------------------------------------------
Function name : displayList - 리스트 내의 모든 데이터 출력
Parameters : lp - 리스트 관리 구조체의 주소
Returns : 없음
----------------------------------------------------------------------------------*/
void displayList(List *lp)
{
Node*curp;
if (lp == NULL) {
return;
}
curp = lp->head->next;
while (curp != lp->tail) {
printf("%8d\n", curp->data);
curp = curp->next;
}
printf("\n");
return;
}
/*----------------------------------------------------------------------------------
Function name : searchNode - data와 일치하는 첫 번째 node 검색
Parameters : lp - 리스트 관리 구조체의 주소
data - 검색할 데이터
Returns : 성공 - 검색된 노드의 주소 / 실패 - NULL pointer
----------------------------------------------------------------------------------*/
Node * searchNode(List *lp, int data)
{
Node*curp;
if (lp == NULL) {
return NULL;
}
curp = lp->head->next;
while (curp != lp->tail) {
if (curp->data == data) {
return curp;
}
curp = curp->next;
}
return NULL;
}
/*----------------------------------------------------------------------------------
Function name : removeNode - data와 일치하는 첫 번째 노드 삭제
Parameters : lp - 리스트 관리 구조체의 주소
data - 삭제할 데이터
Returns : 성공 - TRUE / 실패 - FALSE
----------------------------------------------------------------------------------*/
BOOL removeNode(List *lp, int data)
{
Node*curp;
Node*delp;
if (lp == NULL) {
return FALSE;
}
delp = searchNode(lp, data);
if (delp != NULL) {
curp = lp->head;
while (curp->next != delp) {
curp = curp->next;
}
curp->next = delp->next;
free(delp);
--lp->size;
return TRUE;
}
else {
return FALSE;
}
}
/*----------------------------------------------------------------------------------
Function name : sortList - 노드 정렬(오름차순)
Parameters : lp - 리스트 관리 구조체의 주소
Returns : 없음
----------------------------------------------------------------------------------*/
void sortList(List *lp)
{
Node*nextp;
Node*curp;
int temp;
if (lp == NULL) {
return;
}
curp = lp->head->next;
while (curp->next != lp->tail) {
nextp = curp->next;
while (nextp != lp->tail) {
if (curp->data > nextp->data) {
temp = curp->data;
curp->data = nextp->data;
nextp->data = temp;
}
nextp = nextp->next;
}
curp = curp->next;
}
}
/*----------------------------------------------------------------------------------
Function name : destroyList - 리스트 내의 모든 노드(head, tail 노드 포함)를 삭제
Parameters : lp - 리스트 관리 구조체의 주소
Returns : 없음
----------------------------------------------------------------------------------*/
void destroyList(List *lp)
{
Node*curp;
Node*nextp;
if (lp == NULL) {
return;
}
curp = lp->head->next;
while (curp != lp->tail) {
nextp = curp->next;
free(curp);
curp = nextp;
}
free(lp->head);
free(lp->tail);
lp->head = lp->tail = NULL;
lp->size = 0;
return;
}
////#include "11강 singlyLinkedlist 1.h"
////#include <stdio.h> // printf(), scanf()
////#include <stdlib.h> // malloc(), free()
////#include <crtdbg.h>
////typedef int BOOL;
////
/////*----------------------------------------------------------------------------------
////Function name : createList - 연결 리스트 생성 및 초기화
////Parameters : lp - 리스트 관리 구조체의 주소
////Returns : 성공 - TRUE / 실패 - FALSE
////----------------------------------------------------------------------------------*/
////BOOL createList(List *lp)
////{
//// if(lp==NULL){
//// return FALSE;
//// }
////
//// lp->head = (Node*)malloc(sizeof(Node));
//// if (lp == NULL) {
//// return FALSE;
//// }
////
//// lp->tail = (Node*)malloc(sizeof(Node));
//// if (lp == NULL) {
//// free(lp->head);
//// return FALSE;
//// }
//// lp->head->next = lp->tail;
//// lp->tail->next = lp->tail;
//// lp->size = 0;
//// return TRUE;
////}
////
/////*----------------------------------------------------------------------------------
////Function name : addFirst - head node 뒤에 node 추가(역순 저장)
////Parameters : lp - 리스트 관리 구조체의 주소
//// data - 추가할 데이터
////Returns : 성공 - TRUE / 실패 - FALSE
////----------------------------------------------------------------------------------*/
////BOOL addFirst(List *lp, int data)
////{
//// Node*np;
////
//// if (lp == NULL) {
//// return FALSE;
//// }
////
//// np = (Node*)malloc(sizeof(Node));
//// if (np != NULL) {
//// np->data = data;
//// np->next = lp->head->next;
//// lp->head->next = np;
//// ++lp->size;
//// }
//// else {
//// return FALSE;
//// }
////
////}
/////*----------------------------------------------------------------------------------
////Function name : addLast - tail node 앞에 새 node 추가(정순 저장)
////Parameters : lp - 리스트 관리 구조체의 주소
//// data - 추가할 데이터
////Returns : 성공 - TRUE / 실패 - FALSE
////----------------------------------------------------------------------------------*/
////BOOL addLast(List *lp, char*data)
////{
//// Node*btp;
//// Node*np;
////
//// if (lp == NULL) {
//// return FALSE;
//// }
////
//// np = (Node*)malloc(sizeof(Node));
//// if (np != NULL) {
//// np->data = data;
//// np->next = lp->tail;
////
//// btp = lp->head;
//// while (btp->next != lp->tail) {
//// btp = btp->next;
//// }
//// btp->next = np;
//// ++lp->size;
//// return TRUE;
//// }
//// else {
//// return FALSE;
//// }
////
////}
////
/////*----------------------------------------------------------------------------------
////Function name : displayList - 리스트 내의 모든 데이터 출력
////Parameters : lp - 리스트 관리 구조체의 주소
////Returns : 없음
////----------------------------------------------------------------------------------*/
////void displayList(List *lp)
////{
//// Node*curp;
////
//// if (lp == NULL) {
//// return;
//// }
////
//// curp = lp->head->next;
//// while (curp != lp->tail) {
//// printf("%s-", curp->data);
//// curp = curp->next;
//// }
////
////
//// return;
////
////}
////
/////*----------------------------------------------------------------------------------
////Function name : searchNode - data와 일치하는 첫 번째 node 검색
////Parameters : lp - 리스트 관리 구조체의 주소
//// data - 검색할 데이터
////Returns : 성공 - 검색된 노드의 주소 / 실패 - NULL pointer
////----------------------------------------------------------------------------------*/
////Node * searchNode(List *lp, int data)
////{
//// Node*curp;
////
//// if (lp == NULL) {
//// return NULL;
//// }
////
//// curp = lp->head->next;
//// while (curp != lp->tail) {
//// if (curp->data == data) {
//// return curp;
//// }
//// curp = curp->next;
//// }
//// return NULL;
////
////
////}
/////*----------------------------------------------------------------------------------
////Function name : removeNode - data와 일치하는 첫 번째 노드 삭제
////Parameters : lp - 리스트 관리 구조체의 주소
////data - 삭제할 데이터
////Returns : 성공 - TRUE / 실패 - FALSE
////----------------------------------------------------------------------------------*/
////BOOL removeNode(List *lp, int data)
////{
//// Node*delp;
//// Node*curp;
////
//// if (lp == NULL)
//// {
//// return FALSE;
//// }
////
//// delp=searchNode(lp, data);
//// if (delp != NULL) {
//// curp = lp->head;
//// while (curp->next != delp) {
//// curp = curp->next;
//// }
//// curp->next = delp->next;
//// free(delp);
//// --lp->size;
//// return TRUE;
//// }
//// else {
//// return FALSE;
//// }
////}
/////*----------------------------------------------------------------------------------
////Function name : sortList - 노드 정렬(오름차순)
////Parameters : lp - 리스트 관리 구조체의 주소
////Returns : 없음
////----------------------------------------------------------------------------------*/
////void sortList(List *lp)
////{
////
//// Node*curp;
//// Node*nextp;
//// int temp;
////
//// if (lp == NULL) {
//// return;
//// }
////
//// curp = lp->head->next;
//// while (curp->next != lp->tail) {
//// nextp = curp->next;
//// while (nextp != lp->tail) {
//// if (curp->data > nextp->data) {
//// temp = curp->data;
//// curp->data = nextp->data;
//// nextp->data = temp;
////
//// }
//// nextp = nextp->next;
//// }
//// curp = curp->next;
//// }
////}
////
////
////
////
////
/////*----------------------------------------------------------------------------------
////Function name : destroyList - 리스트 내의 모든 노드(head, tail 노드 포함)를 삭제
////Parameters : lp - 리스트 관리 구조체의 주소
////Returns : 없음
////----------------------------------------------------------------------------------*/
////void destroyList(List *lp)
////{
//// Node*curp;
//// Node*nextp;
////
//// if (lp == NULL) {
//// return;
//// }
////
//// curp = lp->head->next;
//// while (curp != lp->tail) {
//// nextp = curp->next;
//// printf("\n%s freed", curp->data);
//// free(curp);
//// curp = nextp;
//// }
////
//// free(lp->head);
//// free(lp->tail);
////
//// lp->head = lp->tail = NULL;
//// lp->size = 0;
////
//// //_CrtDumpMemoryLeaks();
////
//// return;
////
////
////}
////
////
//
//
Linkedlist.main -[3]
#include <stdio.h>
#include <string.h>
#include "singlyLinkedlist.h"
int menu(const char** mList, size_t menuCnt);
void mInput(List* lp); /* 입력메뉴 처리 함수 */
void mOutput(List* lp); /* 출력메뉴 처리 함수 */
void mSearch(List* lp); /* 검색메뉴 처리 함수 */
void mDelete(List* lp); /* 삭제메뉴 처리 함수 */
void mSort(List* lp); /* 정렬메뉴 처리 함수 */
void myflush(); /* 입력 버퍼 flush 함수 */
/*----------------------------------------------------------------------------------
Function name : main
----------------------------------------------------------------------------------*/
int main()
{
const char* menuList[] = { "입력하기","출력하기","검색하기","삭제하기", "정렬하기", "종 료" };
int menuNum; /* 메뉴번호 저장 변수 */
int menuCnt; /* 메뉴개수 저장 변수 */
List list; /* 리스트관리 구조체 변수 */
BOOL bres;
menuCnt = sizeof(menuList) / sizeof(menuList[0]);
bres = createList(&list); /* 비어있는 리스트 초기화 */
if (bres == TRUE)
printf("@ list 생성 성공!\n");
else
printf("@ list 생성 실패!\n");
while (1)
{
menuNum = menu(menuList, menuCnt); /* 메뉴화면을 띄우고 메뉴번호를 입력 받음 */
if (menuNum == menuCnt) { break; }
switch (menuNum)
{
case 1: mInput(&list); break; /* 입력메뉴 실행 */
case 2: mOutput(&list); break; /* 출력메뉴 실행 */
case 3: mSearch(&list); break; /* 검색메뉴 실행 */
case 4: mDelete(&list); break; /* 삭제메뉴 실행 */
case 5: mSort(&list); break; /* 정렬메뉴 실행 */
}
}
printf("list내의 데이터 노드의 개수 : %d\n", list.size);
destroyList(&list); /* 리스트내의 모든 데이터 삭제 */
return 0;
}
/*----------------------------------------------------------------------------------
Function name : menu
Parameters : mList - 메뉴 목록 배열
menuCnt - 메뉴 개수
Returns : 사용자 선택한 메뉴번호
----------------------------------------------------------------------------------*/
int menu(const char** mList, size_t menuCnt)
{
size_t menuNum = 0; /* 존재하지 않는 메뉴 번호 저장 */
size_t i;
printf("\n\n");
for (i = 0; i < menuCnt; i++) { /* 메뉴 출력 */
printf("%d. %s\n", i + 1, mList[i]);
}
while (menuNum<1 || menuNum>menuCnt) { /* 메뉴번호가 유효하지 않을 동안 반복 */
printf("# 메뉴 선택 : ");
scanf("%d", &menuNum); /* 메뉴 번호 입력 */
}
return menuNum;
}
/*----------------------------------------------------------------------------------
Function name : mInput - 입력 메뉴 처리 함수
Parameters : lp - 리스트 관리 구조체의 주소
Returns : 없음
----------------------------------------------------------------------------------*/
void mInput(List* lp)
{
int inData;
int res; /* scanf()함수의 리턴 값 저장 */
BOOL bres;
printf("\n[ 입력하기 메뉴 ]\n\n");
while (1) {
printf("# 정수를 입력하세요(문자 입력시 종료) : ");
res = scanf("%d", &inData); /* scanf()함수의 리턴 값 : 정수 입력 시 1, 문자 입력 시 0리턴 됨*/
if (res == 0) { /* 문자 입력 시 종료 */
myflush();
break;
}
bres = addLast(lp, inData); /* tail 노드 앞에 데이터 추가 */
if (bres == TRUE)
printf("@ 데이터 추가 성공!\n");
else
printf("@ 데이터 추가 실패!\n");
}
return;
}
/*----------------------------------------------------------------------------------
Function name : mOutput - 출력 메뉴 처리 함수
Parameters : lp - 리스트 관리 구조체의 주소
Returns : 없음
----------------------------------------------------------------------------------*/
void mOutput(List* lp)
{
displayList(lp);
}
/*----------------------------------------------------------------------------------
Function name : mSearch - 검색 메뉴 처리 함수
Parameters : lp - 리스트 관리 구조체의 주소
Returns : 없음
----------------------------------------------------------------------------------*/
void mSearch(List* lp)
{
int sData;
Node* resp; /* 검색된 노드의 시작주소 저장 */
int res; /* scanf()함수의 리턴 값 저장 */
printf("\n[ 검색하기 메뉴 ]\n\n");
while (1) {
printf("# 찾을 데이터를 입력하세요(문자 입력 시 종료) : ");
res = scanf("%d", &sData); /* scanf()함수의 리턴 값 : 정수 입력 시 1, 문자 입력 시 0리턴 됨*/
if (res == 0) { /* 문자 입력 시 종료 */
myflush();
break;
}
else {
;
}
resp = searchNode(lp, sData);
if (resp != NULL) { /* 데이터를 찾았으면 */
printf("@ 검색 데이터 존재!\n");
}
else { /* 데이터를 못찾았으면 */
printf("@ 검색 데이터 존재하지 않음!\n");
}
}
return;
}
/*----------------------------------------------------------------------------------
Function name : mDelete - 삭제 메뉴 처리 함수
Parameters : lp - 리스트 관리 구조체의 주소
Returns : 없음
----------------------------------------------------------------------------------*/
void mDelete(List* lp)
{
int delData;
int res; /* scanf()함수의 리턴 값 저장 */
BOOL bres;
printf("\n[ 삭제하기 메뉴 ]\n\n");
while (1) {
printf("# 삭제할 데이터를 입력하세요(문자 입력 시 종료) : ");
res = scanf("%d", &delData); /* scanf()함수의 리턴 값 : 정수 입력 시 1, 문자 입력 시 0리턴 됨*/
if (res == 0) { /* 문자 입력 시 종료 */
myflush();
break;
}
else {
;
}
bres = removeNode(lp, delData);
if (bres == TRUE)
printf("@ 삭제 성공!\n");
else
printf("@ 삭제 실패!\n");
}
return;
}
/*----------------------------------------------------------------------------------
Function name : mSort - 정렬 메뉴 처리 함수
Parameters : lp - 리스트 관리 구조체의 주소
Returns : 없음
----------------------------------------------------------------------------------*/
void mSort(List* lp)
{
sortList(lp);
}
/*----------------------------------------------------------------------------------
Function name : myflush - 입력 버퍼 내의 모든 데이터 지우는 함수
Parameters : 없음
Returns : 없음
----------------------------------------------------------------------------------*/
void myflush()
{
while (getchar() != '\n') {
;
}
}
✨ 3)화면 출력 결과
