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

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

자료구조

목록 보기
3/10
post-thumbnail

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

Single Linked List 구현 방법

첫 번째 데이터를 어떻게 할 것인가에 따라 구현 방법이 달리진다.
해당 방법에는 여러 방법이 있다.

포인터 변수 사용

첫 번째 데이터를 가리키는 것을 포인터 변수 하나로 두는 방법

더미 노드(Dummy node) 사용

데이터는 없고, 데이터 저장용이 아닌 순수 관리 목적의 노드를 만들어 사용하는 방법

연결 리스트 코딩 순서

  • 전체 리스트 출력 함수 작성
  • 새 노드 추가 함수 작성(개발에 앞서 절차를 정확히 글로 기술한다.)
  • 전체 리스트 삭제 함수 작성
  • 각 함수를 작성할 때마다 main()에서 테스트 코드를 실행한다.
    • 테스트 시 free()를 고려하지 않고 작성하며 구현에 집중한다.

연결 리스트 예제

포인터 변수 사용

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct NODE
{
	char szData[64];
    struct NODE *next;
} NODE;

NODE *g_pHead = NULL;	// 헤드 노드

/* 연결 리스트 전체 리스트 출력 함수 */
void PrintList(void)
{
	NODE *pHead = g_pHead;
    
	while (pHead != NULL)
    {
    	printf("[%p] %s, next[%p]\n", pHead, pHead->szData, pHead->next);
        pHead = pHead->next;
    }
    printf("\n");
}

/* 앞부분에 새 노드 추가 함수 */
int InsertNewNode(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 (g_pHead == NULL)
    	g_pHead = pNode;
    else
    {
    	pNode->next = g_pHead;
        g_pHead = pNode;
    }
    
    return 1;
}

/* 연길 리스트 전체 리스트 삭제 */
void ReleaseList(void)
{
	NODE *pTmp = g_pHead;
    
    while (pTmp != NULL)
    {
    	// 반복문 내에서 변수 선언하는 것이 안좋지만 최근에는 애매함
        // 컴파일러가 최적화를 잘 해주기 때문
        // 오히려 접근성 제한으로 일부로 하는 경우도 존재
    	NODE *pDelete = pTmp;
        pTmp = pTmp->next;
        
        printf("Delete: [%p] %s\n", pDelete, pDelete->szData);
        free(pDelete);
    }
}

/* 특정 노드를 존재하는 지 확인하는 함수 */
int FindData(char *pszData)
{
	NODE *pTmp = g_pHead;
    while (pTmp != NULL)
    {
    	if (strcmp(pTmp->szData, pszData) == 0)
        	return 1;
        pTmp = pTmp->next;
    }
    
    return 0;
}

/* 특정 노드를 찾아 삭제하는 함수*/
int DeleteData(char *pszData)
{
	NODE *pTmp = g_pHead;
    NODE *pPrev = NULL;
    while (pTmp != NULL)
    {
    	if (strcmp(pTmp->szData, pszData) == 0)
        {
        	// 삭제
            if (pPrev != NULL)
	            pPrev->next = pTmp->next;
            else
            {
            	// 삭제할 데이터가 첫 번째
                g_pHead = pTmp->next;
            }
            free(pTmp);
        	return 1;
        }
        pPrev = pTmp;
    	pTmp = pTmp->next;
    }
    
    return 0;
}

int main(void)
{
	// List 테스트를 위한 코드
    InsertNewNode("TEST01");
    PrintList();
    InsertNewNode("TEST02");
    PrintList();
    InsertNewNode("TEST03");
    PrintList();

    if (FindData("TEST01") == 1)
    	printf("FindData(): TEST01 found\n");
    if (FindData("TEST02") == 1)
    	printf("FindData(): TEST02 found\n");
    if (FindData("TEST03") == 1)
    	printf("FindData(): TEST03 found\n");
    putchar('\n');

    DeleteData("TEST03");
    PrintList();
    DeleteData("TEST02");
    PrintList();
    DeleteData("TEST01");
    PrintList();
    
    ReleaseList();
    
	return 0;
}

