[자료구조] 2중 연결 리스트(Doubly Linked List) 중간 삽입 구현

bolee·2022년 10월 13일

C 자료구조

자료구조

목록 보기

9/10

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

2중 연결 리스트 중간 삽입 구현

아래 2중 연결 리스트 예제에 인덱스를 받아 중간에 노드를 삽입하는 함수를 추가하기로 하였다.

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

/* 노드 구조체 정의 */
typedef struct NODE
{
	char szData[64];
    
	struct NODE *prev;
    struct NODE *next;
} NODE;

/* 전역 dummy head, tail 포인터 정의 */
NODE *g_pHead;
NODE *g_pTail;

/* 전역 2중 연결리스트 사이즈 변수 정의 */
int g_nSize;

/* 전역 변수 초기화 함수 */
void InitList(void)
{
	g_pHead = (NODE *)malloc(sizeof(NODE));
    g_pTail = (NODE *)malloc(sizeof(NODE));
    g_nSize = 0;
    
    memset(g_pHead, 0, sizeof(NODE));
    memset(g_pTail, 0, sizeof(NODE));
    
    strcpy_s(g_pHead->szData, sizeof(g_pHead->szData), "DUMMY HEAD");
    strcpy_s(g_pTail->szData, sizeof(g_pTail->szData), "DUMMY TAIL");
    
    g_pHead->next = g_pTail;
    g_pTail->prev = g_pHead;
}

/* 2중 연결 리스트 메모리 해제 함수 */
void ReleaseList(void)
{
	NODE *pTmp = g_pHead;
    while (pTmp != NULL)
    {
    	NODE *pDelete = pTmp;
    	pTmp = pTmp->next;
        
        printf("free(%p)\n", pDelete);
        free(pDelete);
    }
    
    g_pHead = NULL;
    g_pTail = NULL;
    g_nSize = 0;
    
    puts("ReleaseList()");
}

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

/* 맨 앞부분에 데이터 추가 함수 */
int InsertAtHead(const char *pszData)
{
	NODE *pNewNode = (NODE *)malloc(sizeof(NODE));
    memset(pNewNode, 0, sizeof(NODE));
    
    strcpy_s(pNewNode->szData, sizeof(pNewNode->szData), pszData);

	pNewNode->prev = g_pHead;
    pNewNode->next = g_pHead->next;
    
    g_pHead->next = pNewNode;
    pNewNode->next->prev = pNewNode;

	g_nSize++;
    return g_nSize;
}

/* 맨 뒷부분에 데이터 추가 함수 */
int InsertAtTail(const char *pszData)
{
	NODE *pNewNode = (NODE *)malloc(sizeof(NODE));
    memset(pNewNode, 0, sizeof(NODE));
    
    strcpy_s(pNewNode->szData, sizeof(pNewNode->szData), pszData);

	pNewNode->next = g_pTail;
    pNewNode->prev = g_pTail->prev;
    
    g_pTail->prev = pNewNode;
    pNewNode->prev->next = pNewNode;

	g_nSize++;
    return g_nSize;
}

/* 해당 데이터가 존재하는 노드를 찾는 함수 */
NODE *FindNode(const char *pszData)
{
	NODE *pTmp = g_pHead->next;
    while (pTmp != g_pTail)
    {
    	if (strcmp(pTmp->szData, pszData) == 0)
        	return pTmp;
        pTmp = pTmp->next;
    }
    return NULL;
}

/* 해당 데이터가 존재하는 노드를 삭제하는 함수 */
int DeleteNode(const char *pszData)
{
	NODE *pNode = FindNode(pszData);
    
    pNode->prev->next = pNode->next;
    pNode->next->prev = pNode->prev;
    
    printf("DeleteNode(): %p\n", pNode);
    
    g_nSize--;
    
    free(pNode);
    return 0;
}

/* 2중 연결 리스트의 전체 크기를 반환하는 함수 */
int GetSize(void)
{
	return g_nSize;
}

/* 2중 연결 리스트의 전체 크기를 반환하는 함수 */
int GetLength(void)
{
	return GetSize();
}

