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

2중 연결 리스트 구현

2중 연결 리스트 노드 추가

• 추가할 노드의 prev, next 정보를 먼저 설정한다.
• 노드 삽입이 일어나는 지점의 prev 노드를 찾는다. (반대로 next 노드를 찾아도 상관없다.)
• 첫 번째로 추가되는 노드와 이후 추가되는 방식은 구분한다.

InsertAtHead()

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

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

2중 연결 리스트 노드 삭제

FindNode() & DeleteNode()

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);
    
    free(pNode);
    return 0;
}

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

테스트

int main(void)
{
	InitList();

	InsertAtHead("TEST01");
    InsertAtHead("TEST02");
    InsertAtHead("TEST03");
    PrintList();
    putchar('\n');

    printf("FindNode(): %p\n", FindNode("TEST01"));
    printf("FindNode(): %p\n", FindNode("TEST02"));
    printf("FindNode(): %p\n", FindNode("TEST03"));
	putchar('\n');

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

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

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

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

    printf("FindNode(): %p\n", FindNode("TEST01"));
    printf("FindNode(): %p\n", FindNode("TEST02"));
    printf("FindNode(): %p\n", FindNode("TEST03"));
	putchar('\n');

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

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

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

	return 0;
}

실행 결과

참고 자료

• https://www.youtube.com/watch?v=_z1eEef5YtE&t=39s
• https://www.youtube.com/watch?v=0_COzB4AM-U