실행 결과

더미 노드(Dummy node) 사용

#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;
    
    while (pTmp != NULL)
    {
    	NODE *pDelete = pTmp;
        pTmp = pTmp->next;
        
        printf("Delete: [%p] %s\n", pDelete, pDelete->szData);
        free(pDelete);
    }
    g_head.next = NULL;
}

/* 특정 노드를 존재하는 지 확인하는 함수 */
int FindData(char *pszData)
{
	NODE *pCur = g_head.next;
    NODE *pPrev = &g_head;
    while (pCur != NULL)
    {
    	if (strcmp(pCur->szData, pszData) == 0)
        	return 1;
        pCur = pCur->next;
        pPrev = pPrev->next;
    }
    
    return 0;
}

/* 특정 노드를 찾아 삭제하는 함수*/
int DeleteData(char *pszData)
{
	NODE *pCur = g_head.next;
    NODE *pPrev = &g_head;
    
    while (pCur != NULL)
    {
    	if (strcmp(pCur->szData, pszData) == 0)
        {
        	// 삭제
            printf("DeleteData(): %s\n", pCur->szData);
			pPrev->next = pCur->next;
            free(pCur);
        	return 1;
        }
        
        pCur = pCur->next;
    	pPrev = pPrev->next;
    }
    
    return 0;
}

int main(void)
{
	// List 테스트를 위한 코드
    puts("*** InsertAtHead() ***");
    InsertAtHead("TEST01");
    InsertAtHead("TEST01");
    InsertAtHead("TEST01");
    PrintList();
    
    if (FindData("TEST01") == 1)
    	printf("FindData(): TEST01 found\n");
    if (FindData("TEST02") == 1)
    	printf("FindData(): TEST02 found\n");
    if (FindData("TEST03") == 1)
    	printf("FindData(): TEST03 found\n");
    putchar('\n');
    
    DeleteData("TEST01");
    PrintList();
    DeleteData("TEST02");
    PrintList();
    DeleteData("TEST03");
    PrintList();
    
    puts("*** InsertAtTail() ***");
    InsertAtTail("TEST01");
    InsertAtTail("TEST01");
    InsertAtTail("TEST01");
    PrintList();
    
    if (FindData("TEST01") == 1)
    	printf("FindData(): TEST01 found\n");
    if (FindData("TEST02") == 1)
    	printf("FindData(): TEST02 found\n");
    if (FindData("TEST03") == 1)
    	printf("FindData(): TEST03 found\n");
    putchar('\n');
    
    DeleteData("TEST01");
    PrintList();
    DeleteData("TEST02");
    PrintList();
    DeleteData("TEST03");
    PrintList();
    
    ReleaseList();
	return 0;
}

실행 결과

FindData()와 DeleteData() 코드 개선

이전 FindData()과 DeleteData()

/* 특정 노드를 존재하는 지 확인하는 함수 */
int FindData(char *pszData)
{
	NODE *pCur = g_head.next;
    NODE *pPrev = &g_head;
    while (pCur != NULL)
    {
    	if (strcmp(pCur->szData, pszData) == 0)
        	return 1;
        pCur = pCur->next;
        pPrev = pPrev->next;
    }
    
    return 0;
}

/* 특정 노드를 찾아 삭제하는 함수*/
int DeleteData(char *pszData)
{
	NODE *pCur = g_head.next;
    NODE *pPrev = &g_head;
    
    while (pCur != NULL)
    {
    	if (strcmp(pTmp->szData, pszData) == 0)
        {
        	// 삭제
            printf("DeleteData(): %s\n", pCur->szData);
			pPrev->next = pCur->next;
            free(pCur);
        	return 1;
        }
        
        pCur = pCur->next;
    	pPrev = pPrev->next;
    }
    
    return 0;
}

코드 개선 후 FindData()과 DeleteData()

/* 특정 노드를 존재하는 지 확인하는 함수 */
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;
}

참고 자료

profile
bolee
이전 포스트

[자료구조] 단일 연결 리스트(Single linked list) Introduction

다음 포스트

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

0개의 댓글