/* 2중 연결 리스트가 비어 있는지 확인하는 함수*/
int IsEmpty(void)
{
	return GetSize();
}

새로 추가 및 수정된 함수

추가된 함수

InsertBefore()
InsertAt()
GetAt()

수정된 함수

InsertAtTail()

InsertBefore()

InsertAt() 함수를 구현하기 쉽게하기 위해 해당 노드 이전에/앞에 노드를 삽입하는 함수를 구현하였다.

void InsertBefore(NODE *pDstNode, const char *pszData)
{
	NODE *pPrev = pDstNode->prev;
    
    NODE *pNewNode = (NODE *)malloc(sizeof(NODE));
    memset(pNewNode, 0, sizeof(NODE));
    strcpy_s(pNewNode->szData, sizeof(pNewNode->szData), pszData);
    
    pNewNode->prev = pPrev;
    pNewNode->next = pDstNode;
    
    pPrev->next = pNewNode;
    pDstNode->prev = pNewNode;
    
    g_nSize++;
}

InsertAtTail()

InsertBefore() 함수를 구현하다 보니 기존의 InsertAtTail() 함수와 중복되는 코드가 많아 InsertAtTail() 함수를 수정하였다.

기존

int InsertAtTail(const char *pszData)
{
	NODE *pNewNode = (NODE *)malloc(sizeof(NODE));
    memset(pNewNode, 0, sizeof(NODE));
    
    strcpy_s(pNewNode->szData, sizeof(pNewNode->szData), pszData);

	pNewNode->next = g_pTail;
    pNewNode->prev = g_pTail->prev;
    
    g_pTail->prev = pNewNode;
    pNewNode->prev->next = pNewNode;

	g_nSize++;
    return g_nSize;
}

수정

int InsertAtTail(const char *pszData)
{
	InsertBefore(g_pTail, pszData);
    return g_nSize;
}

InsertAt()

int InsertAt(int idx, const char *pszData)
{
	int i = 0;
    NODE *pTmp = g_pHead->next;
    while (pTmp != g_pTail)
    {
    	if (i == idx)
        {
        	InsertBefore(pTmp, pszData);
            return i;
        }
        pTmp = pTmp->next;
        i++;
    }
    
    InsertAtTail(pszData);
    return i;
}

GetAt()

NODE *GetAt(int idx)
{
	int i = 0;
    NODE *pTmp = g_pHead->next;
    while (pTmp != g_pTail)
    {
    	if (i == idx)
        	return pTmp;
            
        pTmp = pTmp->next;
        i++:
    }
    
    return NULL;
}

테스트

int main(void)
{
	InitList();

	InsertAtTail("TEST01");
    InsertAtTail("TEST02");
    InsertAtTail("TEST03");

    PrintList();
    putchar('\n');

    InsertAt(0, "TEST AT 00");
    PrintList();
    putchar('\n');

    InsertAt(2, "TEST AT 02");
    PrintList();
    putchar('\n');

    InsertAt(4, "TEST AT 04");
    PrintList();
    putchar('\n');

    InsertAt(10, "TEST AT 10");
    PrintList();
    putchar('\n');

    NODE *pNode = GetAt(0);
    if (pNode)
    	printf("GetAt(%d): %s\n", 0, pNode->szData);
    else
    	printf("GetAt(%d): %s\n", 0, "Not found");

    pNode = GetAt(3);
    if (pNode)
    	printf("GetAt(%d): %s\n", 3, pNode->szData);
    else
    	printf("GetAt(%d): %s\n", 3, "Not found");

    pNode = GetAt(6);
    if (pNode)
    	printf("GetAt(%d): %s\n", 6, pNode->szData);
    else
    	printf("GetAt(%d): %s\n", 6, "Not found");

    pNode = GetAt(7);
    if (pNode)
    	printf("GetAt(%d): %s\n", 7, pNode->szData);
    else
    	printf("GetAt(%d): %s\n", 7, "Not found");
    putchar('\n');

    DeleteNode("TEST01");
    DeleteNode("TEST02");
    DeleteNode("TEST03");
    putchar('\n');

    PrintList();
    putchar('\n');

	ReleaseList();
    putchar('\n');

	return 0;
}