널널한 개발자 TV의 자료구조 강의 시리즈를 정리할 것이다.
연결 리스트에 데이터를 추가할 때 맨 마지막에 추가하려면 while문으로 노드 개수만큼 루프를 돌아야 한다.
이는 바람직하지 않은 구조이기 때문에 마지막 노드를 가리키는 Tail 포인터를 추가할 것이다.
아래 기존 연결 리스트 코드에 Tail 포인터를 추가한다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct NODE
{
char szData[64];
struct NODE *next;
} NODE;
NODE g_head = { 0 }; // 더미 노드(보통은 동적할당을 함)
/* 연결 리스트가 비어있는 지 확인하는 함수 */
int IsEmpty()
{
if (g_head.next == NULL)
return 1;
return 0;
}
/* 앞부분에 새 노드 추가 함수 */
int InsertAtHead(char *pszData)
{
NODE *pNode = (NODE *)malloc(sizeof(NODE));
if (pNode == NULL)
return 0;
memset(pNode, 0, sizeof(NODE));
strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);
if (IsEmpty())
g_head.next = pNode;
else
{
pNode->next = g_head.next;
g_head.next = pNode;
}
return 1;
}
/* 마지막 부분에 새 노드 추가 함수*/
int InsertAtTail(char *pszData)
{
// 마지막 노드 찾기
NODE *pTmp = &g_head;
while (pTmp->next != NULL)
pTmp = pTmp->next;
NODE *pNode = (NODE *)malloc(sizeof(NODE));
if (pNode == NULL)
return 0;
memset(pNode, 0, sizeof(NODE));
strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);
pTmp->next = pNode;
return 1;
}
/* 연결 리스트 전체 리스트 출력 함수 */
void PrintList(void)
{
NODE *pTmp = &g_head;
while (pTmp != NULL)
{
printf("[%p] %s, next[%p]\n", pTmp, pTmp->szData, pTmp->next);
pTmp = pTmp->next;
}
printf("\n");
}
/* 연길 리스트 전체 리스트 삭제 */
void ReleaseList(void)
{
NODE *pTmp = g_head.next;
printf("ReleseList()\n");
while (pTmp != NULL)
{
NODE *pDelete = pTmp;
pTmp = pTmp->next;
printf("Delete: [%p] %s\n", pDelete, pDelete->szData);
free(pDelete);
}
g_head.next = NULL;
}
/* 특정 노드를 존재하는 지 확인하는 함수 */
NODE *FindData(char *pszData)
{
NODE *pCur = g_head.next;
NODE *pPrev = &g_head;
while (pCur != NULL)
{
if (strcmp(pCur->szData, pszData) == 0)
return (pPrev);
pCur = pCur->next;
pPrev = pPrev->next;
}
return NULL;
}
/* 특정 노드를 찾아 삭제하는 함수*/
int DeleteData(char *pszData)
{
NODE *pPrev = FindData(pszData);
if (pPrev != NULL)
{
NODE *pDelete = pPrev->next;
pPrev->next = pDelete->next;
// 삭제
printf("DeleteData(): %s\n", pDelete->szData);
free(pDelete);
return 1;
}
return 0;
}
/* stack에 데이터 추가하는 함수*/
void PushData(char *pszData)
{
InsertAtHead(pszData);
}
/* stack에 데이터 꺼내오는 함수*/
int PopData(NODE *pPopNode)
{
NODE *sp = g_head.next;
if (IsEmpty())
return 0;
memcpy(pPopNode, sp, sizeof(NODE));
g_head.next = sp->next;
free(sp);
return 1;
}
/* queue에 데이터 추가하는 함수*/
void Equeue(char *pszData)
{
InsertAtTail(pszData);
}
/* queue에 데이터 꺼내오는 함수*/
int Dequeue(NODE *pGetNode)
{
return PopData(pGetNode);
}
Tail 포인터를 추가한다.
NODE *g_pTail = &g_head;
/*
NODE *g_pTail = 0; // 다른 방법
*/
추가된 Tail 포인터를 활용해 기존 코드를 개선한다.
int InsertAtHead(char *pszData)
{
NODE *pNode = (NODE *)malloc(sizeof(NODE));
if (pNode == NULL)
return 0;
memset(pNode, 0, sizeof(NODE));
strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);
if (IsEmpty())
g_head.next = pNode;
else
{
pNode->next = g_head.next;
g_head.next = pNode;
}
return 1;
}
int InsertAtHead(char *pszData)
{
NODE *pNode = (NODE *)malloc(sizeof(NODE));
if (pNode == NULL)
return 0;
memset(pNode, 0, sizeof(NODE));
strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);
if (IsEmpty())
{
g_head.next = pNode;
g_pTail = pNode;
}
else
{
pNode->next = g_head.next;
g_head.next = pNode;
}
return 1;
}
int InsertAtTail(char *pszData)
{
// 마지막 노드 찾기
NODE *pTmp = &g_head;
while (pTmp->next != NULL)
pTmp = pTmp->next;
NODE *pNode = (NODE *)malloc(sizeof(NODE));
if (pNode == NULL)
return 0;
memset(pNode, 0, sizeof(NODE));
strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);
pTmp->next = pNode;
return 1;
}
int InsertAtTail(char *pszData)
{
NODE *pNode = (NODE *)malloc(sizeof(NODE));
if (pNode == NULL)
return 0;
memset(pNode, 0, sizeof(NODE));
strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);
if (IsEmpty())
g_head.next = pNode;
else
g_pTail->next = pNode;
g_pTail = pNode;
return 1;
}
int DeleteData(char *pszData)
{
NODE *pPrev = FindData(pszData);
if (pPrev != NULL)
{
NODE *pDelete = pPrev->next;
pPrev->next = pDelete->next;
printf("DeleteData(): %s\n", pDelete->szData);
free(pDelete);
return 1;
}
return 0;
}
int DeleteData(char *pszData)
{
NODE *pPrev = FindData(pszData);
if (pPrev != NULL)
{
NODE *pDelete = pPrev->next;
pPrev->next = pDelete->next;
printf("DeleteData(): %s\n", pDelete->szData);
if (pDelete == g_pTail)
g_pTail = pPrev;
free(pDelete);
printf("g_Tail: [%p], Dummy head: [%p]\n", g_pTail, &g_head);
return 1;
}
return 0;
}
int PopData(NODE *pPopNode)
{
NODE *sp = g_head.next;
if (IsEmpty())
return 0;
memcpy(pPopNode, sp, sizeof(NODE));
g_head.next = sp->next;
free(sp);
return 1;
}
int PopData(NODE *pPopNode)
{
NODE *sp = g_head.next;
if (IsEmpty())
return 0;
memcpy(pPopNode, sp, sizeof(NODE));
g_head.next = sp->next;
if (sp == g_pTail || g_head.next == NULL)
g_pTail = &g_head;
printf("g_Tail: [%p], Dummy head: [%p]\n", g_pTail, &g_head);
free(sp);
return 1;
}
int main(void)
{
Equeue("TEST01");
Equeue("TEST02");
Equeue("TEST03");
PrintList();
NODE node;
PopData(&node);
PopData(&node);
PopData(&node);
putchar('\n');
Equeue("TEST01");
Equeue("TEST02");
Equeue("TEST03");
PrintList();
DeleteData("TEST01");
DeleteData("TEST02");
DeleteData("TEST03");
putchar('\n');
ReleaseList();
return 0;
}