[자료구조] 단일 연결 리스트(Single Linked List) Tail 포인터 추가

bolee·2022년 9월 27일
C자료구조
0

자료구조

목록 보기
6/10

널널한 개발자 TV의 자료구조 강의 시리즈를 정리할 것이다.

리스트에 Tail 포인터 추가

연결 리스트에 데이터를 추가할 때 맨 마지막에 추가하려면 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 포인터 추가

Tail 포인터를 추가한다.

NODE *g_pTail = &g_head;
/*
NODE *g_pTail = 0;	// 다른 방법
*/

추가된 Tail 포인터를 활용해 기존 코드를 개선한다.

코드 개선

InsertAtHead()

기존 코드

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;
}

InsertAtTail()

기존 코드

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;
}

DeleteData()

기존 코드

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;
}

PopData()

기존 코드

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;
}

실행 결과

참고 자료

profile
bolee
이전 포스트

[자료구조] 단일 연결 리스트(Single Linked List)로 큐(Queue) 구현

다음 포스트

[자료구조] 2중 연결 리스트(Doubly linked list) Introduction

0개의 댓글