[자료구조] Doubly Linked List ADT 적용 - 1

bolee·2022년 12월 7일
C자료구조
0

자료구조

목록 보기
10/10
post-thumbnail

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

ADT

  • ADT(Abstract Data Type)
  • 추상 자료형이라고 하며, 핵심은 자료와 관리체계를 분리하는 것이다.
  • 연결 리스트의 prev, next,포인터는 관리체계이며 연결 리스트 사용자가 임의로 접근하거나 변경하지 않아야 한다.

기존 이중 연결 리스트

#include <stdio.h>
#include <string.h>
#include <stdlib.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 InsertBefore(NODE *pDstNode, const char *pszData);

/* 전역 변수 초기화 함수 */
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)
{
	InsertBefore(g_pTail, pszData);
    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();
}

/* 해당 노드 뒤에 새로운 노드를 추가하는 함수 */
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++;
}

/* 해당 인덱스에 새로운 노드를 추가하는 함수 */
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;
}

/* 인덱스에 해당하는 노드를 반환하는 함수 */
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;
}

ADT 적용 이중 연결 리스트

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

/* 관리 대상 데이터 */
typedef struct USERDATA 
{
    char szName[64];
    char szPhone[64];
} USERDATA;

/* 노드 구조체 정의 */
typedef struct NODE
{
    // 관리 대상 자료
	USERDATA *pData;
    
    // 자료 구조
	struct NODE *prev;
    struct NODE *next;
} NODE;

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

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

void InsertBefore(NODE *pDstNode, const USERDATA *pParam);

/* 전역 변수 초기화 함수 */
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));
    
    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->pData);
        free(pDelete);
    }
    
    g_pHead = NULL;
    g_pTail = NULL;
    g_nSize = 0;

    puts("ReleaseList()");
}

/* 2중 연결 리스트 전체 출력 함수 */
void PrintList(void)
{
    int i = 0;
	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)
    {
        if (pTmp == g_pHead || pTmp == g_pTail)
        	printf("[%p] DUMMY [%p]\n", pTmp->prev, pTmp->next);
        else
        {
        	printf("index:%d [%p] %p, %s, %s [%p]\n", \
                i, pTmp->prev, pTmp, \
                pTmp->pData->szName, \
                pTmp->pData->szPhone, \
                pTmp->next);
            ++i;
        }
    	pTmp = pTmp->next;
    }

    putchar('\n');
}

/* 맨 앞부분에 데이터 추가 함수 */
// pParam: 호출자가 메모리를 동적 할당 및 값 설정하여 전달
int InsertAtHead(const USERDATA *pParam)
{
	NODE *pNewNode = (NODE *)malloc(sizeof(NODE));
    memset(pNewNode, 0, sizeof(NODE));

    pNewNode->pData = pParam;

	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 USERDATA *pParam)
{
	InsertBefore(g_pTail, pParam);
    return g_nSize;
}

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

        pTmp = pTmp->next;
    }

    return NULL;
}

/* 해당 데이터가 존재하는 노드를 삭제하는 함수 */
int DeleteNode(const char *pszName)
{
	NODE *pNode = FindNode(pszName);
    
    pNode->prev->next = pNode->next;
    pNode->next->prev = pNode->prev;

    printf("DeleteNode(): %p\n", pNode);
    
    g_nSize--;

    free(pNode->pData);    
    free(pNode);
    return 0;
}

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

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

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

/* 해당 노드 뒤에 새로운 노드를 추가하는 함수 */
void InsertBefore(NODE *pDstNode, const USERDATA *pParam)
{
	NODE *pPrev = pDstNode->prev;

	NODE *pNewNode = (NODE *)malloc(sizeof(NODE));
	memset(pNewNode, 0, sizeof(NODE));

    pNewNode->pData = pParam;

	pNewNode->prev = pPrev;
	pNewNode->next = pDstNode;

	pPrev->next = pNewNode;
	pDstNode->prev = pNewNode;

	g_nSize++;
}

/* 해당 인덱스에 새로운 노드를 추가하는 함수 */
int InsertAt(int idx, const USERDATA *pParam)
{
	int i = 0;
	NODE *pTmp = g_pHead->next;

	while (pTmp != g_pTail)
	{
		if (i == idx)
		{
			InsertBefore(pTmp, pParam);
			return i;
		}
		pTmp = pTmp->next;
		i++;
	}

	InsertAtTail(pParam);
	return i;
}

/* 인덱스에 해당하는 노드를 반환하는 함수 */
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;
}

주요 수정 부분

ADT의 핵심처럼 기존 노드를 자료와 관리체계 여기에서는 데이터를 담는 구조체와 이중 연결 리스트 구조로 분리하여 함수를 수정하였다.

기존

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

수정

/* 관리 대상 데이터 */
typedef struct USERDATA 
{
    char szName[64];
    char szPhone[64];
} USERDATA;

/* 노드 구조체 정의 */
typedef struct NODE
{
    // 관리 대상 자료
	USERDATA *pData;
    
    // 자료 구조
	struct NODE *prev;
    struct NODE *next;
} NODE;

테스트

int main(void)
{
	InitList();

    USERDATA *pNewData = (USERDATA *)malloc(sizeof(USERDATA));
    memset(pNewData, 0, sizeof(USERDATA));
    strcpy_s(pNewData->szName, sizeof(pNewData->szName), "BOLEE");
    strcpy_s(pNewData->szPhone, sizeof(pNewData->szPhone), "010-1234-1234");
    InsertAtTail(pNewData);


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

	return 0;
}

실행 결과

PrintList(): g_nSize 1, g_pHead [0x7f9c41405850], g_pTail [0x7f9c41405870]
[0x0] DUMMY [0x7f9c41405910]
index:0 [0x7f9c41405850] 0x7f9c41405910, BOLEE, 010-1234-1234 [0x7f9c41405870]
[0x7f9c41405910] DUMMY [0x0]

free(0x7f9c41405850)
free(0x7f9c41405910)
free(0x7f9c41405870)
ReleaseList()

참고 자료

profile
bolee
이전 포스트

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

0개의 댓글